Estoy tratando de construir un A* solver para un 15-square puzzle.preguntas con respecto al uso de A * con el rompecabezas de 15 cuadrados
alt text http://i49.tinypic.com/343r8ki.jpg
El objetivo es volver a colocar los azulejos para que aparezcan en sus posiciones naturales. Solo puedes deslizar una ficha a la vez. Cada posible estado del rompecabezas es un nodo en el gráfico de búsqueda.
Para la función h (x), estoy usando una suma agregada, en todas las teselas, de la dislocación de la tesela desde el estado objetivo. En la imagen de arriba, el 5 está en la ubicación 0,0, y pertenece a la ubicación 1,0, por lo tanto, contribuye 1 a la función h (x). La siguiente ficha es la 11, ubicada en 0,1, y pertenece a 2,2, por lo tanto, contribuye 3 a h (x). Y así. EDITAR: Ahora entiendo que esto es lo que ellos llaman "distancia de Manhattan" o "taxicab distance".
He estado usando un conteo de pasos para g (x). En mi implementación, para cualquier nodo en el gráfico de estado, g es solo +1 del g del nodo anterior.
Para encontrar nodos sucesivos, solo examino dónde puedo mover el "agujero" en el rompecabezas. Hay 3 vecinos para el estado del rompecabezas (nodo alias) que se muestra: el agujero puede moverse hacia el norte, el oeste o el este.
Mi búsqueda A * converge a veces en una solución en 20s, a veces 180s, y en ocasiones no converge en absoluto (esperó 10 minutos o más). Creo que h es razonable. Me pregunto si he modelado g correctamente. En otras palabras, ¿es posible que mi función A * esté llegando a un nodo en el gráfico a través de una ruta que no es la ruta más corta?
Tal vez no he esperado lo suficiente? Tal vez 10 minutos no es lo suficientemente largo?
Para una disposición completamente al azar, (suponiendo que no haya problemas de paridad), ¿Cuál es el número promedio de permutaciones que examinará una solución A *? (demuestre las matemáticas)
Voy a buscar errores de lógica en mi código, pero mientras tanto, ¿Algún consejo?
(pd: está hecho en Javascript).
Además, no, esto no es tarea de CompSci. Es solo una cosa de exploración personal. Solo estoy tratando de aprender Javascript.
EDITAR: Me he dado cuenta que el tiempo de ejecución es altamente depende de la heurística. Vi el factor 10x aplicado a la heurística del artículo que alguien mencionó, y me hizo preguntarme: ¿por qué 10 veces? ¿Por qué lineal? Como esto se hace en javascript, podría modificar el código para actualizar dinámicamente una tabla html con el nodo que se está considerando actualmente. Esto me permitió echar un vistazo al algoritmo a medida que avanzaba. Con una heurística de distancia de taxi regular, observé como no lograba converger.
Había 5 y 12 en la fila superior, y seguían dando vueltas. Veía que 1,2,3,4 se arrastraba a la fila superior, pero luego se salían, y otros números se movían hacia arriba. Lo que esperaba ver era que 1,2,3,4 se arrastraba hasta la cima y luego se quedaba allí.
Pensé para mí mismo: esta no es la forma en que resuelvo esto personalmente. Haciendo esto manualmente, resuelvo la fila superior, luego la 2ª fila, luego la 3ª y 4ª filas de forma concurrente.
De modo que modifiqué la función h (x) para ponderar más las filas más altas y las columnas "lefter". El resultado fue que A * convergió mucho más rápido. Ahora se ejecuta en 3 minutos en lugar de "indefinidamente". Con el "vistazo" del que hablé, puedo ver que los números más pequeños se arrastran hasta las filas más altas y se quedan allí. No solo parece ser lo correcto, sino que funciona mucho más rápido.
Estoy en proceso de probar varias variaciones. Parece bastante claro que A * runtime es muy sensible a la heurística. Actualmente, la mejor heurística que he encontrado usa la suma de dislocation * ((4-i) + (4-j)) donde i y j son la fila y la columna, y la dislocación es la distancia del taxi.
Una parte interesante del resultado que obtuve: con una heurística particular, encuentro un camino muy rápido, pero obviamente no es el camino más corto. Creo que esto es porque estoy ponderando la heurística. En un caso, obtuve un camino de 178 pasos en 10s. Mi propio esfuerzo manual produce una solución en 87 movimientos. (mucho más que 10s). Más investigación garantizada.
Así que el resultado es que estoy viendo que la convergencia debe ser más rápida, y la ruta definitivamente no es la más corta. Tengo que pensar en esto más.
Código:
var stop = false;
function Astar(start, goal, callback) {
// start and goal are nodes in the graph, represented by
// an array of 16 ints. The goal is: [1,2,3,...14,15,0]
// Zero represents the hole.
// callback is a method to call when finished. This runs a long time,
// therefore we need to use setTimeout() to break it up, to avoid
// the browser warning like "Stop running this script?"
// g is the actual distance traveled from initial node to current node.
// h is the heuristic estimate of distance from current to goal.
stop = false;
start.g = start.dontgo = 0;
// calcHeuristic inserts an .h member into the array
calcHeuristicDistance(start);
// start the stack with one element
var closed = []; // set of nodes already evaluated.
var open = [ start ]; // set of nodes to evaluate (start with initial node)
var iteration = function() {
if (open.length==0) {
// no more nodes. Fail.
callback(null);
return;
}
var current = open.shift(); // get highest priority node
// update the browser with a table representation of the
// node being evaluated
$("#solution").html(stateToString(current));
// check solution returns true if current == goal
if (checkSolution(current,goal)) {
// reconstructPath just records the position of the hole
// through each node
var path= reconstructPath(start,current);
callback(path);
return;
}
closed.push(current);
// get the set of neighbors. This is 3 or fewer nodes.
// (nextStates is optimized to NOT turn directly back on itself)
var neighbors = nextStates(current, goal);
for (var i=0; i<neighbors.length; i++) {
var n = neighbors[i];
// skip this one if we've already visited it
if (closed.containsNode(n)) continue;
// .g, .h, and .previous get assigned implicitly when
// calculating neighbors. n.g is nothing more than
// current.g+1 ;
// add to the open list
if (!open.containsNode(n)) {
// slot into the list, in priority order (minimum f first)
open.priorityPush(n);
n.previous = current;
}
}
if (stop) {
callback(null);
return;
}
setTimeout(iteration, 1);
};
// kick off the first iteration
iteration();
return null;
}
Usa la suma de la distancia de las fichas desde su posición de objetivo como la heurística. Es mucho más efectivo. (ver Inteligencia Artificial, un Enfoque Moderno Segunda Edición p.107: El efecto de la precisión heurística en el rendimiento) –
Eso es lo que estoy haciendo. Escribí: * Para la función h (x), estoy usando una suma agregada, en todas las teselas, de la dislocación de la tesela desde el estado objetivo. * Y cuando dices "mucho más efectivo", ¿qué quieres decir? ¿comparado con que? – Cheeso