Búsqueda RBFS para hallar la ruta de Oradea a Bucharest

La búsqueda en computación, es un tema muy estudiado, esto se debe a que las búsquedas son las funciones más usadas en los sistemas software de cualquier índole, más que otras operaciones como inserción, selección, actualización y eliminación. En el campo específicamente de Inteligencia Artificial, las búsquedas toman una connotación un poco diferente. El buscar datos implica buscar nuevas soluciones que en muchos casos no se tiene certeza si será encontrada. En el curso de IA tratamos, entre otras búsquedas, la búsqueda RBFS. Como referencia, el libro de Russell y Norving: "Artificial Intelligence A Modern Approach" contiene este tema, además de dicho libro sacamos un ejemplo, el cual lo resolvimos de manera gráfica para observar el comportamiento del RBFS.

Sea el mapa de ruta:

Y la tabla de heurística:

Primer paso:

El hijo con menor recorrido es Sibiu, y el siguiente hijo menor queda en memoria, en este caso Zerind con un valor de 445.

Segundo paso:

El nodo Sibiu se expande, sin imbargo, sus hijos presentan valores mayores que él. El algoritmo toma el nodo en memoria con el menor valor, no sin antes, guardar el menor valor de los hijos expandidos, en este caso Romnicu Vicea con un valor de 424, que queda en memoria, para luego expandir Zerind.

Tercer paso:

El hijo expandido de Zerind: Arad, presenta un valor mayor al de su padre, por tanto pasa al anterior que estaba en memoria, es decir 424 que correspondía a Rimnicu Vilcea, y en este ser verifica el hermano menor en memoria, es decir Fagaras con 426 y se procede a expandir los hijos de Rimnicu Vilcea.

Cuarto paso:

Los hijos de Rimnicu Vilcea son mayores que el padre, por tanto, se procede a llamar al nodo que quedo en memoria, es decir Fagaras, se guarda antes el menor valor de los hijos expandidos, en este caso con 428 el nodo Pitesti. Y se procede a expandir Fagaras.

Quinto paso:

Fagaras expande su hijo que casualmente llega a ser el nodo buscado: Bucarest, y entonces termina el algoritmo.