„Nachbar-Funktion“ Optimierung 8-Puzzle mit A * -Algorithmus zu lösen

Question

fand ich die A*-Algorithm und ich möchte es verwenden, um die optimale Lösung für eine 8-Puzzle zu finden.

wie im Bild das Puzzle wie folgt aussieht:

0 1 2 
3 4 5 
6 7 8 

und ist als eine Anordnung dargestellt ist: 0 1 2 3 4 5 6 7 8

Die "Nachbar-Funktion" gibt alle Nachbarn ein Array-Index. Nachbarn sind alle Zahlen, die ein Feld vertikal oder horizontal vom Array-Index entfernt sind.

Beispiel: Neighbor (4) zurückkehren würde und 1,5,7,3 Nachbar (6) 3,7

Meine aktuelle Lösung (codiert durch Uwe Raabe) zurückkehren würde:

function Neighbours(zahl: Integer): TArray<Integer>; 
var 
    lst: TList<Integer>; 
    c: Integer; 
    r: Integer; 
begin 
    lst := TList<Integer>.Create; 
    try 
    c := zahl mod 3; 
    r := zahl div 3; 
    if r > 0 then 
     lst.Add(zahl-3); 
    if c > 0 then 
     lst.Add(zahl-1); 
    if c < 2 then 
     lst.Add(zahl+1); 
    if r < 2 then 
     lst.Add(zahl+3); 
    result := lst.ToArray; 
    finally 
    lst.Free; 
    end; 
end; 

Ich bin auf der Suche nach einer kompakten und besseren Lösung. Ich würde gerne etwas algorithmisches sehen. Ich mag das if's nicht. Die Programmiersprache ist nicht wirklich wichtig, solange es zu einem von diesen tragbar ist: C/C++/Delphi/C#

Vielen Dank im Voraus!

Answer 1

Mit Delphi XE7 oder neuer eine Look-up-Tabelle Lösung ist kompakt:

function Neighbours(number: Integer): TArray<Integer>; 
const 
    resCount: array[0..8] of Integer = (2,3,2,3,4,3,2,3,2); 
    resValue: TArray<TArray<Integer>> = [ 
    [1,3,-1,-1], 
    [0,2,4,-1], 
    [1,5,-1,-1], 
    [0,4,6,-1], 
    [1,3,5,7], 
    [2,4,8,-1], 
    [3,7,-1,-1], 
    [4,6,8,-1], 
    [5,7,-1,-1]]; 
begin 
    SetLength(Result,4); // Set default length 
    Result := resValue[number]; // Assign a solution vector 
    SetLength(Result,resCount[number]); // Correct result length 
end; 

Es ist unwahrscheinlich, dass Sie einen Algorithmus finden, die kompakter als die in Ihrer Frage gegeben ist. Selbst wenn Sie if Aussagen hässlich betrachten, sind sie effektiv und ein zentraler Bestandteil jeder (fast) Programmiersprache.

---

oder einen Satz, wie durch das OP vorgeschlagen:

Type 
    TMySet = set of 0..8; 

function Neighbours(number: Integer): TMySet; 
const 
    NeighboursA: array[0..8] of TMySet = 
    ([1,3], [0,2,4], [1,5], [0,4,6],[1,3,5,7], [2,4,8], [3,7], [4,6,8], [5,7]); 
begin 
    Result := NeighboursA[number]; 
end; 

Answer 2

Wie in den Kommentaren erwähnt, brauchen Sie nur eine Nachschlagetabelle. Die Anzahl der Nachbarn ist nicht konstant, Sie müssen also wissen, wie viele Nachbarn jedes Quadrat hat. Dies kann mit einem sentinel value erfolgen, wie unter

int neighbors[9][5] = { 
    { 1, 3,-1,-1,-1 }, 
    { 0, 2, 4,-1,-1 }, 
    // etc 
}; 

int main(void) 
{ 
    // get the list of neighbors for square 1 
    int *list = neighbors[1]; 

    // print the list of neighbors 
    for (int i = 0; list[i] >= 0; i++) 
     printf("%d\n", list[i]); 
} 

Hinweis gezeigt, dass die Lookup-Tabelle von Hand codiert werden kann, oder automatisch generierte beim Start durch den Code, den Sie bereits haben.

Answer 3

Diese Antworten konzentrieren sich auf die statischen x- und y-Größen der Matrix ... wenn Sie in algorythmics interessiert sind, könnten Sie machen Sie sie auch variabel:

function Neighbours(zahl: Integer; xSize,Ysize:integer): TArray<Integer>; 
var 
    lst: TList<Integer>; 
    x: Integer; 
    y: Integer; 
begin 
    lst := TList<Integer>.Create; 
    try 
    x := zahl mod xSize; 
    y := zahl div ySize; 
    if x > 0 then 
     lst.Add(zahl-1); 
    if x < (xSize - 1) then 
     lst.Add(zahl+1); 
    if y > 0 then 
     lst.Add(zahl-xSize); 
    if y < (ySize - 1) then 
     lst.Add(zahl+xSize); 
    result := lst.ToArray; 
    finally 
    lst.Free; 
    end; 
end;