A *アルゴリズムを使用して8パズルを解くための "近傍関数"の最適化

Question

A*-Algorithm が見つかりました。8-Puzzleの最適解を見つけるために使いたいと思います。

等が画像にパズルのように見える：

0 1 2 
3 4 5 
6 7 8 

アレイとして表される：0 1 2 3 4 5 6 7 8

"近隣関数" のすべてのネイバーを返します配列インデックス 隣人はすべて、array-indexから垂直または水平に1フィールド離れた番号です。

例：

：隣人（4）1,5,7,3及び隣接（6）（ウーヴェラーベによってコード）-3,7-

私の現在の解を返す返します

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; 

私は、よりコンパクトで優れたソリューションを探しています。私は何かアルゴリズムを見たいと思う。私は、もしかすると、好きではない。プログラミング言語は、C/C++/Delphi/C＃

のいずれかに移植可能であれば、実際問題はありません！

Answer 1

：

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; 

あなたがあなたの質問に与えられたものよりも、よりコンパクトであるアルゴリズムを見つけることはほとんどありません。 ifのステートメントは醜いとみなしても効果的であり、（ほぼ）プログラミング言語の中心的な部分です。

---

またはOPによって提案されたセットを使用します。

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

コメントに記載されているとおり、ルックアップテーブルだけが必要です。隣人の数は一定ではないので、各正方形にどれくらい多くの近隣があるかを知る方法が必要です。ルックアップテーブルは、あなたが既に持っているコードで、起動時に手でコード化された、または自動生成することができることを

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

注意の下に示すように、これはsentinel valueで行うことができます。ルックアップテーブルのソリューションは、コンパクトであるデルファイXE7以降を使用して

Answer 3

をこれらの応答は、行列の静的xとyの大きさに焦点を当てる...あなたはalgorythmicsに興味があるなら、あなたは可能性があります同様に変数を変更します。

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;