pytania dotyczące użycia A * z układanką 15-kwadratową

Próbuję zbudowaćA * solver dla15-kwadratowa łamigłówka.

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

Celem jest ponowne ułożenie płytek tak, aby pojawiły się w ich naturalnych pozycjach. Możesz przesuwać tylko jedną płytkę na raz. Każdy możliwy stan układanki jest węzłem na wykresie wyszukiwania.

W przypadku funkcji h (x) używam sumarycznej sumy, dla wszystkich płytek, przemieszczenia płytki ze stanu celu. Na powyższym obrazie 5 znajduje się w miejscu 0,0 i należy do miejsca 1,0, dlatego przyczynia się do 1 funkcji h (x). Kolejny kafelek to 11, znajdujący się na 0,1 i należy do 2,2, dlatego przyczynia się do 3 do h (x). I tak dalej.EDYTOWAĆ: Teraz rozumiem, że to właśnie nazywają „odległością Manhattanu” lub „odległość taksówki

Używam liczby kroków dla g (x). W mojej implementacji, dla dowolnego węzła na wykresie stanu, g jest tylko +1 od poprzedniego g węzła.

Aby znaleźć kolejne węzły, po prostu sprawdzam, gdzie mogę przesunąć „dziurę” w układance. Wyświetlany jest 3 sąsiadów stanu logicznego (aka węzeł): dziura może poruszać się na północ, zachód lub wschód.

Moje wyszukiwanie A * zbiega się czasem z rozwiązaniem w 20s, czasem 180s, a czasami wcale nie zbiega się (czekam 10 minut lub dłużej). Myślę, że h jest rozsądny. Zastanawiam się, czy właściwie modelowałem g. Innymi słowy, czy jest możliwe, że moja funkcja A * dociera do węzła na wykresie ścieżką, która nie jest najkrótszą ścieżką?

Może nie czekałem wystarczająco długo? Może 10 minut to za mało?

Dla w pełni losowego układu (przy założeniu braku problemów z parzystością), jaka jest średnia liczba permutacji, którą przeanalizuje rozwiązanie A *? (proszę pokazać matematykę)

Zamierzam szukać błędów logicznych w moim kodzie, ale w międzyczasie, jakieś wskazówki?

(ps: odbywa się w Javascript).

Poza tym, nie, to nie jest praca domowa CompSci. To tylko osobista eksploracja. Próbuję tylko nauczyć się Javascript.

EDYTOWAĆ: Odkryłem, że czas wykonywania zależy w dużym stopniu od heurystyki. Widziałem czynnik 10x zastosowany do heurystyki z artykułu, o którym ktoś wspomniał, i zastanawiałem się - dlaczego 10x? Dlaczego liniowy? Ponieważ jest to wykonywane w javascript, mogę zmodyfikować kod, aby dynamicznie aktualizować tabelę html z aktualnie rozważanym węzłem. Pozwoliło mi to zajrzeć do algorytmu w miarę jego postępu. Przy zwykłej heurystyce odległości taksówki obserwowałem, jak nie zbiegła się.

W górnym rzędzie było 5 i 12, a oni ciągle się kręcili. Zobaczyłbym, że 1,2,3,4 skrada się w górnym rzędzie, ale potem odpadną, a inne numery będą się tam przesuwać. To, co miałem nadzieję zobaczyć, to 1,2,3,4, rodzaj skradania się do góry, a następnie pozostawania tam.

Pomyślałem sobie - to nie jest sposób, w jaki osobiście to rozwiązuję. Robiąc to ręcznie, rozwiązuję górny wiersz, następnie 2ne wiersze, a następnie trzeci i czwarty wiersz, sortując jednocześnie.

Tak więc poprawiłem funkcję h (x), aby bardziej obciążyć wyższe wiersze i kolumny „lefter”. W wyniku tego A * zbiegło się znacznie szybciej. Teraz działa w ciągu 3 minut zamiast „w nieskończoność”. Z „podglądem”, o którym mówiłem, widzę, że mniejsze liczby pełzają do wyższych rzędów i pozostają tam. Nie tylko wydaje się to właściwe, ale działa znacznie szybciej.

Jestem w trakcie wypróbowywania wielu odmian. Wydaje się całkiem jasne, że środowisko wykonawcze A * jest bardzo wrażliwe na heurystykę. Obecnie najlepsza heurystyka, jaką znalazłem, wykorzystuje sumowaniedislocation * ((4-i) + (4-j)) gdzie i i j to wiersz i kolumna, a przemieszczenie to odległość taksówki.

Jedna interesująca część wyniku, którą otrzymałem: przy szczególnej heurystyce znajduję ścieżkę bardzo szybko, ale oczywiście nie jest to najkrótsza ścieżka. Myślę, że to dlatego, że ważę heurystykę. W jednym przypadku dostałem ścieżkę 178 kroków na 10s. Mój własny wysiłek fizyczny daje rozwiązanie w 87 ruchach. (o wiele więcej niż 10s). Więcej dochodzenia uzasadnione.

Rezultat jest taki, że widzę, że zbiega się szybciej, a ścieżka zdecydowanie nie jest najkrótsza. Muszę o tym pomyśleć więcej.

Kod:

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

questionAnswers(8)

yourAnswerToTheQuestion