“邻居函数”优化使用A * -Algorithm解决8-Puzzle

I found the A*-Algorithm and I want to use it to find the optimal solution for an 8-Puzzle.

我找到了A * -Algorithm,我想用它来找到8-Puzzle的最佳解决方案。

Like in the picture the puzzle looks like:

就像图片中的拼图一样:

0 1 2
3 4 5
6 7 8

and is represented as an array: 0 1 2 3 4 5 6 7 8

并表示为数组:0 1 2 3 4 5 6 7 8

The "Neighbor-function" returns all neighbors of an array-index. Neighbors are all numbers that are one field vertical or horizontal away from the array-index.

“Neighbor-function”返回数组索引的所有邻居。邻居是距离数组索引垂直或水平一个字段的所有数字。

Example: Neighbor(4) would return 1,5,7,3 and Neighbor(6) would return 3,7

示例:Neighbor(4)将返回1,5,7,3而Neighbor(6)将返回3,7

My current solution (coded by Uwe Raabe):

我目前的解决方案(由Uwe Raabe编码):

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;

I am looking for a compact and better solution. I would love to see something algorithmic. I don't like the if's ect. The programming language doesn't really matter as long as it's portable to one of these: C/C++/Delphi/C#

我正在寻找一个紧凑和更好的解决方案。我很想看到一些算法。我不喜欢if等。编程语言并不重要,只要它可以移植到其中一个:C / C ++ / Delphi / C#

Thanks in advance!

提前致谢!

3 个解决方案

#1

Using Delphi XE7 or newer a look-up table solution is compact:

使用Delphi XE7或更新的查找表解决方案是紧凑的:

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;

It is unlikely that you will find an algorithm that is more compact than the one given in your question. Even if you consider if statements ugly, they are effective and a central part of every (almost) programming language.

您不太可能找到比您的问题中给出的算法更紧凑的算法。即使您认为陈述是丑陋的,它们也是有效的,并且是每种(几乎)编程语言的核心部分。

Or use a set as proposed by the OP:

或者使用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;

#2

As mentioned in the comments, all you need is a look-up table. The number of neighbors is not constant, so you need a way to know how many neighbors each square has. This can be done with a sentinel value as shown below

正如评论中所提到的,您只需要一个查找表。邻居的数量不是恒定的,因此您需要一种方法来了解每个方块有多少邻居。这可以通过如下所示的标记值来完成

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

Note that the lookup table can be coded by hand, or auto-generated at startup by the code you already have.

请注意,查找表可以手动编码,也可以在启动时通过您已有的代码自动生成。

#3

These replies focus on the static x and y sizes of the matrix... if you're interested in algorythmics, you might as well make them variable:

这些回复集中在矩阵的静态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;

#1