Búsqueda "primero el mejor"
PREGUNTA:
Tengo una duda respecto al método "Primero el Mejor" (PM). Segun se dice en
el libro este método no considera el coste del camino recorrido para llegar
a un nodo, sino que se le asigna a cada nodo un coste estimativo de la
distancia hasta la meta.
Segun lo entiendo yo, este valor se establecera en base a unos criterios que
nada tendran que ver con el camino recorrido para llegar al nodo en
cuestion, sino con el camino estimado que falta por llegar a la meta. Por lo
tanto, una vez fijado su valor, este no deberia variar, o por lo menos no
hacerlo en funcion del camino recorrido para llegar al nodo, ya que si asi
se hiciera se estaria aplicando el algoritmo A*.
Entonces no entiendo porque, al describir el algoritmo PM, se incluyen los
pasos (3.4) y (3.5). La reorientacion de los punteros no tiene sentido en el
método PM puesto que no se considera el camino recorrido. Es decir, si en
algun momento se genera un nodo que ya habia sido generado en un paso
anterior (esta en ABIERTA o CERRADA), simplemente se ignora (ya que si
estaba en CERRADA ya se han generado todos sus sucesores, y si estaba en
ABIERTA ya le llegara el turno cuando el valor de su funcion heuristica sea
el menor de la lista ABIERTA).
RESPUESTA:
Efectivamente, el "método primero el mejor" usa una función de evaluación
heurística que no tiene en cuenta, para cada nodo N, el coste del camino
óptimo actual desde el nodo raíz hasta el nodo N. No obstante, es necesario
seguir gestionando el árbol parcial de costes mínimos de cara a disponer en
todo momento del camino óptimo actual desde N hasta el nodo raíz. De este
modo, al generar un nodo meta, siguiendo los arcos ascendentes de dicho
árbol podremos trazar el mejor camino encontrado hasta el momento del nodo
raíz al nodo meta. Además, tenga en cuenta que el "método primero el mejor"
no es más que un caso particular de la "búsqueda general en grafos", donde
sí se gestiona el árbol parcial de costes mínimos.