Алгоритм поиска циклов

Ответ 1

Вот что я сделал. Я не знаю, оптимизирован ли он, но он работает правильно. Я не сделал сортировку очков, как предложил @marcog.

private static bool LoopSearch2(bool[,] mask, int supIndexStart, int recIndexStart, out List<MyPoint> path)
    {
        List<MyPoint> points = new List<MyPoint>();
        points.Add(new MyPoint { X = recIndexStart, Y = supIndexStart });

        for (int i = 0; i < mask.GetLength(0); i++)
        {
            for (int j = 0; j < mask.GetLength(1); j++)
            {
                if (mask[i, j])
                {
                    points.Add(new MyPoint { X = j, Y = i });
                }
            }
        }

        for (int i = 0; i < points.Count; i++)
        {
            for (int j = 0; j < points.Count; j++)
            {
                if (i != j)
                {
                    if (points[i].X == points[j].X || points[i].Y == points[j].Y)
                    {
                        points[i].Neighbours.Add(points[j]);
                    }
                }
            }
        }

        List<MyPoint> queue = new List<MyPoint>();
        MyPoint start = (points[0]);
        start.marked = true;
        queue.Add(points[0]);

        path = new List<MyPoint>();

        bool found = false;

        while(queue.Count>0)
        {
            MyPoint current = queue.First();
            queue.Remove(current);

            foreach (MyPoint neighbour in current.Neighbours)
            {
                if (!neighbour.marked)
                {
                    neighbour.marked = true;
                    neighbour.parent = current;
                    queue.Add(neighbour);
                }
                else
                {
                    if (neighbour.parent != null && neighbour.parent.Equals(current))
                        continue;

                    if (current.parent == null)
                        continue;

                    bool previousConnectionHorizontal = current.parent.Y == current.Y;
                    bool currentConnectionHorizontal = current.Y == neighbour.Y;

                    if (previousConnectionHorizontal != currentConnectionHorizontal)
                    {
                        MyPoint prev = current;

                        while (true)
                        {
                            path.Add(prev);
                            if (prev.Equals(start))
                                break;
                            prev = prev.parent;
                        }

                        path.Reverse();

                        prev = neighbour;

                        while (true)
                        {
                            if (prev.Equals(start))
                                break;
                            path.Add(prev);                                
                            prev = prev.parent;
                        }

                        found = true;
                        break;
                    }                      
                }
                if (found) break;
            }
            if (found) break;
        }

        if (path.Count == 0)
        {
            path = null;
            return false;
        }
        return true;   
    }   

Ответ 2

Прежде всего, вы должны изменить свое представление на более эффективное. Вы должны сделать вершину структурой/классом, который хранит список связанных вершин.

Изменив представление, вы можете легко найти кратчайший цикл, используя поиск в ширину.

Вы можете ускорить поиск с помощью следующего трюка: пересечь график в порядке ширины, маркировать пройденные вершины (и хранить "родительскую вершину" на пути к корню в каждой вершине). Как только вы найдете уже отмеченную вершину, поиск завершен. Вы можете найти два пути от найденной вершины к корню, возвращаясь к сохраненным "родительским" вершинам.

Edit:
Вы уверены, что код правильный? Я попробовал следующее:

while (queue.Count > 0)
{
    MyPoint current = queue.First(); //taking point from queue
    queue.Remove(current);           //removing it

    foreach (MyPoint neighbour in current.Neighbours) //checking Neighbours
    {
        if (!neighbour.marked) //if neighbour isn't marked adding it to queue
        {
            neighbour.marked = true;
            neighbour.parent = current;
            queue.Add(neighbour);
        }
        else if (!neighbour.Equals(current.parent)) // not considering own parent
        {
            // found!
            List<MyPoint> loop = new List<MyPoint>();
            MyPoint p = current;
            do
            {
                loop.Add(p);
                p = p.parent;
            }
            while (p != null);
            p = neighbour;
            while (!p.Equals(start))
            {
                loop.Add(p);
                p = p.parent;
            }
            return loop;
        }
    }
}

return null;

вместо соответствующей части вашего кода (я тоже изменил тип возврата на List<MyPoint>). Он работает и правильно находит меньшую петлю, состоящую из трех точек: красной точки, точки непосредственно выше и точки непосредственно ниже.

Ответ 3

Шаг удаления точек в худшем случае O (N ^ 3), если он выполняется плохо, в худшем случае - удаление одной точки на каждой итерации. И так как он не всегда сохраняет вас столько вычислений в определении цикла, я бы избегал этого, так как он также добавляет дополнительный уровень сложности в решение.

Начните с создания списка смежности из набора точек. Вы можете сделать это эффективно в O (NlogN), если сортировать точки по X и Y (отдельно) и итерации по точкам по порядку X и Y. Затем, чтобы найти кратчайшую длину цикла (определяемую количеством точек), начните a BFS из каждой точки, изначально бросая все точки в очереди. По мере прохождения по краю сохраните источник пути вместе с текущей точкой. Затем вы узнаете, когда BFS вернется к источнику, и в этом случае мы нашли цикл. Если вы закончите с пустой очередью, прежде чем найти цикл, то не существует. Будьте осторожны, чтобы не отследить назад до предыдущей точки, или вы закончите с неработающим циклом, образованным двумя точками. Вы также можете избежать, например, цикла, образованного точками (0, 0), (0, 2) и (0, 1), поскольку это образует прямую линию.

BFS потенциально имеет худший случай экспоненциальности, но я считаю, что такой случай может быть доказан, что он не существует или будет чрезвычайно редок, поскольку более плотный граф быстрее, чем вы найдете цикл, в то время как более редкий график меньше ваша очередь будет. В среднем он, скорее всего, будет ближе к той же самой среде исполнения, что и конструкция списка смежности, или к худшим реалистичным случаям O (N ^ 2).

Ответ 4

Я думаю, что я использовал адаптированный вариант Dijkstra algorithm, который останавливает и возвращает цикл всякий раз, когда он прибывает в любой node для второй раз. Если этого не происходит, у вас нет цикла.

Этот подход должен быть намного более эффективным, чем поиск по ширине или глубине, особенно если у вас много узлов. Гарантируется, что вы будете посещать только каждый node один раз, таким образом, у вас есть линейное время выполнения.