Indice
Autor
Esta práctica ha sido realizada únicamente por Jose María Rodríguez Valls.
Se adjunta la documentación y el código fuente de dicha sesión.
Problema 18
Dada una palabra w y un diccionario D, se quiere saber cuales son las permutaciones necesarias y suficientes entre las letras consecutivas para obtener una palabra w' que exista en D
Para solucionar el problema he recurrido a las clases AIMA de Java.
En un principio el problema está resuelto para poder introducir N palabras dentro del diccionario.
Resultado 1
Para realizar el primer experimento me he basado con los datos del enunciado del problema.
Tomando w = ARTE como estado inicial y D = {TERA,RETA,TRAE} como posibles estados finales.
La aplicación del operador se realiza mediante una función indicando el índice del carácter origen (carácter a desplazar) y el índice del carácter destino.
Ejemplo
Origen: 0 Destino: 1 Word: RATE
Indica que partiendo de la palabra ARTE movemos el carácter 0 a la posición 1 y viceversa.
(Intercambiamos la A por la R).
Ejecución del Algoritmo
Anchura
Origen: 0 Destino: 0 Word: ARTE
Origen: 0 Destino: 1 Word: RATE
Origen: 1 Destino: 3 Word: RETA
QueueSize = 55
Nodes Expanded = 11
---------------------
Profundidad
Origen: 0 Destino: 0 Word: ARTE
Origen: 0 Destino: 1 Word: RATE
Origen: 0 Destino: 1 Word: ARTE
Origen: 0 Destino: 1 Word: RATE
Origen: 0 Destino: 1 Word: ARTE
Origen: 0 Destino: 1 Word: RATE
Origen: 0 Destino: 1 Word: ARTE
Origen: 0 Destino: 1 Word: RATE
Origen: 0 Destino: 1 Word: ARTE
Origen: 0 Destino: 1 Word: RATE
Origen: 0 Destino: 1 Word: ARTE
Origen: 0 Destino: 1 Word: RATE
Origen: 0 Destino: 1 Word: ARTE
Origen: 0 Destino: 1 Word: RATE
Origen: 0 Destino: 2 Word: TARE
Origen: 1 Destino: 3 Word: TERA
QueueSize = 130
Nodes Expanded = 26
---------------------
Profundidad Iterativa
Searching at depth 1
Searching at depth 2
Origen: 0 Destino: 0 Word: ARTE
Origen: 0 Destino: 1 Word: RATE
Origen: 1 Destino: 3 Word: RETA
QueueSize = 65
Nodes Expanded = 13
---------------------
A*
Origen: 0 Destino: 0 Word: ARTE
Origen: 0 Destino: 1 Word: RATE
Origen: 0 Destino: 2 Word: TARE
Origen: 1 Destino: 3 Word: TERA
QueueSize = 30
Nodes Expanded = 6
---------------------
IDA*
f cost of result node = 4
Origen: 0 Destino: 0 Word: ARTE
Origen: 0 Destino: 1 Word: RATE
Origen: 0 Destino: 2 Word: TARE
Origen: 1 Destino: 3 Word: TERA
QueueSize = 40
Nodes Expanded = 8
Resultado 2
Para realizar el siguiente experimento cambiamos la configuración de estados iniciales y finales.
Tomando w = RATO como estado inicial y D = {TORA,ROAT,TARO} como posibles estados finales.
Ejecución del Algoritmo
Anchura
Origen: 0 Destino: 0 Word: RATO
Origen: 0 Destino: 2 Word: TARO
QueueSize = 10
Nodes Expanded = 2
---------------------
Profundidad
Origen: 0 Destino: 0 Word: RATO
Origen: 0 Destino: 1 Word: ARTO
Origen: 0 Destino: 1 Word: RATO
Origen: 0 Destino: 1 Word: ARTO
Origen: 0 Destino: 1 Word: RATO
Origen: 0 Destino: 1 Word: ARTO
Origen: 0 Destino: 1 Word: RATO
Origen: 0 Destino: 1 Word: ARTO
Origen: 0 Destino: 1 Word: RATO
Origen: 0 Destino: 1 Word: ARTO
Origen: 0 Destino: 1 Word: RATO
Origen: 0 Destino: 1 Word: ARTO
Origen: 0 Destino: 1 Word: RATO
Origen: 0 Destino: 1 Word: ARTO
Origen: 0 Destino: 1 Word: RATO
Origen: 0 Destino: 2 Word: TARO
QueueSize = 80
Nodes Expanded = 16
---------------------
Profundidad Iterativa
Searching at depth 1
Origen: 0 Destino: 0 Word: RATO
Origen: 0 Destino: 2 Word: TARO
QueueSize = 10
Nodes Expanded = 2
---------------------
A*
Origen: 0 Destino: 0 Word: RATO
Origen: 1 Destino: 3 Word: ROTA
Origen: 0 Destino: 2 Word: TORA
QueueSize = 10
Nodes Expanded = 2
---------------------
IDA*
f cost of result node = 3
Origen: 0 Destino: 0 Word: RATO
Origen: 0 Destino: 2 Word: TARO
QueueSize = 15
Nodes Expanded = 3
Cambio de Heurístico
Ahora pasaremos ha cambiar el heurístico para poder apreciar los cambios.
El nuevo heuristico será:
h'(wp) = #D - dif(wp, D)
Donde:
dif(wp, D) = número de palabras en D tales que su letra 0 coincide con la letra 0 de wp.
Ejecución del Algoritmo
Anchura
Origen: 0 Destino: 0 Word: RATO
Origen: 0 Destino: 2 Word: TARO
QueueSize = 10
Nodes Expanded = 2
---------------------
Profundidad
Origen: 0 Destino: 0 Word: RATO
Origen: 0 Destino: 1 Word: ARTO
Origen: 0 Destino: 1 Word: RATO
Origen: 0 Destino: 1 Word: ARTO
Origen: 0 Destino: 1 Word: RATO
Origen: 0 Destino: 1 Word: ARTO
Origen: 0 Destino: 1 Word: RATO
Origen: 0 Destino: 1 Word: ARTO
Origen: 0 Destino: 1 Word: RATO
Origen: 0 Destino: 1 Word: ARTO
Origen: 0 Destino: 1 Word: RATO
Origen: 0 Destino: 1 Word: ARTO
Origen: 0 Destino: 1 Word: RATO
Origen: 0 Destino: 1 Word: ARTO
Origen: 0 Destino: 1 Word: RATO
Origen: 0 Destino: 2 Word: TARO
QueueSize = 80
Nodes Expanded = 16
---------------------
Profundidad Iterativa
Searching at depth 1
Origen: 0 Destino: 0 Word: RATO
Origen: 0 Destino: 2 Word: TARO
QueueSize = 10
Nodes Expanded = 2
---------------------
A*
Origen: 0 Destino: 0 Word: RATO
Origen: 0 Destino: 2 Word: TARO
QueueSize = 5
Nodes Expanded = 1
---------------------
IDA*
f cost of result node = 2
Origen: 0 Destino: 0 Word: RATO
Origen: 0 Destino: 2 Word: TARO
QueueSize = 5
Nodes Expanded = 1
Conclusiones
La aplicación de cambio de heurístico parece mejorar el rendimiento para alcanzar la solución en los casos de algoritmos A* y IDA*.
Con el heuristico anterior el coste de f era superior al del nuevo heuristico.
Se realizan menos expansiones de los nodos y el coste del resultado final se acerca más al valor real.
En el caso del cambio de estados iniciales y finales he observado que pueden aumentar o disminuir sensiblemente la cantidad de nodos abiertos para llegar a la solución final.
Problema Gasolineras
Se dispone de un grafo apartir del cual tenemos las distancias entre los diferentes puntos de una ciudad.
El problema pretende colocar g gasolineras en la ciudad lo máximo distanciadas posible.
No tendré en cuenta la central de abastecimiento puesto que no tiene ningún sentido si solo pretendemos separar las gasolineras.
El algoritmo genera aleatoriamente el mapa de la ciudad y la cantidad de gasolineras.
Heuristico
Como heurístico del problema he considerado oportuno utilizar el algoritmo de Dijkstra para encontrar el camino de distancia mínima entre dos gasolineras.
Si bien es verdad que realmente nos interesa el camino de distancia máximo, no resulta complicado invertir el resultado.
El heuristico es:
para toda i,j que existen dentro del número de gasolineras.
h'(n) = 9999 - sumatorio( distancia_minima(i,j) );
Haciendo esto pretendo que h' dependa de las distancias entre las gasolineras en función de la posición dentro del mapa.
Resultado 1
El problema dispone de dos operadores:
- Desplazar una gasolinera a una posición adyacente sin ocupar.
- Intercambiar la posición entre dos gasolineras adyacentes.
Los diferentes pasos los podemos observar de la siguiente manera:
g={4,5,3}
Nos indica que existen tres gasolineras.
g[0] (Gasolinera 0) se encuentra en el vertice 4.
g[1] (Gasolinera 1) se encuentra en el vertice 5.
g[2] (Gasolinera 2) se encuentra en el vertice 3.
Ejecución del Algoritmo
======GRAFO MAPA CIUDAD======
(0,0) = Distancia: 9
(1,0) = Distancia: 4
(1,1) = Distancia: 2
(2,0) = Distancia: 0
(2,1) = Distancia: 9
(2,2) = Distancia: 2
(3,0) = Distancia: 5
(3,1) = Distancia: 2
(3,2) = Distancia: 8
(3,3) = Distancia: 2
ARESTAS: 10
VERTICES: 4
GASOLINERAS: 2
=============================
g={0,1}
heuristico del estado inicial: 9991
==========HILLCLIMBING=========
cost of result node is 9981
Search stuck on local maximum
HighestNode has Value -9981
g={0,1}
g={2,1}
QueueSize = 14
Nodes Expanded = 2
======SIMULATED ANNEALING======
cost of result node is 9981
g={0,1}
g={0,1}
g={0,1}
g={0,1}
g={0,1}
g={0,3}
g={2,1}
QueueSize = 133
Nodes Expanded = 19
Resultado 2
Pasamos a volver a ejecutar el programa para obtener otro resultado en función del mapa y gasolineras aleatorias.
Ejecución del Algoritmo
======GRAFO MAPA CIUDAD======
(0,0) = Distancia: 4
(1,0) = Distancia: 6
(1,1) = Distancia: 5
(2,0) = Distancia: 5
(2,1) = Distancia: 5
(2,2) = Distancia: 8
(3,0) = Distancia: 8
(3,1) = Distancia: 7
(3,2) = Distancia: 4
(3,3) = Distancia: 7
ARESTAS: 10
VERTICES: 4
GASOLINERAS: 3
=============================
g={0,1,2}
heuristico del estado inicial: 9967
==========HILLCLIMBING=========
cost of result node is 9957
Search stuck on local maximum
HighestNode has Value -9957
g={0,1,2}
g={0,1,3}
QueueSize = 22
Nodes Expanded = 2
======SIMULATED ANNEALING======
cost of result node is 9957
g={0,1,2}
g={3,1,2}
g={0,1,2}
g={3,1,2}
g={0,1,2}
g={0,1,2}
g={3,1,2}
g={0,1,2}
g={0,1,3}
QueueSize = 231
Nodes Expanded = 21
Conclusiones
Por lo que podemos apreciar después de realizar las dos ejecuciones el algoritmo Simulated Anneling consume más recursos para llegar a una solución.
La calidad de la solución dependerá de la profundidad a la cual permitamos que se ejecuten nuestros Algoritmos.
No necesariamente los dos algoritmos llegarían a una misma solución. Puesto que depende de los parámetros de búsqueda.
El heuristico parece acercarse al propósito del problema. Es muy posible que exista alguno mejor.