El Primero

El Primero Mejor (Best-First)

Este algoritmo, combina las ventajas de los algoritmos primero en profundidad y primero en amplitud. Sigue un sendero a la vez, pero puede cambiarse a otro senderoque parece más prometedor que el que está siguiendo.
En este sentido, puede considerarse que es un algoritmo que realiza su proceso de búsqueda en un grafo de tipo O, ya que todos sus ramalesrepresentan una alternativa de solución. Para su operación, el algoritmo necesita dos listas de nodos y una función heurística que estime los méritos de cada nodo que se genere:
1. ABIERTOS - Es una variableque contiene los nodos que han sido generados. La función heurística ha sido aplicada a ellos, pero todavía no han sido examinados, es decir no se han generado sus sucesores. ABIERTOS puedeconsiderarse como una COLA DE PRIORIDADES en la que los elementos con mayor prioridad son los que tienen los valores más prometedores, dados por la función heurística.
2. CERRADOS - Es una variable quecontiene los nodos que han sido examinados. Es necesario tener esta información, para que la búsqueda sea en un grafo y no en un árbol.
3. FUNCIÓN HEURÍSTICA - Permite que el algoritmo busque primero porsenderos que son o parecen más prometedores.
Para muchas aplicaciones, es conveniente definir esta función f', como la suma de dos, que se las llamará g y h'. La función g es una medida del costo dellegar desde el nodo inicial al nodo actual. La función h' es una estimación del costo adicional para llegar desde el nodo actual al estado objetivo. Aquí es donde se explota el conocimiento que sedispone sobre el dominio del problema.
Es decir, la función combinada f' representa una estimación del costo de llegar desde el estado inicial hasta el estado objetivo, siguiendo el sendero que hagenerado el nodo actual. Si el nodo actual ha generado más de un sendero, el algoritmo deberá dejar registrado sólo el mejor.
El algoritmo, en la forma que fue formulado, se aplica a grafos. Puede ser...