Estoy tratando de construir unA * solver paraRompecabezas de 15 cuadrados.

texto alt http://i49.tinypic.com/343r8ki.jpg

El objetivo es reorganizar las baldosas para que aparezcan en sus posiciones naturales. Solo puedes deslizar una ficha a la vez. Cada estado posible del rompecabezas es un nodo en el gráfico de búsqueda.

Para la función h (x), estoy usando una suma agregada, en todos los mosaicos, de la dislocación del mosaico del 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 con 1 a la función h (x). El siguiente mosaico es el 11, ubicado en 0,1, y pertenece a 2,2, por lo tanto, contribuye con 3 a h (x). Y así.EDITAR: Ahora entiendo que esto es lo que ellos llaman "distancia de Manhattan", o "distancia de taxi".

He estado usando un recuento de pasos para g (x). En mi implementación, para cualquier nodo en el gráfico de estado, g es solo +1 de la 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 (también conocido como nodo) que se muestra: el agujero puede moverse hacia el norte, el oeste o el este.

Mi búsqueda A * a veces converge en una solución en 20, a veces 180, y a veces no converge en absoluto (esperó 10 minutos o más). Creo que 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 más corta?

Tal vez no he esperado lo suficiente? Tal vez 10 minutos no es suficiente?

Para una disposición completamente aleatoria, (suponiendo que no haya problemas de paridad), ¿cuál es el número promedio de permutaciones que examinará una solución A *? (por favor muestra las matemáticas)

Voy a buscar errores lógicos en mi código, pero mientras tanto, ¿Algún consejo?

(ps: se hace 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: He descubierto que el tiempo de ejecución depende en gran medida 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é 10x? ¿Por qué lineal? Debido a que esto se hace en javascript, podría modificar el código para actualizar dinámicamente una tabla html con el nodo que actualmente se está considerando. Esto me permitió echar un vistazo al algoritmo a medida que avanzaba. Con una heurística de taxis de distancia regular, observé que no podía converger.

Había 5 y 12 en la fila superior, y seguían dando vueltas. Vería 1,2,3,4 arrastrarse en la fila superior, pero luego se retiraban y otros números se movían allí. Lo que esperaba ver era 1,2,3,4 que se arrastraba hasta la cima y luego se quedaba allí.

Pensé para mí mismo: esta no es la forma en que lo resuelvo personalmente. Haciendo esto manualmente, resuelvo la fila superior, luego la segunda fila, luego la tercera y la cuarta fila de forma concurrente.

Así que modifiqué la función h (x) para que pesara más las filas más altas y las columnas de "izquierda". El resultado fue que el 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 los números más pequeños que se arrastran hasta las filas más altas y permanecer allí. No solo parece lo correcto, sino que se ejecuta mucho más rápido.

Estoy en el proceso de probar un montón de variaciones. Parece bastante claro que el tiempo de ejecución A * es muy sensible a la heurística. Actualmente la mejor heurística que he encontrado utiliza la suma dedislocation * ((4-i) + (4-j)) donde i y j son la fila y la columna, y la dislocación es la distancia del taxi.

Obtuve una parte interesante del resultado: con una heurística particular, encuentro un camino muy rápidamente, pero obviamente no es el más corto. Creo que esto es porque estoy sopesando la heurística. En un caso conseguí un camino de 178 pasos en 10s. Mi propio esfuerzo manual produce una solución en 87 movimientos. (mucho más de 10s). Más investigación justificada.

Así que el resultado es que veo que la convergencia debe ser más rápida, y el camino definitivamente no es el más corto. Tengo que pensar más en esto.

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;
}