Inteligencia Artificial - Viajante De Comercio

El problema del viajante de comercio

Ingeniería en Informática

0743 - Inteligencia Artificial
Gabriel Fiol

León Eduardo Monzón Martín
Palma, 17 de marzo de 2008

1

ENUNCIADO DEL PROBLEMA ________________________________________________ 1

2

DESCRIPCIÓN DEL PROBLEMA_______________________________________________ 2
2.1
DEFINICIÓN DEL OBJETIVO DEL PROBLEMA_______________________________________
2.2
ABSTRACCIÓN DEL PROBLEMA: ESTADOS Y ACCIONES ______________________________
2.3
FORMULACIÓN DEL PROBLEMA ________________________________________________
2.3.1
Estado inicial: __________________________________________________________
2.3.2
Función sucesor: ________________________________________________________
2.3.3
Test objetivo:___________________________________________________________
2.3.4
Coste de camino: ________________________________________________________

3

MÉTODOS DE BÚSQUEDA: RESOLUCIÓN DEL PROBLEMA _____________________ 4
3.1
MÉTODOS DE BÚSQUEDA NO INFORMADOS _______________________________________
3.1.1
Primero en profundidad___________________________________________________
3.1.2
Primero en profundidad con ramificacióny poda _______________________________
3.1.3
Búsqueda de costo uniforme _______________________________________________
3.2
MÉTODOS DE BÚSQUEDA INFORMADA O HEURÍSTICA _______________________________
3.2.1
El vecino más próximo: heurística local -de mejora iterativa- _____________________
3.2.2
Método de escalada: heurística local ________________________________________
3.2.3
BúsquedaA*: heurística primero el (aparentemente) mejor _______________________

4

ADECUACIDAD DE CADA TÉCNICA _____________________________________________
Completitud ___________________________________________________________
Complejidad temporal ___________________________________________________
Complejidad espacial____________________________________________________
Optimalidad___________________________________________________________
¿POR QUÉ USAR HEURÍSTICAS? _______________________________________________
VENTAJAS DE CADA TÉCNICA ________________________________________________
Ventajas de Primero en profundidad ________________________________________
Ventajas de Ramificación y poda___________________________________________
Ventajas de Costo uniforme_______________________________________________
Ventajas de la heurística Vecino más próximo ________________________________
Ventajas de la heurística de Escalada _______________________________________
Ventajas de la Búsqueda A*_______________________________________________
COMPARATIVA DE TÉCNICAS EN RESULTADOS OBTENIDOS __________________________
Comparativa de tiempos_________________________________________________
Comparativa de número de nodos recorridos _________________________________
Conclusiones: óptimo en tiempo y nodos visitados _____________________________
Conclusiones __________________________________________________________

FORMULACIÓN DEL PROBLEMA _______________________________________________ 21
GENERACIÓN DE SOLUCIONES ________________________________________________ 21DESCRIPCIÓN DE LA IMPLEMENTACIÓN ____________________________________ 24
6.1
ESTRUCTURAS DE DATOS USADAS _____________________________________________
6.1.1
Estructura Lista Ciudad__________________________________________________
6.1.2
Estructura NodoArbol ___________________________________________________
6.2
FUNCIONES DESTACADAS USADAS EN LA IMPLEMENTACIÓN _________________________
6.3ESTRUCTURA DE FICHEROS DE CÓDIGO FUENTE___________________________________

7

11
12
12
12
13
14
14
14
14
14
15
15
15
16
16
17
19
19

FUNCIONAMIENTO DE LA APLICACIÓN _____________________________________ 21
5.1
5.2

6

4
4
5
6
7
7
8
9

ANÁLISIS DE CADA ALGORITMO ____________________________________________ 11
4.1
4.1.1
4.1.2
4.1.3
4.1.4
4.2
4.3...