ClubEnsayos.com - Ensayos de Calidad, Tareas y Monografias
Buscar

Practica de algoritmos de busqueda


Enviado por   •  1 de Febrero de 2020  •  Tarea  •  1.851 Palabras (8 Páginas)  •  128 Visitas

Página 1 de 8

[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.

...

Descargar como (para miembros actualizados) txt (13 Kb) pdf (308 Kb) docx (237 Kb)
Leer 7 páginas más »
Disponible sólo en Clubensayos.com