Algoritmos de Búsqueda en Inteligencia Artificial: Best-First, Breadth-First, Depth-First y A*
Clasificado en Informática
Escrito el en 
español con un tamaño de 3,3 KB
Algoritmos de Búsqueda en Inteligencia Artificial
A continuación, se describen algunos algoritmos de búsqueda fundamentales en el campo de la Inteligencia Artificial.
Best-First
En el algoritmo Best-First, el nodo que recibe la mejor evaluación se expande primero. Se expande el nodo que parece ser el mejor de acuerdo con la función de evaluación. Para esto, se toman en cuenta todos los nodos que se han visto hasta el momento.
Breadth-First (Amplitud)
Se evalúa cada nodo en un determinado nivel antes de pasar al siguiente. Es completo y óptimo, buscando la solución más corta.
Cómo trabaja: Busca en el gráfico entero o la secuencia sin considerar el objetivo hasta que lo encuentra. No usa una heurística. Desde el punto de vista del algoritmo, todos los nodos hijos obtenidos por ampliar un nodo, son añadidos a una cola FIFO.
Depth-First (Profundidad)
Algoritmo que permite recorrer recursivamente todos los nodos de un grafo o árbol de manera ordenada, pero no uniforme. Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de forma recurrente, en un camino concreto. Cuando ya no quedan más nodos, regresa, de modo que repite el mismo proceso con cada rama del nodo ya procesado.
ABIERTOS := [INICIAL]; CERRADOS := []; f'(INICIAL) := h'(INICIAL)
repetir
si ABIERTOS = [] entonces FALLO
si no // quedan nodos
extraer MEJORNODO de ABIERTOS con f' mínima
// cola de prioridad
mover MEJORNODO de ABIERTOS a CERRADOS
si MEJORNODO contiene estado_objetivo entonces
SOLUCION_ENCONTRADA := TRUE
si no
generar SUCESORES de MEJORNODO
para cada SUCESOR hacer TRATAR_SUCESOR
hasta SOLUCION_ENCONTRADA o FALLO
A*
El algoritmo A* tiene en cuenta el valor heurístico de los nodos y el coste real del recorrido. Este algoritmo utiliza una función de evaluación f(n) = g(n) + h(n), donde h(n) es el valor heurístico del nodo a evaluar desde el actual, n, hasta el final, y g(n) es el coste real del camino recorrido para llegar a dicho nodo, n. A* mantiene dos estructuras de datos auxiliares, que podemos denominar abiertos, poniendo como una cola de prioridad, y cerrados, donde se guarda la información de los nodos que han sido visitados. El algoritmo es una combinación entre búsquedas del tipo primero en anchura con primero en profundidad: mientras que h'(n) tiende primero en profundidad, g(n) va primero en anchura. De este modo, se cambia de camino de búsqueda cada vez que existen nodos más convenientes.
Este algoritmo es un algoritmo completo; en caso de haber una solución, dará con ella. Para garantizar que este algoritmo es óptimo, la función h(n) debe ser admisible. De no cumplir esto, el algoritmo se llamaría A y no aseguraría que el resultado obtenido sea el camino de coste mínimo.
El pseudocódigo será: