java - soluciones - ¿Cómo funciona una búsqueda de primer orden cuando se busca el camino más corto?

si p y q son numeros enteros encuentra las posibles soluciones para cada ecuacion

Question

Investigué un poco y parece que me falta una pequeña parte de este algoritmo. Entiendo cómo funciona una búsqueda de primer orden, pero no entiendo cómo exactamente me llevará a una ruta específica, en lugar de solo decirme a dónde puede ir cada nodo individual. Supongo que la manera más fácil de explicar mi confusión es proporcionar un ejemplo:

Entonces, por ejemplo, digamos que tengo un gráfico como este:

Y mi objetivo es llegar de A a E (todos los bordes no son ponderados).

Comienzo en A, porque ese es mi origen. Hizo una cola A, seguido de dequeueing inmediatamente A y explorándolo. Esto produce B y D, porque A está conectado a B y D. Por lo tanto, hago cola tanto B como D.

Dequeue B y lo exploro, y descubro que lleva a A (ya explorado), y C, entonces hago cola C. Luego dequeue D, y descubro que conduce a E, mi objetivo. Luego dequeue C, y descubro que también conduce a E, mi objetivo.

Sé lógicamente que el camino más rápido es A-> D-> E, pero no estoy seguro de cómo ayuda exactamente la búsqueda de amplitud: ¿cómo debería estar registrando rutas de modo que cuando termino pueda analizar los resultados y ver que el camino más corto es A-> D-> E?

Además, tenga en cuenta que en realidad no estoy usando un árbol, por lo que no hay nodos "principales", solo hijos.

Answer 1

Basado en la respuesta de acheron55, publiqué una posible implementación here .
Aquí hay un breve resumen de esto:

Todo lo que tienes que hacer es hacer un seguimiento de la ruta a través de la cual se ha alcanzado el objetivo. Una forma sencilla de hacerlo es insertar en la Queue toda la ruta utilizada para llegar a un nodo, en lugar de hacerlo en el nodo mismo.
El beneficio de hacerlo es que cuando se alcanza el objetivo, la cola conserva la ruta utilizada para alcanzarlo.
Esto también es aplicable a gráficos cíclicos, donde un nodo puede tener más de un padre.

Answer 2

Como se señaló anteriormente, BFS solo se puede usar para encontrar la ruta más corta en un gráfico si:

1. No hay bucles

2. Todos los bordes tienen el mismo peso o ningún peso.

Para encontrar la ruta más corta, todo lo que tiene que hacer es comenzar desde la fuente y realizar una primera búsqueda de amplitud y detenerse cuando encuentre su Nodo de destino. Lo único adicional que necesita hacer es tener una matriz anterior [n] que almacenará el nodo anterior para cada nodo visitado. La fuente anterior puede ser nula.

Para imprimir la ruta, bucle simple a través de la matriz [] anterior desde el origen hasta llegar a destino e imprimir los nodos. DFS también se puede usar para buscar la ruta más corta en un gráfico en condiciones similares.

Sin embargo, si el gráfico es más complejo, contiene bordes pesados ​​y bucles, entonces necesitamos una versión más sofisticada de BFS, es decir, el algoritmo de Dijkstra.

Answer 3

De tutorial aquí

"Tiene la propiedad extremadamente útil de que si todos los bordes de un gráfico no son ponderados (o tienen el mismo peso), entonces la primera vez que se visita un nodo es la ruta más corta hacia ese nodo desde el nodo de origen"

Answer 4

He perdido 3 días
finalmente resolvió una pregunta gráfica
usado para
encontrando la distancia mas corta
usando BFS

Quieres compartir la experiencia

When the (undirected for me) graph has
fixed distance (1, 6, etc.) for edges

#1
We can use BFS to find shortest path simply by traversing it
then, if required, multiply with fixed distance (1, 6, etc.)

#2
As noted above
with BFS
the very 1st time an adjacent node is reached, it is shortest path

#3
It does not matter what queue you use
   deque/queue(c++) or
   your own queue implementation (in c language)
   A circular queue is unnecessary

#4
Number of elements required for queue is N+1 at most, which I used
(dint check if N works)
here, N is V, number of vertices.

#5
Wikipedia BFS will work, and is sufficient.
    https://en.wikipedia.org/wiki/Breadth-first_search#Pseudocode

Perdí 3 días probando todas las alternativas anteriores, verificando y volviendo a verificar una y otra vez arriba
ellos no son el problema.
(Intente pasar el tiempo buscando otros problemas, si no encuentra ningún problema con el anterior 5).

Más explicación del comentario a continuación:

      A
     /  /
  B       C
 //       //
D  E     F  G

Asuma que arriba está su gráfica
el gráfico va hacia abajo
Para A, los adyacentes son B & C
Para B, los adyacentes son D y E
Para C, los adyacentes son F & G

decir, el nodo de inicio es A

1. cuando llegas a A, a, B y C, la distancia más corta a B y C de A es 1

2. cuando llegas a D o E, a B, la distancia más corta a A y D es 2 (A-> B-> D)

Del mismo modo, A-> E es 2 (A-> B-> E)

también, A-> F & A-> G es 2

Entonces, ahora, en lugar de 1 distancia entre nodos, si es 6, simplemente multiplique la respuesta por 6
ejemplo,
si la distancia entre cada uno es 1, entonces A-> E es 2 (A-> B-> E = 1 + 1)
si la distancia entre cada uno es 6, entonces A-> E es 12 (A-> B-> E = 6 + 6)

sí, bfs puede tomar cualquier camino
pero estamos calculando para todos los caminos

si tiene que pasar de A a Z, entonces viajamos todos los caminos desde A hasta un intermedio I, y dado que habrá muchos caminos, descartamos todos menos el camino más corto hasta I, luego continuamos con el camino más corto hacia el siguiente nodo J
de nuevo si hay múltiples rutas de I a J, solo tomamos el camino más corto
ejemplo,
asumir,
A -> I tenemos distancia 5
(STEP) supongamos que I -> J tenemos múltiples caminos, de distancias 7 y 8, ya que 7 es el más corto
tomamos A -> J como 5 (A-> I más corto) + 8 (más corto ahora) = 13
entonces A-> J tiene ahora 13
repetimos ahora arriba (PASO) para J -> K y así sucesivamente, hasta que lleguemos a Z

Lea esta parte, 2 o 3 veces, y dibuje en papel, seguramente obtendrá lo que estoy diciendo, la mejor de las suertes

Answer 5

La siguiente solución funciona para todos los casos de prueba.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

   public static void main(String[] args)
        {
            Scanner sc = new Scanner(System.in);

            int testCases = sc.nextInt();

            for (int i = 0; i < testCases; i++)
            {
                int totalNodes = sc.nextInt();
                int totalEdges = sc.nextInt();

                Map<Integer, List<Integer>> adjacencyList = new HashMap<Integer, List<Integer>>();

                for (int j = 0; j < totalEdges; j++)
                {
                    int src = sc.nextInt();
                    int dest = sc.nextInt();

                    if (adjacencyList.get(src) == null)
                    {
                        List<Integer> neighbours = new ArrayList<Integer>();
                        neighbours.add(dest);
                        adjacencyList.put(src, neighbours);
                    } else
                    {
                        List<Integer> neighbours = adjacencyList.get(src);
                        neighbours.add(dest);
                        adjacencyList.put(src, neighbours);
                    }


                    if (adjacencyList.get(dest) == null)
                    {
                        List<Integer> neighbours = new ArrayList<Integer>();
                        neighbours.add(src);
                        adjacencyList.put(dest, neighbours);
                    } else
                    {
                        List<Integer> neighbours = adjacencyList.get(dest);
                        neighbours.add(src);
                        adjacencyList.put(dest, neighbours);
                    }
                }

                int start = sc.nextInt();

                Queue<Integer> queue = new LinkedList<>();

                queue.add(start);

                int[] costs = new int[totalNodes + 1];

                Arrays.fill(costs, 0);

                costs[start] = 0;

                Map<String, Integer> visited = new HashMap<String, Integer>();

                while (!queue.isEmpty())
                {
                    int node = queue.remove();

                    if(visited.get(node +"") != null)
                    {
                        continue;
                    }

                    visited.put(node + "", 1);

                    int nodeCost = costs[node];

                    List<Integer> children = adjacencyList.get(node);

                    if (children != null)
                    {
                        for (Integer child : children)
                        {
                            int total = nodeCost + 6;
                            String key = child + "";

                            if (visited.get(key) == null)
                            {
                                queue.add(child);

                                if (costs[child] == 0)
                                {
                                    costs[child] = total;
                                } else if (costs[child] > total)
                                {
                                    costs[child] = total;
                                }
                            }
                        }
                    }
                }

                for (int k = 1; k <= totalNodes; k++)
                {
                    if (k == start)
                    {
                        continue;
                    }

                    System.out.print(costs[k] == 0 ? -1 : costs[k]);
                    System.out.print(" ");
                }
                System.out.println();
            }
        }
}

Answer 6

Técnicamente, la búsqueda en primer lugar (BFS) por sí sola no le permite encontrar la ruta más corta, simplemente porque BFS no busca una ruta más corta: BFS describe una estrategia para buscar un gráfico, pero no dice que deba buscar nada en particular.

El algoritmo de Dijkstra adapta BFS para permitirle encontrar rutas de acceso más cortas de una sola fuente.

Para recuperar la ruta más corta desde el origen hasta un nodo, necesita mantener dos elementos para cada nodo en el gráfico: su distancia más corta actual y el nodo anterior en la ruta más corta. Inicialmente, todas las distancias se establecen en infinito y todos los predecesores se configuran como vacíos. En su ejemplo, establece la distancia de A a cero y luego continúa con BFS. En cada paso verifica si puede mejorar la distancia de un descendiente, es decir, la distancia desde el origen al predecesor más la longitud del borde que está explorando es menor que la mejor distancia actual para el nodo en cuestión. Si puede mejorar la distancia, establezca la nueva ruta más corta y recuerde el predecesor a través del cual se adquirió esa ruta. Cuando la cola BFS está vacía, elija un nodo (en su ejemplo, es E) y recorra sus predecesores de regreso al origen. Esto te daría el camino más corto.

Si esto suena un poco confuso, wikipedia tiene una buena sección de pseudocódigo sobre el tema.