Я пытаюсь построитьA * решатель дляЗагадка с 15 квадратами.

альтернативный текст http://i49.tinypic.com/343r8ki.jpg

Цель состоит в том, чтобы переставить плитки так, чтобы они появлялись в их естественном положении. Вы можете сдвинуть только одну плитку за раз. Каждое возможное состояние головоломки - это узел в графе поиска.

Для функции h (x) я использую суммарную сумму по всем плиткам дислокации плитки из состояния цели. На изображении выше, 5 находится в местоположении 0,0, и оно принадлежит в местоположении 1,0, поэтому оно вносит 1 в функцию h (x). Следующая ячейка - это 11, расположенная в 0,1, и принадлежащая в 2,2, поэтому она вносит 3 в h (x). И так далее.РЕДАКТИРОВАТЬ: Теперь я понимаю, что это то, что они называют "Манхэттенское расстояние", или "расстояние такси».

Я использовал счетчик шагов для g (x). В моей реализации для любого узла в графе состояний g равно +1 от g предыдущего узла.

Чтобы найти последовательные узлы, я просто исследую, где я могу переместить «дыру» в головоломке. Для состояния головоломки (он же узел) отображается 3 соседа: дыра может двигаться на север, запад или восток.

Мой поиск A * иногда сходится к решению в 20 секунд, иногда 180, а иногда вообще не сходится (ждал 10 минут или больше). Я думаю, что это разумно. Мне интересно, правильно ли я смоделировал г. Другими словами, возможно ли, что моя функция A * достигает узла в графе по пути, который не является кратчайшим?

Может быть, я не ждал достаточно долго? Может быть, 10 минут не достаточно долго?

Для полностью случайного расположения (при условии отсутствия проблем с четностью), каково среднее число перестановок, которое будет проверено решением A *? (пожалуйста, покажите математику)

Я собираюсь искать логические ошибки в моем коде, но в то же время, какие-нибудь советы?

(PS: это сделано в Javascript).

Кроме того, нет, это не домашняя работа CompSci. Это просто личное исследование. Я просто пытаюсь выучить Javascript.

РЕДАКТИРОВАТЬЯ обнаружил, что время выполнения сильно зависит от эвристики. Я видел 10-кратный коэффициент, примененный к эвристике из статьи, которую кто-то упоминал, и это заставило меня задуматься - почему 10-кратное? Почему линейный? Поскольку это сделано в javascript, я мог бы изменить код для динамического обновления html-таблицы с учетом рассматриваемого узла. Это позволило мне взглянуть на алгоритм по мере его развития. При регулярной эвристике на такси я наблюдал, как она не сходится.

В верхнем ряду было 5 и 12, и они продолжали торчать. Я бы увидел 1,2,3,4 ползущих в верхнем ряду, но потом они выпадут, и другие числа будут двигаться там. То, что я надеялся увидеть, было 1,2,3,4 вроде ползания до вершины, а затем оставаться там.

Я подумал про себя - это не так, как я решаю это лично. Делая это вручную, я решаю верхний ряд, затем 2-й ряд, затем 3-й и 4-й ряды одновременно.

Таким образом, я настроил функцию h (x) для более тяжелого взвешивания старших строк и столбцов «lefter». Результатом было то, что A * сходились намного быстрее. Теперь он запускается за 3 минуты вместо «бесконечно». С «взглядами», о которых я говорил, я вижу, как меньшие числа ползут до верхних рядов и остаются там. Это не только кажется правильным, но и работает намного быстрее.

Я пробую кучу вариантов. Кажется довольно ясным, что среда выполнения A * очень чувствительна к эвристике. В настоящее время лучшая эвристика, которую я нашел, использует суммированиеdislocation * ((4-i) + (4-j)) где i и j - строка и столбец, а дислокация - расстояние такси.

Одна интересная часть результата, который я получил: с определенной эвристикой я нахожу путь очень быстро, но это, очевидно, не самый короткий путь. Я думаю, что это потому, что я взвешиваю эвристику. В одном случае я получил путь 178 шагов за 10 секунд. Мои собственные ручные усилия дают решение за 87 ходов. (намного больше 10 с). Требуется дополнительное расследование.

В результате я вижу, что он должен сходиться быстрее, и путь определенно не самый короткий. Я должен думать об этом больше.

Код:

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