Estou tentando construir umUm solver * paraQuebra-cabeça de 15 quadrados.

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

O objetivo é reorganizar as peças de forma que elas apareçam em suas posições naturais. Você só pode deslizar um bloco de cada vez. Cada estado possível do quebra-cabeça é um nó no gráfico de pesquisa.

Para a função h (x), estou usando uma soma agregada, em todos os blocos, do deslocamento do bloco do estado de meta. Na imagem acima, o 5 está na posição 0,0 e pertence ao local 1,0, portanto, ele contribui com 1 para a função h (x). O próximo bloco é o 11, localizado em 0,1, e pertence a 2,2, portanto, contribui com 3 para h (x). E assim por diante.EDITAR: Eu agora entendo isso é o que eles chamam de "distância de Manhattan", ou "distância do táxi".

Eu tenho usado uma contagem de passos para g (x). Na minha implementação, para qualquer nó no gráfico de estado, g é apenas +1 do g do nó anterior.

Para encontrar nós sucessivos, eu apenas examino onde posso mover o "buraco" no quebra-cabeça. Há 3 vizinhos para o estado do quebra-cabeça (também conhecido como nó) que é exibido: o buraco pode se mover para o norte, oeste ou leste.

Minha busca A * às vezes converge para uma solução em 20s, às vezes 180s, e algumas vezes não converge (esperei 10 minutos ou mais). Eu acho que é razoável. Eu estou querendo saber se eu modelei g corretamente. Em outras palavras, é possível que minha função A * esteja alcançando um nó no gráfico através de um caminho que não seja o caminho mais curto?

Talvez eu não tenha esperado o suficiente? Talvez 10 minutos não seja tempo suficiente?

Para um arranjo totalmente aleatório, (assumindo que não há problemas de paridade), Qual é o número médio de permutações que uma solução A * examinará? (por favor mostre a matemática)

Eu vou procurar por erros de lógica no meu código, mas enquanto isso, alguma dica?

(ps: é feito em Javascript).

Além disso, não, isso não é tarefa de casa da CompSci. É apenas uma coisa de exploração pessoal. Eu só estou tentando aprender JavaScript.

EDITAR: Eu descobri que o tempo de execução é altamente dependente da heurística. Eu vi o fator 10x aplicado à heurística do artigo que alguém mencionou, e isso me fez pensar - por que 10x? Por que linear? Como isso é feito em javascript, eu poderia modificar o código para atualizar dinamicamente uma tabela html com o nó sendo considerado atualmente. Isso me permitiu espiar o algoritmo enquanto progredia. Com uma heurística regular de táxi, observei que ela não convergiu.

Havia 5 e 12 na fila de cima, e eles ficavam por perto. Eu veria 1,2,3,4 arrastando-se para a linha superior, mas depois eles desistiriam e outros números subiriam para lá. O que eu estava esperando para ver foi 1,2,3,4 tipo de rastejando até o topo e, em seguida, ficar lá.

Eu pensei comigo mesmo - não é assim que eu resolvo isso pessoalmente. Fazendo isso manualmente, eu resolvo a linha superior, depois a linha 2ne, depois a terceira e a quarta linhas simultaneamente.

Então eu ajustei a função h (x) para pesar mais as linhas mais altas e as colunas "lefter". O resultado foi que o A * convergiu muito mais rapidamente. Agora corre em 3 minutos em vez de "indefinidamente". Com a "espiada" de que falei, posso ver os números menores subindo até as linhas mais altas e ficando lá. Isso não parece ser a coisa certa, é muito mais rápido.

Eu estou no processo de tentar um monte de variações. Parece bastante claro que o tempo de execução do A * é muito sensível à heurística. Atualmente, a melhor heurística que encontrei usa o somatório dedislocation * ((4-i) + (4-j)) onde i e j são a linha e a coluna, e o deslocamento é a distância do taxista.

Uma parte interessante do resultado que obtive: com uma determinada heurística, acho um caminho muito rápido, mas obviamente não é o caminho mais curto. Eu acho que isso é porque eu estou pesando a heurística. Em um caso eu tenho um caminho de 178 passos em 10s. Meu próprio esforço manual produz uma solução em 87 movimentos. (muito mais do que 10s). Mais investigação garantida.

Então, o resultado é que eu estou vendo que a convergência deve ser mais rápida, e o caminho definitivamente não é o mais curto. Eu tenho que pensar mais sobre isso.

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