“EL TURISTA VIRTUAL” Algoritmo de búsqueda en grafos

MODELOS DE
LA 
INTELIGENCIA
ARTIFICIAL
“EL TURISTA VIRTUAL”



Introducción al tipo de método empleado
La práctica consiste en la búsqueda de un camino mínimo (óptimo) en un grafo. Esto es difícilmente abordable ya que conllevaría un consumo computacional elevado. 
Solucionar   este   problema   es   factible   introduciendo   una   heurística   para conseguir una aproximación al problema en un tiempo y con un resultado razonable. 
Ahora   el   óptimo   lo   entenderíamos   como   la   mejor   relación   de   la   menor distancia del camino, entre dos cruces  y el menor numero de nodos explorados para 
encontrar este camino seria la solución. 
Al estar hablando de búsqueda en grafos se plantean varios problemas a 
solucionar:
1.Como controlamos el consumo de memoria para almacenar la información 
referente al grafo.
2. La forma de recorrer este grafo. 
3. Criterios elegir para realizar la exploración encontrando un camino solución.Ante estos problemas he optado por implementar un método de escalada, pero 
con algunas modificaciones para conseguir mejores resultados y aliviar las 
deficiencias de éste.
El método explora los nodos primero en profundidad, de una forma retroactiva que ayuda a evitar ciclos en la búsqueda de un camino y asegura encontrar una 
solución, también se ha modificado la forma en la que se eligen los hijos que se van a expandir  de un nodo padre dado. Así conseguiremos que los nodos en teoría con 
mejor valoración heurística, sean los primeros en expandirse con la consecuente 
disminución del espacio de búsqueda y en su tiempo de ejecución.Realizamos  una exploración en profundidad almacenando solo el camino 
recorrido, que representa a la solución parcial obtenida del problema, sin necesidad 
de mantener todo el grafo en memoria.Especificación del método
Esta implementado sobre el esqueleto: 
 Escalada_recursivo(lista_solución, parámetros_búsqueda, bool solucionado)
{
if ( !solucionado)
{...