Algoritmo A Astericos Inteligencia Artificial

INTELIGENCIA ARTIFICIAL
¨ EJERCICIO BUSQUEDA A ASTERISCO ¨
Ing. Mg. Ing Mg BRUNO ELIO VARGAS TAMANI

BUSQUEDA A ASTERISCO

Consideremos el mapa C id l de Rumania que Rumania, indica las rutasentre las ciudades mencionadas. mencionadas Además se muestra las distancias entre ciudades adyacentes adyacentes.
05/03/2012 Ing. M.Sc. BRUNO VARGAS T. 2

BUSQUEDA A ASTERISCO

05/03/2012Ing. M.Sc. BRUNO VARGAS T.

3

BUSQUEDA A ASTERISCO FUNCION HEURISTICA h(n) h( )

Se utiliza como función heurística h(n), a la distancia en línea recta de todas las ciudades a la ciudad deBucharest Bucharest. q Si deseamos ir de la cualquier ciudad a la Bucharest, la siguiente t bl muestra h( ) i i t tabla t h(n).
05/03/2012 Ing. M.Sc. BRUNO VARGAS T. 4

FUNCION HEURISTICA h(n)05/03/2012

Ing. M.Sc. BRUNO VARGAS T.

5

FUNCION HEURISTICA h(n)

05/03/2012

Ing. M.Sc. BRUNO VARGAS T.

6

CIUDAD

DISTANCIA EN LINEA DIRECTA A BUCHAREST

FUNCION HEURISTICA h(n)PARA IR A BUCHAREST

05/03/2012

Arad Bucharest Craiova Dobreta Fagaras g Giurgiu Lugoj Mehadia Oradea Pitesti Rimnicu Sibiu Timisoara Ing. M.Sc. BRUNO VARGAS T. Zerind

366 0 160 242 178 77 244241 380 98 193 253 329 374

7

DEFINICION DE ESTADOS

La posición de cada ciudad. Espacio de Estados = {todas las ciudades} Estado inicial Arad E t d i i i l=A d Estado final = Bucharest05/03/2012 Ing. M.Sc. BRUNO VARGAS T. 8

DEFINICION DE PROCESOS O ACCIONES

Trasladarse de una ciudad a otra.

05/03/2012

Ing. M.Sc. BRUNO VARGAS T.

9

DEFINICION DE COMPONENTES DE FUNCIONDE EVALUACION f(n)

Función costo de la ruta : g(n) g( ) Función heurística : h(n) : distancias directas entre las demás ciudades y Bucarest Función de evaluación de la solución más barata pasandopor n : f( ) f (n) = g (n) + h(n) f(n)
05/03/2012 Ing. M.Sc. BRUNO VARGAS T. 10

REPRESENTACION GRAFICA DEL ALGORITMO DE BUSQUEDA A ASTERISCO (RUTA DE ARAD A BUCHAREST)

05/03/2012

Ing. M.Sc....