algorithm - tentativas - Criterios de terminación para la búsqueda bidireccional

recorrido en anchura de un grafo java

Question

Según la mayoría de las lecturas que he hecho, se dice que un algoritmo de búsqueda bidireccional termina cuando las fronteras "hacia adelante" y "hacia atrás" se cruzan por primera vez. Sin embargo, en la Sección 3.4.6 de Inteligencia Artificial: Un enfoque moderno , Russel y Norvig afirman:

La búsqueda bidireccional se implementa al reemplazar la prueba de metas con una verificación para ver si las fronteras de las dos búsquedas se cruzan; Si lo hacen, se ha encontrado una solución. Es importante darse cuenta de que la primera solución encontrada puede no ser óptima, incluso si las dos búsquedas son las dos primeras; se requiere alguna búsqueda adicional para asegurarse de que no haya un atajo a través del espacio.

He considerado esta afirmación durante bastante tiempo, pero no puedo encontrar un ejemplo de este comportamiento. ¿Alguien puede proporcionar un gráfico de ejemplo donde la primera intersección entre las fronteras hacia adelante y hacia atrás de una búsqueda bidireccional BFS o A * no sea la ruta más corta?

Edición: es evidente que BFS no encontrará la ruta más corta en un gráfico ponderado. Parece que este extracto se refiere a BFS bidireccional en un gráfico no dirigido. Alternativamente, me interesaría ver un contraejemplo utilizando A * bidireccional en un gráfico ponderado.

Answer 1

Creo que tiene que ver con cómo se implementa la búsqueda bidireccional.

El pseudocódigo para BFS es algo así:

until frontier.empty?
    node <- frontier.pop()
    add node to explored
    for each child not in expored or frontier:
        if child is goal then
            return path
        add child to frontier

Imagina implementar una búsqueda bidireccional como esta:

until frontierForward.emtpy? or frontierBackward.empty?
    node <- frontierForward.pop()
    add node to exploredForward
    for each child not in exporedForward or frontierForward:
        if child in frontierBackward then
            return pathForward + pathBackward
        add child to frontierForward

    Do something similar but now searching backwards

Básicamente, pasos alternos de BFS "hacia adelante" y BFS "hacia atrás". Ahora imagina una gráfica como esta:

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

Las primeras ejecuciones hacia adelante y hacia atrás de BFS nos darían un estado como este:

1) expandedForward = A ; frontierForward = B, F
2) expandedBackward = E ; frontierBackward = D, G

Ahora el algoritmo selecciona el siguiente nodo para expandirse desde la frontera delantera y elige B.

3) expandedForward = A, B ; frontierForward = F, C

Ahora ejecutamos un BFS hacia atrás y expandimos el nodo D. El hijo de D, C, está en la frontera delantera, por lo que devolvemos el camino A - B - C - D - E.

Creo que esto es a lo que Russel y Norvig se referían. Si la implementación no considera este escenario, podría darle una solución que no es óptima.

Debe terminar de expandir todos los nodos en la frontera que tienen la misma "profundidad" antes de decidir que ha encontrado una solución óptima. O tal vez alterne las búsquedas BFS hacia adelante y hacia atrás por capa y no por nodo (expanda hacia adelante todos los nodos en la capa 0, expanda hacia atrás todos los nodos en la capa 0, expanda hacia adelante todos los nodos en la capa 1, etc.)

Answer 2

En un gráfico sin ponderar (costo unitario), BFS bidireccional ha encontrado la solución óptima cuando llega a la intersección, como lo indican Russell & Norvig en la página 80 de la edición de 2003 de "AIMA":

La búsqueda bidireccional se implementa haciendo que una o ambas búsquedas verifiquen cada nodo antes de expandirlo para ver si está en el borde del otro árbol de búsqueda. El algoritmo está completo y es óptimo (para costos de paso uniformes) si ambas búsquedas son primero en amplitud [.]

(Al "expandir un nodo", R&N significa generar los sucesores. Se agregó énfasis).

Answer 3

No sé si esto era lo que Russel y Norvig tenían en mente, pero si la gráfica está ponderada (es decir, algunos bordes son más largos que otros), la ruta más corta podría tener más pasos que otra que se encontraría antes en un BFS. Incluso si el número de pasos es el mismo, el mejor podría no encontrarse primero; Considera una gráfica con seis nodos:

(A-> B) = (A-> C) = 0

(B-> D) = 2

(C-> E) = 1

(D-> F) = (E-> F) = 0

Después de un paso adelante de A y un paso atrás de F, la frontera delantera es {B, C} y la frontera posterior es {D, E}. El buscador ahora expande B y hey! ¡intersección! (A-> B-> D-> F) = 2. Pero aún debe buscar un poco más para descubrir que (A-> C-> E-> F) es mejor.

Answer 4

un triángulo simple satisfaría su condición, con los lados 6,6,10 con la ruta óptima que atraviesa el segmento de longitud 10. En Bidireccional, el algoritmo busca la ruta más corta hacia adelante, luego la marcha atrás también tomaría la ruta más corta , se encontrarían, se encuentra un camino completo.

pero claramente 2 segmentos de 6 + 6 es peor que un segmento de longitud 10.