¿Cuál es la diferencia entre la búsqueda de gráficos y las versiones de búsqueda de árbol con respecto a las búsquedas DFS, A * en inteligencia artificial ?

A juzgar por las respuestas existentes, parece haber mucha confusión sobre este concepto.

El problema es siempre un gráfico

La distinción entre búsqueda de árbol y búsqueda de gráfico no se basa en el hecho de que el gráfico del problema sea un árbol o un gráfico general. Siempre se asume que se trata de un gráfico general. La distinción radica en el patrón transversal que se utiliza para buscar en el gráfico, que puede tener forma de gráfico o de árbol.

Si se trata de un problema en forma de árbol , ambas variantes del algoritmo conducen a resultados equivalentes. Para que pueda elegir la variante de búsqueda de árbol más simple.

Diferencia entre la búsqueda de gráficos y árboles

Su algoritmo básico de búsqueda de gráficos se parece a lo siguiente. Con un nodo de inicio start, bordes dirigidos como successorsy una goalespecificación utilizada en la condición de bucle. opencontiene los nodos en la memoria, que están actualmente bajo consideración, la lista abierta . Tenga en cuenta que el siguiente pseudocódigo no es correcto en todos los aspectos (2).

Búsqueda de árbol

open <- []
next <- start

while next is not goal {
    add all successors of next to open
    next <- select one node from open
    remove next from open
}

return next

Dependiendo de cómo implemente select from open, obtendrá diferentes variantes de algoritmos de búsqueda, como búsqueda en profundidad (DFS) (elija el elemento más nuevo), búsqueda primero en amplitud (BFS) (elija el elemento más antiguo) o búsqueda de costo uniforme (elija el elemento con el costo de ruta más bajo) ), la popular búsqueda A-star eligiendo el nodo con menor costo más valor heurístico , y así sucesivamente.

El algoritmo mencionado anteriormente en realidad se llama búsqueda de árbol . Visitará un estado del gráfico del problema subyacente varias veces, si hay varias rutas dirigidas a él enraizándose en el estado de inicio. Incluso es posible visitar un estado un número infinito de veces si se encuentra en un bucle dirigido. Pero cada visita corresponde a un nodo diferente en el árbol generado por nuestro algoritmo de búsqueda. Esta aparente ineficacia a veces se desea, como se explica más adelante.

Búsqueda gráfica

Como vimos, la búsqueda de árboles puede visitar un estado varias veces. Y como tal, explorará el "subárbol" que se encuentra después de este estado varias veces, lo que puede resultar caro. La búsqueda de gráficos corrige esto al realizar un seguimiento de todos los estados visitados en una lista cerrada . Si nextya se conoce un sucesor recién encontrado , no se insertará en la lista abierta:

open <- []
closed <- []
next <- start

while next is not goal {
    add next to closed
    add all successors of next to open, which are not in closed 
    remove next from open
    next <- select from open
}

return next

Comparación

Notamos que la búsqueda de gráficos requiere más memoria, ya que realiza un seguimiento de todos los estados visitados. Esto puede compensarse con la lista abierta más pequeña, lo que da como resultado una mayor eficiencia de búsqueda.

Soluciones óptimas

Algunos métodos de implementación selectpueden garantizar el retorno de soluciones óptimas, es decir, una ruta más corta o una ruta con un costo mínimo (para gráficos con costos adjuntos). Esto básicamente se mantiene siempre que los nodos se expanden en orden de costo creciente, o cuando el costo es una constante positiva distinta de cero. Un algoritmo común que implementa este tipo de selección es la búsqueda de costos uniformes , o si los costos de paso son idénticos, BFS o IDDFS . IDDFS evita el consumo agresivo de memoria de BFS y generalmente se recomienda para búsquedas desinformadas (también conocidas como fuerza bruta) cuando el tamaño del paso es constante.

UNA*

Además, el (muy popular) algoritmo de búsqueda de árbol A * ofrece una solución óptima cuando se utiliza con una heurística admisible . El algoritmo de búsqueda de gráficos A * , sin embargo, solo ofrece esta garantía cuando se usa con una heurística consistente (o "monótona") (una condición más fuerte que la admisibilidad).

(2) Defectos del pseudocódigo

Por simplicidad, el código presentado no:

• manejar búsquedas fallidas, es decir, solo funciona si se puede encontrar una solución

Un árbol es un caso especial de un gráfico, por lo que cualquier cosa que funcione para gráficos generales funciona para árboles. Un árbol es un gráfico donde hay precisamente una ruta entre cada par de nodos. Esto implica que no contiene ningún ciclo, como dice una respuesta anterior, pero un gráfico dirigido sin ciclos (un DAG, gráfico acíclico dirigido) no es necesariamente un árbol.

Sin embargo, si sabe que su gráfico tiene algunas restricciones, por ejemplo, que es un árbol o un DAG, generalmente puede encontrar algún algoritmo de búsqueda más eficiente que para un gráfico sin restricciones. Por ejemplo, probablemente no tenga mucho sentido usar A *, o su contraparte no heurística, el "algoritmo de Dijkstra", en un árbol (donde solo hay una ruta para elegir de todos modos, que puede encontrar por DFS o BFS) o en un DAG (donde se puede encontrar una ruta óptima considerando los vértices en el orden obtenido por clasificación topológica).

En cuanto a dirigido vs no dirigido, un grafo no dirigido es un caso especial de uno dirigido, es decir, el caso que sigue la regla “si hay un borde (enlace, transición) de u a v, también hay un borde de v a u .

Actualización : tenga en cuenta que si lo que le importa es el patrón transversal de la búsqueda en lugar de la estructura del gráfico en sí, esta no es la respuesta. Vea, por ejemplo, la respuesta de @ ziggystar.

La única diferencia entre un gráfico y un árbol es el ciclo . Un gráfico puede contener ciclos, un árbol no. Entonces, cuando vaya a implementar un algoritmo de búsqueda en un árbol, no necesita considerar la existencia de ciclos, pero cuando trabaje con un gráfico arbitrario, deberá considerarlos. Si no maneja los ciclos, el algoritmo puede eventualmente caer en un bucle infinito o una recursividad sin fin.

Otro punto para pensar son las propiedades direccionales del gráfico con el que está tratando. En la mayoría de los casos, tratamos con árboles que representan las relaciones entre padres e hijos en cada borde. Un DAG (gráfico acíclico dirigido) también muestra características similares. Pero los gráficos bidireccionales son diferentes. Cada borde en un gráfico bidireccional representa dos vecinos. Entonces, los enfoques algorítmicos deberían diferir un poco para estos dos tipos de gráficos.

GRÁFICO VS ÁRBOL

• Los gráficos tienen ciclos
• Los árboles no tienen ciclos "Por ejemplo, imagina cualquier árbol en tu cabeza, las ramas no tienen conexiones directas con la raíz, pero las ramas tienen conexiones con otras ramas, hacia arriba"

Pero en el caso de AI Graph-search vs Tree-search

La búsqueda de gráficos tiene una buena propiedad que es cuando el algoritmo explora un nuevo nodo y lo marca como visitado, "Independientemente del algoritmo utilizado", el algoritmo normalmente explora todos los demás nodos que son accesibles desde el nodo actual.

Por ejemplo, considere la siguiente gráfica con 3 vértices AB y C, y considere las siguientes aristas

AB, BC y CA, bueno, hay un ciclo de C a A,

Y cuando DFS comience desde A, A generará un nuevo estado B, B generará un nuevo estado C, pero cuando se explore C, el algoritmo intentará generar un nuevo estado A, pero A ya está visitado, por lo que se ignorará. ¡Frio!

Pero ¿y los árboles? Bueno, el algoritmo de los árboles no marca el nodo visitado como visitado, pero los árboles no tienen ciclos, ¿cómo entraría en bucles infinitos?

Considere este árbol con 3 vértices y considere los siguientes bordes

A - B - C arraigada en A, hacia abajo. Y supongamos que estamos usando el algoritmo DFS

A generará un nuevo estado B, B generará dos estados A y C, porque los árboles no tienen "Marcar un nodo visitado si se explora", por lo que tal vez el algoritmo DFS explorará A nuevamente, generando así un nuevo estado B, por lo tanto estamos entrando en un bucle infinito.

Pero, ¿ha notado algo? Estamos trabajando en bordes no dirigidos, es decir, hay una conexión entre AB y BA. por supuesto, esto no es un ciclo, porque el ciclo implica que los vértices deben ser> = 3 y todos los vértices son distintos excepto el primero y el último nodos.

ST A-> B-> A-> B-> A no es un ciclo porque viola la propiedad del ciclo> = 3. Pero de hecho A-> B-> C-> A es un ciclo> = 3 nodos distintos Marcados, el primer y el último nodo son iguales. Comprobado.

Considere nuevamente los bordes del árbol, A-> B-> C-> B-> A, por supuesto que no es un ciclo, porque hay dos B, lo que significa que no todos los nodos son distintos.

Por último, podría implementar un algoritmo de búsqueda de árbol para evitar explorar el mismo nodo dos veces. Pero eso tiene consecuencias.

En palabras simples, el árbol no contiene ciclos y, como gráfico, sí. Entonces, cuando buscamos, debemos evitar los ciclos en los gráficos para no entrar en bucles infinitos.

Otro aspecto es que el árbol normalmente tendrá algún tipo de clasificación topológica o una propiedad como el árbol de búsqueda binaria que hace que la búsqueda sea tan rápida y fácil en comparación con los gráficos.