search - sensibilidad - dibujar arbol binario
Búsqueda de gráficos vs búsqueda de árboles (5)
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 la búsqueda en árbol y la búsqueda de gráficos no está enraizada en el hecho de si su problema es un árbol o un gráfico. Siempre se supone que estás tratando con un gráfico. La distinción radica en el patrón transversal que se utiliza para buscar a través del gráfico, que puede ser en forma de gráfico o de árbol.
Si se trata de un problema en forma de árbol, ambas variantes de algoritmo conducen a resultados equivalentes. Para que pueda elegir la variante de búsqueda de árbol más simple.
Diferencia entre gráfico y búsqueda de árbol
Su algoritmo básico de búsqueda de gráficos se parece a lo siguiente. Con un comienzo de nodo de start , bordes dirigidos como successors y una especificación de goal utilizada en la condición de bucle. open contiene los nodos en memoria, que están actualmente bajo consideración, la lista abierta . Tenga en cuenta que el siguiente pseudo có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) (selección del elemento más nuevo), búsqueda de amplitud primera (BFS) (selección del elemento más antiguo) o búsqueda de costo uniforme (elemento de selección con costo de ruta más bajo), la popular búsqueda de estrellas A eligiendo el nodo con el costo más bajo más el valor heurístico , y así sucesivamente.
El algoritmo indicado anteriormente se llama realmente búsqueda de árbol . Visitará un estado del gráfico subyacente del problema varias veces, si hay múltiples rutas dirigidas a enrutar 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 ineficiencia aparente 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á varias veces el "subárbol" que se encuentra después de este estado, lo que puede ser costoso. La búsqueda de gráficos corrige esto haciendo un seguimiento de todos los estados visitados en una lista cerrada . Si ya se conoce un sucesor recién encontrado para el next , 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
Observamos 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 resulta en una mejor eficiencia de búsqueda.
Soluciones óptimas
Algunos métodos de implementación select pueden 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 asociados a los bordes). Básicamente, esto se mantiene cada vez que los nodos se expanden en orden creciente de costo 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 pasos son idénticos, BFS o IDDFS . IDDFS evita el consumo agresivo de memoria de BFS y generalmente se recomienda para búsquedas no informadas (también conocidas como fuerza bruta) cuando el tamaño del paso es constante.
A*
Además, el algoritmo de búsqueda de árboles A * (muy popular) 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 hace esta garantía cuando se usa con una heurística consistente (o "monotónica") (una condición más fuerte que la admisibilidad).
(2) Errores de pseudo-código
Para simplificar, el código presentado no:
- manejar búsquedas fallidas, es decir, solo funciona si se puede encontrar una solución
¿Cuál es la diferencia básica entre la búsqueda de gráficos y las versiones de búsqueda en árbol con respecto a DFS, A * búsquedas en inteligencia artificial ?
En palabras simples, el árbol no contiene ciclos y donde el gráfico puede hacerlo. Entonces cuando buscamos, debemos evitar ciclos en gráficos para no entrar en bucles infinitos.
Otro aspecto es que tree 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 sencilla en comparación con los gráficos.
La única diferencia entre un gráfico y un árbol es ciclo . Un gráfico puede contener ciclos, un árbol no puede. Entonces, cuando va 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 eventualmente puede caer en un ciclo infinito o una recursión sin fin.
Otro punto para pensar son las propiedades direccionales del gráfico con el que estás tratando. En la mayoría de los casos tratamos con árboles que representan 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.
Un árbol es un caso especial de un gráfico, por lo que todo lo que funciona para los gráficos generales funciona para los á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 previa, 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 un algoritmo de búsqueda más eficiente que para un gráfico sin restricciones. Por ejemplo, probablemente no tenga mucho sentido utilizar A *, o su homólogo no heurístico, el "algoritmo de Dijkstra", en un árbol (donde solo hay una ruta para elegir, que puede encontrar por DFS o BFS) o en un DAG (donde se puede encontrar un camino óptimo considerando vértices en el orden obtenido por clasificación topológica).
En cuanto a dirigido vs no dirigido, un gráfico no dirigido es un caso especial de uno dirigido, es decir, el caso que sigue a 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. Ver, por ejemplo, la respuesta de @ ziggystar.
GRÁFICO CONTRA Á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, siempre que el algoritmo explore un nuevo nodo y lo marque como visitado, independientemente del algoritmo utilizado, el algoritmo generalmente explora todos los otros nodos que se pueden alcanzar desde el nodo actual.
Por ejemplo, considere el siguiente gráfico con 3 vértices AB y C, y considere los siguientes los bordes
AB, BC y CA. Bueno, hay un ciclo de C a A,
Y cuando DFS a partir de A, A generará un nuevo estado B, B generará un nuevo estado C, pero cuando se explora C, el algoritmo intentará generar un nuevo estado A, pero A ya ha sido visitado, por lo que será ignorado. ¡Guay!
Pero, ¿y los árboles? el algoritmo de árboles de pozo no marca el nodo visitado como visitado, pero los árboles no tienen ciclos, ¿cómo se obtendría en un bucle infinito?
Considera este árbol con 3 vértices y considera los siguientes bordes
A - B - C arraigado 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 Trees no tiene "Marcar un nodo visitado si se explora", por lo que tal vez el algoritmo DFS explorará A de nuevo, generando así un nuevo estado B, por lo tanto nos estamos metiendo en un bucle infinito.
Pero si 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.
ST A-> B-> A-> B-> A no es un ciclo porque viola la propiedad de ciclismo> = 3. Pero de hecho A-> B-> C-> A es un ciclo> = 3 nodos distintos Controlados, el primer y el último nodo son los mismos marcados.
Consideremos nuevamente los bordes del árbol, A-> B-> C-> B-> A, por supuesto, 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.