Timisoara

Problema de las ciudades: Desde Timisoara a Urziceni.

Búsqueda primero en Anchura.

Se podría llegar a una solución buscando en anchura. Desde Timisoara creamos el árbol.

1. En primer lugarse comprueba si el destino es Timisoara, como no lo es, los siguientes nodos a comprobar son Arad y Lugoj.
2. Tampoco es una solución así que comprobamos el siguiente nivel: Timisoara, Zerind,Sibiu y Mehadia.
3. Tampoco encontramos una solución, comprobamos el siguiente nivel: Arad, Oradea, Rimnicu, Fagaras, Dobreta y Lugoj.
4. Tampoco encontramos una solución, comprobamos el siguientenivel: Zerind, Sibiu, Sibiu, Craiova, Pitesti, Sibiu, Bucharest, Mehadia, Craiova.
5. Tampoco encontramos una solución, comprobamos el siguiente nivel: Bucharest, Bucharest, Fagaras, Pitesti, Giurgiu yUrziceni
6. Encontramos la solución Urziceni.

Búsqueda primero en profundidad.

No podríamos llegar a una solución usando la búsqueda en profundidad, el motivo es que el árbol es infinito alno tener restricciones al generarlo.

Búsqueda de profundidad limitada.

Para solucionar el problema de tener un árbol ilimitado usamos un limite de profundidad, podemos suponer que el limite sea20 (número de ciudades que tenemos) o 9 (número de pasos para alcanzar cualquier ciudad). Lo mejor es poner 9. El algoritmo buscara en la rama izquierda de cada nodo hasta un limite de profundidad9, luego buscara en la rama derecha hasta profundidad 9. El algoritmo no es muy eficiente y para eso mejor usar profundidad iterativa.




Búsqueda de profundidad iterativa.

Aumentamosgradualmente el limite de profundidad hasta que encontremos el objeto que buscamos. En nuestro ejemplo alcanzaremos un limite de profundidad de 6. Primero se buscara en el primer nivel, al no encontrar elobjeto se incrementara el limite de profundidad y buscaremos en el segundo nivel, al no encontrar el objeto se incrementara el limite de profundidad a 3 y así sucesivamente hasta el nivel 6 donde...