algorithm por Algoritmo de búsqueda de ciclo



busqueda en profundidad java (4)

Creo que usaría una variante adaptada del algoritmo de Dijkstra que detiene y devuelve el ciclo cada vez que llega a un nodo por segunda vez. Si esto nunca sucede, no tienes un ciclo.

Este enfoque debería ser mucho más eficiente que una búsqueda de ancho primero o de profundidad primero, especialmente si tiene muchos nodos. Se garantiza que solo visitará cada nodo una vez, por lo tanto, tendrá un tiempo de ejecución lineal.

Necesito encontrar un ciclo que comience y termine en un punto dado. No se garantiza que exista. Uso bool[,] points para indicar qué punto puede estar en ciclo. Los puntos pueden estar solo en la cuadrícula. points indica si el punto dado en la cuadrícula puede estar en ciclo. Necesito encontrar este ciclo usando como mínimo número de puntos. Un punto se puede usar solo una vez. La conexión puede ser solo vertical u horizontal.

Deje que este sea nuestro punto (el rojo es el punto de partida):

eliminar enlaces muertos de ImageShack

Me di cuenta de que puedo hacer esto:

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

Así que tengo:

eliminar enlaces muertos de ImageShack

Ahora, puedo encontrar el camino.

eliminar enlaces muertos de ImageShack

Pero, ¿qué pasa si hay puntos que no son eliminados por este bucle pero que no deberían estar en la ruta?

He escrito el código:

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;            
    }

Pero no funciona. La ruta que encuentra contiene dos puntos: inicio y es el primer vecino.
¿Qué estoy haciendo mal?

EDITAR: se olvidó de mencionar ... Después de la conexión horizontal tiene que haber vertical, horizontal, vertical y así sucesivamente ... Lo que es más en cada fila y columna debe haber máximo dos puntos (dos o ninguno) que están en el ciclo. Pero esta condición es la misma que "El ciclo tiene que ser el más corto".


Answer #1

Eso es lo que hice. No sé si está optimizado pero funciona correctamente. No he hecho la clasificación de los puntos como sugirió @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 #2

En primer lugar, debe cambiar su representación por una más eficiente. Debería hacer de los vértices una estructura / clase, que mantiene la lista de los vértices conectados.

Después de cambiar la representación, puede encontrar fácilmente el ciclo más corto utilizando la búsqueda de amplitud .

Puede acelerar la búsqueda con el siguiente truco: recorra el gráfico en orden de amplitud, marcando los vértices atravesados ​​(y almacenando el número de "vértice principal" en el camino hacia la raíz en cada vértice). Tan pronto como encuentre un vértice ya marcado, la búsqueda habrá finalizado. Puede encontrar las dos rutas desde el vértice encontrado hasta la raíz retrocediendo por los vértices "principales" almacenados.

Editar:
¿Estás seguro de que tu código es correcto? Intenté lo siguiente:

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;

en lugar de la parte correspondiente en su código (también cambié el tipo de devolución a List<MyPoint> ). Funciona y encuentra correctamente un bucle más pequeño, que consta de 3 puntos: el punto rojo, el punto directamente arriba y el punto directamente debajo.


Answer #3

El paso de eliminación de puntos es el peor de los casos O (N ^ 3) si se implementa mal, en el peor de los casos se elimina un punto en cada iteración. Y como no siempre le ahorra tanto cálculo en la detección de ciclos, evitaría hacerlo ya que también agrega una capa adicional de complejidad a la solución.

Comience por crear una lista de adyacencia a partir del conjunto de puntos. Puede hacer esto de manera eficiente en O (NlogN) si ordena los puntos por X e Y (por separado) e itera por los puntos en orden de X e Y. Luego, para encontrar la duración más corta del ciclo (determinada por el número de puntos), comience un BFS desde cada punto al arrojar inicialmente todos los puntos en la cola. A medida que atraviesa un borde, almacene la fuente de la ruta junto con el punto actual. Entonces sabrá cuándo el BFS vuelve a la fuente, en cuyo caso hemos encontrado un ciclo. Si termina con una cola vacía antes de encontrar un ciclo, entonces no existe ninguna. Tenga cuidado de no rastrear inmediatamente hacia el punto anterior o terminará con un ciclo difunto formado por dos puntos. También es posible que desee evitar, por ejemplo, un ciclo formado por los puntos (0, 0) , (0, 2) y (0, 1) ya que esto forma una línea recta.

El BFS tiene potencialmente el peor caso de ser exponencial, pero creo que tal caso puede probarse que no existe o ser extremadamente raro ya que cuanto más denso sea el gráfico, más rápido se encontrará un ciclo, mientras más escaso sea el gráfico menor será la cola estarán. En promedio, es más probable que esté más cerca del mismo tiempo de ejecución que la construcción de la lista de adyacencia, o en los peores casos realistas O (N ^ 2).





graph