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

Question

Мне нужно найти цикл, начинающийся и заканчивающийся в данной точке. Не гарантируется, что оно существует. Я использую bool[,] points, чтобы указать, какая точка может быть в цикле. Точки могут быть только на сетке. points указывает, может ли данная точка на сетке находиться в цикле. Мне нужно найти этот цикл, используя как минимальное количество баллов. Одна точка может быть использована только один раз. Соединение может быть только вертикальным или горизонтальным.

Пусть это будут наши точки (красный - отправная точка):

удаление мертвых ссылок ImageShack

Я понял, что могу сделать это:

while(numberOfPointsChanged)
{
    //remove points that are alone in row or column
}

Итак, у меня есть:

удаление мертвых ссылок ImageShack

Теперь я могу найти путь.

удаление мертвых ссылок ImageShack

Но что, если есть точки, которые не удаляются этим циклом, но не должны находиться в пути?

Я написал код:

class MyPoint
{
    public int X { get; set; }
    public int Y { get; set; }
    public List<MyPoint> Neighbours = new List<MyPoint>();
    public MyPoint parent = null;
    public bool marked = false;
}

    private static MyPoint LoopSearch2(bool[,] mask, int supIndexStart, int recIndexStart)
    {
        List<MyPoint> points = new List<MyPoint>();

        //here begins translation bool[,] to list of points
        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]);
                    }
                }
            }
        }
        //end of translating

        List<MyPoint> queue = new List<MyPoint>();
        MyPoint start = (points[0]); //beginning point
        start.marked = true; //it is marked
        MyPoint last=null;   //last point. this will be returned
        queue.Add(points[0]);


        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) //in neighbour isn't marked adding it to queue
                {
                    neighbour.marked = true;
                    neighbour.parent = current;
                    queue.Add(neighbour);
                }
                //if neighbour is marked checking if it is startig point and if neighbour's parent is current point. if it is not that means that loop already got here so we start searching parents to got to starting point
                else if(!neighbour.Equals(start) && !neighbour.parent.Equals(current))
                {                        
                    current = neighbour;
                    while(true)
                    {
                        if (current.parent.Equals(start))
                        {
                            last = current;
                            break;
                        }
                        else
                            current = current.parent;

                    }
                    break;
                }
            }
        }

        return last;            
    }

Но это не работает. Найденный путь содержит две точки: начало и его первый сосед.
Что я делаю не так?

EDIT: Забыл упомянуть ... После горизонтального соединения должно быть вертикальное, горизонтальное, вертикальное и так далее ... Более того, в каждой строке и столбце должно быть максимум две точки (две или ни одной), которые находятся в цикле. Но это условие такое же, как «цикл должен быть самым коротким».

Answer 1

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

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

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

---

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

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 точек: красная точка, точка непосредственно над и точка ниже.

Answer 2

Это то, что я сделал. Я не знаю, оптимизирован ли он, но он работает правильно. Я не сделал сортировку точек, как предложил @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;   
    }   

Answer 3

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

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

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

Answer 4

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

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