busqueda costo uniforme

INSTITUTO TECNOLOGICO






Ingeniería en sistemas computacionales

Inteligencia Artificial Unidad 4

Tarea 2


Alumno: Rubén De La Cruz Venegas
No. Control 09110964


Profesor:Trejo Ramírez Francisco2/12/13
Búsqueda del costo uniforme
Este tipo de algoritmos suelen usarse en problemas donde el objetivo es encontrar un camino que minimice o maximice alguna propiedad del sistema estudiado. Paraque puedan aplicarse el sistema debe poder modelarse mediante un árbol o un grafo ponderado, de forma que la magnitud de la propiedad estudiada sea función de los nodos recorridos.
Un ejemplo de estetipo es el mostrado en la figura 1. Supongamos que se quiere determinar el camino que permite llegar desde el nodo 1 al 6 minimizando el  atributo "valor". Este atributo se incrementa en la cantidadindicada por la etiqueta de cada arista, por lo que en función del camino seguido para llegar hasta el nodo 6 determina su valor. 

Para solucionar este problema se puede usar un algoritmo de búsquedauniforme. Para ello se necesitarán como poco las siguientes estructuras de datos:
1. Una clase nodo con un atributo que sea una referencia al nodo "progenitor".
2. Una colección de nodos aun novisitados , o de nodos visitados (visitados), según el enfoque.
3. Una lista de nodos (por_visitar) ordenada de mejor a peor opción según su aporte a la propiedad a optimizar. Si se quiere minimizarestarán primero los que produzcan un menor incremento.En el siguiente esquema muestran
los pasos básicos que siguen este tipo de algoritmos.








Si se aplica este algoritmo para llegar alnodo 6 de la figura con el menor valor posible se obtiene lo siguiente:

1. Se comprueba si nodo 1 es solución, como no lo es se obtienen los hijos que aún no han sido visitados (nodos 2,3 y 6)...