PDF de programación - El algoritmo Fringe Search como solución superior a A* en la búsqueda de caminos sobre gráficos de malla

UNIVERSIDAD NACIONAL AUT ÓNOMA DE MÉXICO

FACULTAD DE CONTADURÍA Y ADMINISTRACI ÓN

El algoritmo Fringe Search como

solución superior a A* en la búsqueda de

caminos sobre gráficos de malla

T

E

S

I

S

PRESENTA:

Jesús Manuel Mager Hois

México, D.F.

2015

UNIVERSIDAD NACIONAL AUT ÓNOMA DE MÉXICO

FACULTAD DE CONTADURÍA Y ADMINISTRACI ÓN

El algoritmo Fringe Search como

solución superior a A* en la búsqueda de

caminos sobre gráficos de malla

E

S
T
QUE PARA OBTENER EL TÍTULO DE:

S

I

Licenciado en Informática

PRESENTA:

Jesús Manuel Mager Hois

ASESORA:

Mtra. GARCÍA VARGAS ADRIANA

México, D.F.

2015

Índice general

Índice de Algoritmos

Índice de figuras

Introducción

1. Marco teórico

1.1. Teoría de gráficos y definiciones formales . . . . . . . . . . . . . . . . . . . . . .

1.2. La búsqueda de caminos sobre gráficos desde la inteligencia artificial . . . . . . .

1.2.1. Búsqueda no informada

. . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.2. Búsqueda informada . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3. El Algoritmo Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2. Marco Contextual

2.1. El algoritmo A* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.1. Planteamiento formal . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.2. La estimación heurística . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.2.1. Distancia Manhattan . . . . . . . . . . . . . . . . . . . . . . . .

2.1.2.2. Distancia de Chebyshov . . . . . . . . . . . . . . . . . . . . . .

2.1.2.3. Distancia Euclidiana . . . . . . . . . . . . . . . . . . . . . . . .

2.1.2.4. Algunas notas sobre la función heurística . . . . . . . . . . . . .

2.1.3. El algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.4. Los tipos de datos usados para el algoritmo . . . . . . . . . . . . . . . .

2.1.4.1. Listas ordenadas . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.4.2. Binary Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.4.3. Skiplist

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

3

4

7

15

15

17

18

20

21

24

24

24

25

26

27

27

28

28

30

31

31

32

2.1.4.4. Tablas hash y arreglos . . . . . . . . . . . . . . . . . . . . . . .

2.1.5.

Implementación mixta . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.6. Algunas notas sobre la implementación . . . . . . . . . . . . . . . . . . .

2.1.7. Análisis del código fuente

. . . . . . . . . . . . . . . . . . . . . . . . . .

2.2. Fringe Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.1.

IDA* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.2. Mejorando IDA*: Fringe Search . . . . . . . . . . . . . . . . . . . . . . .

2.2.2.1. Heurística . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.2.2. Apuntes sobre los caminos generados . . . . . . . . . . . . . . .

2.2.3.

Implementación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.4. Análisis del código fuente

. . . . . . . . . . . . . . . . . . . . . . . . . .

3. Método y técnica

3.1. El método . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.1. El método dialéctico . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.2. Tipo de estudio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.3. Fuentes

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.4.

Indicadores y variables . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2. La técnica utilizada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4. Resultados

4.1. Comparación entre A* y Fringe Search . . . . . . . . . . . . . . . . . . . . . . .

4.1.1. La experimentación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.1.1.1. El entorno de experimentación . . . . . . . . . . . . . . . . . .

4.1.1.2. El experimento . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.1.1.3. Presentación visual . . . . . . . . . . . . . . . . . . . . . . . . .

4.1.2. Comportamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.1.2.1. Sobre un mapa de una sola medida . . . . . . . . . . . . . . . .

4.1.2.2. Sobre mapas aleatorios de medidas diversas

. . . . . . . . . . .

4.1.2.3. Regresiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.1.3. Análisis

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.1.3.1. Velocidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

32

33

33

39

39

40

41

41

42

43

50

50

50

52

52

53

53

55

55

55

55

56

57

58

58

59

60

62

62

2

4.1.3.2. Camino . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2. Aplicaciones en casos prácticos

. . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2.1. Búsqueda de mejores caminos . . . . . . . . . . . . . . . . . . . . . . . .

4.2.2. Caminos en el mundo real

. . . . . . . . . . . . . . . . . . . . . . . . . .

4.2.2.1. Problemas de transporte . . . . . . . . . . . . . . . . . . . . . .

4.2.2.2. Robótica

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2.3. Juegos de vídeo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2.4. Otros usos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Conclusiones

Anexos

Índice alfabético

Bibliografía

64

66

66

68

69

70

72

73

74

80

99

102

3

Índice de Algoritmos

1. Depth-First Search (DFS)

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.

Breadth-first search (BFS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3. Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.

5.

A* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Fringe Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

20

23

29

49

4

Índice de figuras

1.1. Gráfico de Lattice o de malla

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2. Algoritmo Djikstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

22

2.1.

Implementación de las listas now y later. . . . . . . . . . . . . . . . . . . . . . .

43

4.1. Camino encontrado por A* en un gráfico 100x100. . . . . . . . . . . . . . . . . .

4.2. Camino encontrado por Fringe Search en un gráfico 100x100. . . . . . . . . . . .

57

58

4.3. Comportamiento de A* y Fringe Search con respecto al número de nodos del

gráfico y al tamaño del camino.

. . . . . . . . . . . . . . . . . . . . . . . . . . .

59

4.4. Comportamiento del tiempo de ejecución de los dos algoritmos con respecto al

tamaño del gráfico.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.5. Residuos y datos relevantes para A*(arriba) y Fringe Search(Abajo) . . . . . . .

4.6. Comparación del tiempo de ejecución entre A* y Fringe Search sobre los mismos

gráficos.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.7. Tabla ANOVA: relación entre la velocidad y los dos algoritmos . . . . . . . . . .

60

61

63

64

4.8. Comparación de los caminos generados A* y Fringe Search en los mismos gráficos. 65

4.9. Tabla ANOVA: Relación entre el tamaño del camino y los dos algoritmos . . . .

65

4.10. Búsqueda de caminos en MapQuest usando OpenStreetMap. La imagen fue toma-

da de la wiki de OSM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.11. Búsqueda del mejor camino de robots esclavos . . . . . . . . . . . . . . . . . . .

4.12. Agentes del juego libre TuxHistory buscando el mejor camino para llevar la

70

71

cosecha del campo al granero.

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

73

5

Dedicatorias

A mi madre Elisabeth Mager por haberme ofrecido todas las oportunidades, apoyo y cariño

para la optimización en este intrincado gráfico llamado vida.

6

Agradecimientos

Agradezco al pueblo mexicano que ha hecho posible que estudie en la Universidad Nacional

Autónoma de México, institución pública y gratuita, de una calidad extraordinaria y que aún

se encuentra al servicio de todos; a todos los profesores, trabajadores y alumnos de la UNAM

que han sido la comunidad que me ha formado desde el CCH Naucalpan, la FES Acatlán y

la Facultad de Contaduría y Administración; pero sobre todo a aquellos que han puesto sus

esfuerzos en conservar su espíritu crítico y abierto.

Quiero hacer mención especial del Lic. Carlos Pineda, profesor de la Facultad de Estudios

Superiores Cuautitlán que me ha dado dirección en el estudio del tema de búsqueda de mejores

camino, sobre todo en el área paralela, a mi asesora de tesis Mtra. Adriana García Vargas que

ha dedicado un gran esfuerzo en apoyarme en este trabajo, al Dr. Iván Vladimir Meza Ruiz del

IIMAS que aportó su orientación en la definición del tema, además de correcciones al trabajo

y a mi madre la Dra. Elisabeth Mager que me enseño desde joven a realizar investigaciones

exhaustivas y los métodos para alcanzar los objetivos académicos.

También agradezco a la comunidad de Software Libre en el mundo, y en especial al proyecto

Tux4Kids que me introdujo en este increíble mundo de la inteligencia artificial aplicada a juegos

que sirven en la enseñanza para niños en todo el mundo. También quiero agradecer al grupo

de Software Libre de la FES Cuautitlán y el apoyo con el diseño gráfico por parte de Rebeca

Guerrero.

7

Introducción

En un mundo virtual, que puede representar un espacio de la realidad, existen posibles

movimientos, y encontrar los mejores caminos para realizar un desplazamiento dentro de este

entorno es un tema que ha sido intensamente estudiado por la inteligencia