Practica de algoritmos de busqueda
Enviado por Daniel callejo • 1 de Febrero de 2020 • Tarea • 1.851 Palabras (8 Páginas) • 127 Visitas
[pic 1][pic 2]
Formulación de estados: Problema 1
En esta sección vamos a describir el espacio de estados que tenemos gracias el enunciado del problema:
- Estado inicial: Ávila
- Estado final: León
- Posibles estados: Salamanca, Zamora, Valladolid, Segovia, Soria, Burgos, Palencia
- Coste en minutos de capital a capital por Google Maps:
- Ávila🡪Valladolid=89 min
- Ávila🡪Segovia=55 min
- Ávila🡪Salamanca=68 min
- Segovia🡪Ávila=52 min
- Segovia🡪Soria=136 min
- Segovia🡪Burgos=125 min
- Segovia🡪Valladolid=81 min
- Soria🡪Segovia=140 min
- Soria🡪Burgos=103 min
- Burgos🡪Soria=106 min
- Burgos🡪Segovia=125 min
- Burgos🡪Valladolid=80 min
- Burgos🡪Palencia=58 min
- Palencia🡪Burgos=59 min
- Palencia🡪Valladolid=40 min
- Palencia🡪León=93 min
- Valladolid🡪Ávila=91 min
- Valladolid🡪Segovia=79 min
- Valladolid🡪Burgos=82 min
- Valladolid🡪Palencia=44 min
- Valladolid🡪León=109 min
- Valladolid🡪Zamora=74 min
- Valladolid🡪Salamanca=78 min
- León🡪Palencia=95 min
- León🡪Valladolid=110 min
- León🡪Zamora=93 min
- Zamora🡪León=91 min
- Zamora🡪 Valladolid=70 min
- Zamora🡪Salamanca=52 min
- Salamanca🡪Zamora=49 min
- Salamanca🡪Valladolid=77 min
- Salamanca🡪Ávila=66 min
La flecha es para indicar la función sucesor, es decir, de la cual puedes ir del punto A al punto B.
- Test objetivo: nuestro objetivo es, partiendo del estado inicial, alcanzar el estado final encontrando el camino más corto.
Resultado de aplicar los algoritmos de búsqueda.
En esta sección daremos los resultados de los distintos algoritmos de búsqueda utilizados para alcanzar nuestro objetivo.
Algoritmos implementados con el Software “Search Applet”:
Aquí están las soluciones de los algoritmos que hemos podido implementar utilizando el Software: “Search Applet”.
Primero en Profundidad
El algoritmo de búsqueda nunca llega a alcanzar nuestra función objetivo, debido a que entra en bucle. Este problema surge del coste entre los distintos caminos, ya que siempre escoge el camino que menos coste le lleva, entrando en un bucle infinito.
Primero en Anchura
El algoritmo de búsqueda llega a nuestra función objetivo tras 9 pasos y con un coste de 198 minutos. Aunque llegamos a nuestro objetivo, el coste en nodos no es el más óptimo, ya que, existe la posibilidad de pasar varias veces por la misma ciudad.
La solución es:
Ávila🡪Valladolid🡪León, son 9 nodos y un coste de 198 minutos
Menor coste primero
El algoritmo de búsqueda llega a nuestra función objetivo tras 28 pasos y con un coste de 198 minutos. Este algoritmo obtiene el resultado en minutos más óptimo pero tiene un coste alto en nodos para llegar al resultado
Solución:
Ávila🡪Valladolid🡪León, son 28 nodos y un coste de 198 minutos
Primero Mejor
El algoritmo de búsqueda llega a nuestra función objetivo tras 3 pasos y con un coste de 198 minutos. Este algoritmo, en nuestro caso, nos da la solución óptima, aunque podría darse el caso de que no fuera así. Por lo que podemos concluir que la heurística utilizada es buena, ya que nos lleva a alcanzar la solución óptima.
Solución:
Ávila🡪Valladolid🡪León, son 3 nodos y un coste de 198 minutos
Voraz Primero Mejor
El algoritmo de búsqueda llega a nuestra función objetivo tras 3 pasos y con un coste de 198 minutos. Nos lleva a alcanzar la solución óptima.
Solución:
Ávila🡪Valladolid🡪León, son 3 nodos y un coste de 198 minutos
A*
El algoritmo de búsqueda llega a nuestra función objetivo tras 3 pasos y con un coste de 198 minutos. Con este algoritmo alcanzamos también la solución óptima gracias a la heurística utilizada.
Solución:
Ávila🡪Valladolid🡪León, son 3 nodos y un coste de 198 minutos
Algoritmos implementados sin el Software “Search Applet”:
Aquí están las soluciones de los algoritmos que hemos implementado a través del papel.
Profundidad limitada
Este algoritmo de búsqueda cuenta con un limite que sirve de tope para limitar el nivel en el que busca la solución a través de la altura del árbol.
...