logo标签列表

国王在棋盘上的最短路径

algorithmpascalshortest-pathdirected-acyclic-graphs
3
我有一个8x8的棋盘。这是我得到的信息:
- 国王的坐标 - 目标的坐标 - 被阻挡的方格数量 - 被阻挡的方格的坐标
我不能踩在被阻挡的方格上。我想找到到达目标的最短路径，如果没有可用的路径(即目标不可达)，则返回-1。
我试着写代码，但我不确定代码是否有意义，而且我有点迷失方向，非常感谢任何帮助。
Program ShortestPath;

TYPE 
    coords = array [0..1] of integer;

var goal,shortest : coords;
    currentX, currentY,i : integer;
    arrBlocked,result : array [0..64] of coords;

function findShortestPath (currentX, currentY, goal, arrBlocked,path,i) : array [0..64] of coords;
begin
    {check if we are still on board}
    if (currentX < 1 OR currentX > 8 OR currentY < 1 OR currentY > 8) then begin
        exit;
    end;
    if (currentX = arrBlocked[currentX] AND currentY = arrBlocked[currentY]) then begin
        exit;
    end;
    {save the new square into path}
    path[i] = currentX;
    path[i+1] = currentY;
    {check if we reached the goal}
    if (currentX = goal[0]) and (currentY = goal[1]) then begin
        {check if the path was the shortest so far}
        if (shortest > Length(path)) then begin
            shortest := Length(path);
            findShortestPath := path;
        end else begin
            exit;
        end;
    end else begin
        {move on the board}
        findShortestPath(currentX+1, currentY, goal, arrBlocked,path,i+2);
        findShortestPath(currentX, currentY+1, goal, arrBlocked,path,i+2);
        findShortestPath(currentX-1, currentY, goal, arrBlocked,path,i+2);
        findShortestPath(currentX, currentY-1, goal, arrBlocked,path,i+2);
    end;
end;

begin
    {test values}
    currentX = 2; 
    currentY = 5;
    goal[0] = 8;
    goal[1] = 7;
    arrBlocked[0] = [4,3];
    arrBlocked[1] = [2,2];
    arrBlocked[2] = [8,5];
    arrBlocked[3] = [7,6];
    i := 0;
    shortest := 9999;
    path[i] = currentX;
    path[i+1] = currentY;
    i := i + 2;
    result := findShortestPath(currentX,currentY,goal,arrBlocked,path,i);
end.
1
查找BFS算法，这将是解决此问题的自然方式。 - interjay
4个回答
3
在当前情况下（只有64个单元格的小棋盘），可以通过以下方式无需递归解决任务。
Program ShortestPath;
type
  TCoords = record
    X, Y: byte;
  end;

  TBoardArray = array [0 .. 63] of TCoords;

var
  Goal: TCoords;
  Current: TCoords;
  i, j: integer;
  ArrBlocked, PathResult: TBoardArray;
  BlockedCount: byte;
  Board: array [1 .. 8, 1 .. 8] of integer;

procedure CountTurnsToCells;
var
  Repetitions: byte;
  BestPossible: byte;
begin
  for Repetitions := 1 to 63 do
    for j := 1 to 8 do
      for i := 1 to 8 do
        if Board[i, j] <> -2 then
        begin
          BestPossible := 255;
          if (i < 8) and (Board[i + 1, j] >= 0) then
            BestPossible := Board[i + 1, j] + 1;
          if (j < 8) and (Board[i, j + 1] >= 0) and
            (BestPossible > Board[i, j + 1] + 1) then
            BestPossible := Board[i, j + 1] + 1;
          if (i > 1) and (Board[i - 1, j] >= 0) and
            (BestPossible > Board[i - 1, j] + 1) then
            BestPossible := Board[i - 1, j] + 1;
          if (j > 1) and (Board[i, j - 1] >= 0) and
            (BestPossible > Board[i, j - 1] + 1) then
            BestPossible := Board[i, j - 1] + 1;
          { diagonal }
          if (j > 1) and (i > 1) and (Board[i - 1, j - 1] >= 0) and
            (BestPossible > Board[i - 1, j - 1] + 1) then
            BestPossible := Board[i - 1, j - 1] + 1;
          if (j > 1) and (i < 8) and (Board[i + 1, j - 1] >= 0) and
            (BestPossible > Board[i + 1, j - 1] + 1) then
            BestPossible := Board[i + 1, j - 1] + 1;
          if (j < 8) and (i < 8) and (Board[i + 1, j + 1] >= 0) and
            (BestPossible > Board[i + 1, j + 1] + 1) then
            BestPossible := Board[i + 1, j + 1] + 1;
          if (j < 8) and (i > 1) and (Board[i - 1, j + 1] >= 0) and
            (BestPossible > Board[i - 1, j + 1] + 1) then
            BestPossible := Board[i - 1, j + 1] + 1;

          if (BestPossible < 255) and
            ((Board[i, j] = -1) or (Board[i, j] > BestPossible)) then
            Board[i, j] := BestPossible;
        end;
end;

function GetPath: TBoardArray;
var
  n, TurnsNeeded: byte;
  NextCoord: TCoords;

  function FindNext(CurrentCoord: TCoords): TCoords;
  begin
    result.X := 0;
    result.Y := 0;

    if (CurrentCoord.X > 1) and (Board[CurrentCoord.X - 1, CurrentCoord.Y] >= 0)
      and (Board[CurrentCoord.X - 1, CurrentCoord.Y] < Board[CurrentCoord.X,
      CurrentCoord.Y]) then
    begin
      result.X := CurrentCoord.X - 1;
      result.Y := CurrentCoord.Y;
      exit;
    end;

    if (CurrentCoord.Y > 1) and (Board[CurrentCoord.X, CurrentCoord.Y - 1] >= 0)
      and (Board[CurrentCoord.X, CurrentCoord.Y - 1] < Board[CurrentCoord.X,
      CurrentCoord.Y]) then
    begin
      result.X := CurrentCoord.X;
      result.Y := CurrentCoord.Y - 1;
      exit;
    end;

    if (CurrentCoord.X < 8) and (Board[CurrentCoord.X + 1, CurrentCoord.Y] >= 0)
      and (Board[CurrentCoord.X + 1, CurrentCoord.Y] < Board[CurrentCoord.X,
      CurrentCoord.Y]) then
    begin
      result.X := CurrentCoord.X + 1;
      result.Y := CurrentCoord.Y;
      exit;
    end;

    if (CurrentCoord.Y < 8) and (Board[CurrentCoord.X, CurrentCoord.Y + 1] >= 0)
      and (Board[CurrentCoord.X, CurrentCoord.Y + 1] < Board[CurrentCoord.X,
      CurrentCoord.Y]) then
    begin
      result.X := CurrentCoord.X;
      result.Y := CurrentCoord.Y + 1;
      exit;
    end;
    { diagonal }
    if (CurrentCoord.X > 1) and (CurrentCoord.Y > 1) and
      (Board[CurrentCoord.X - 1, CurrentCoord.Y-1] >= 0) and
      (Board[CurrentCoord.X - 1, CurrentCoord.Y-1] < Board[CurrentCoord.X,
      CurrentCoord.Y]) then
    begin
      result.X := CurrentCoord.X - 1;
      result.Y := CurrentCoord.Y - 1;
      exit;
    end;

    if (CurrentCoord.X < 8) and (CurrentCoord.Y > 1) and
      (Board[CurrentCoord.X + 1, CurrentCoord.Y-1] >= 0) and
      (Board[CurrentCoord.X + 1, CurrentCoord.Y-1] < Board[CurrentCoord.X,
      CurrentCoord.Y]) then
    begin
      result.X := CurrentCoord.X + 1;
      result.Y := CurrentCoord.Y - 1;
      exit;
    end;

    if (CurrentCoord.X < 8) and (CurrentCoord.Y < 8) and
      (Board[CurrentCoord.X + 1, CurrentCoord.Y+1] >= 0) and
      (Board[CurrentCoord.X + 1, CurrentCoord.Y+1] < Board[CurrentCoord.X,
      CurrentCoord.Y]) then
    begin
      result.X := CurrentCoord.X + 1;
      result.Y := CurrentCoord.Y + 1;
      exit;
    end;

    if (CurrentCoord.X > 1) and (CurrentCoord.Y < 8) and
      (Board[CurrentCoord.X - 1, CurrentCoord.Y+1] >= 0) and
      (Board[CurrentCoord.X - 1, CurrentCoord.Y+1] < Board[CurrentCoord.X,
      CurrentCoord.Y]) then
    begin
      result.X := CurrentCoord.X - 1;
      result.Y := CurrentCoord.Y + 1;
      exit;
    end;

  end;

begin
  TurnsNeeded := Board[Goal.X, Goal.Y];
  NextCoord := Goal;
  for n := TurnsNeeded downto 1 do
  begin
    result[n] := NextCoord;
    NextCoord := FindNext(NextCoord);
  end;
  result[0] := NextCoord; // starting position
end;

procedure BoardOutput;
begin
  for j := 1 to 8 do
    for i := 1 to 8 do
      if i = 8 then
        writeln(Board[i, j]:2)
      else
        write(Board[i, j]:2);
end;

procedure OutputTurns;
begin
  writeln(' X Y');
  for i := 0 to Board[Goal.X, Goal.Y] do
    writeln(PathResult[i].X:2, PathResult[i].Y:2)
end;

begin
  { test values }
  Current.X := 2;
  Current.Y := 5;
  Goal.X := 8;
  Goal.Y := 7;
  ArrBlocked[0].X := 4;
  ArrBlocked[0].Y := 3;
  ArrBlocked[1].X := 2;
  ArrBlocked[1].Y := 2;
  ArrBlocked[2].X := 8;
  ArrBlocked[2].Y := 5;
  ArrBlocked[3].X := 7;
  ArrBlocked[3].Y := 6;
  BlockedCount := 4;

  { preparing the board }
  for j := 1 to 8 do
    for i := 1 to 8 do
      Board[i, j] := -1;

  for i := 0 to BlockedCount - 1 do
    Board[ArrBlocked[i].X, ArrBlocked[i].Y] := -2; // the blocked cells

  Board[Current.X, Current.Y] := 0; // set the starting position

  CountTurnsToCells;
  BoardOutput;

  if Board[Goal.X, Goal.Y] < 0 then
    writeln('no path') { there is no path }

  else
  begin
    PathResult := GetPath;
    writeln;
    OutputTurns
  end;

  readln;

end.

思路如下。我们使用一个表示棋盘的数组。每个单元格可以设置为0-起点，-1-未知/无法到达的单元格，或-2-阻塞的单元格。所有正数表示从起点到当前单元格所需的最小步数。
接下来，我们检查目标单元格是否包含大于0的数字。这意味着国王可以移动到目标单元格。如果是这样，我们找到从目标到起点依次跟随的序号单元格，并在决策数组中表示它们。
两个额外的过程：BoardOutput和OutputTurns将Board结构和决策打印到控制台。
2
很有趣，想知道为什么要对答案进行投反对票？我猜这样的“反对者”至少可以写一个评论。 - asd-tm
有趣的解决方案，我修复了语法错误，看起来它可以工作，我会再试一下并尝试理解它，谢谢 :) - Mykybo
@Mykybo，我已经更正了答案，使其能够检查对角线移动。 - asd-tm
2

由于您的问题规模很小，因此您不必使用最有效的方法。因此，您可以使用BFS查找最短路径，因为首先移动的成本是一致的，其次由于问题规模较小，您不会面临内存限制。

 1 Breadth-First-Search(Graph, root):
 2 
 3     for each node n in Graph:            
 4         n.distance = INFINITY        
 5         n.parent = NIL
 6 
 7     create empty queue Q      
 8 
 9     root.distance = 0
10     Q.enqueue(root)                      
11 
12     while Q is not empty:        
13     
14         current = Q.dequeue()
15     
16         for each node n that is adjacent to current:
17             if n.distance == INFINITY:
18                 n.distance = current.distance + 1
19                 n.parent = current
20                 Q.enqueue(n)

https://en.wikipedia.org/wiki/Breadth-first_search

但是当问题变得更加复杂时，你需要使用更高效的方法。最终解决方案是使用IDA*算法。因为IDA*的空间复杂度是线性的，并且如果使用一致的启发式函数，它将始终返回最优解。

0

A* Search是一种适用于像象棋棋盘这样的图形的好的路径查找算法，通过搜索最有希望的路径来找到最佳路径，采用可允许启发式方法确定哪些路径是（可能）最好的。也就是说，搜索首先探索通往目标的最直接路径，只有在直接路径被阻止时才探索更曲折的路径。在你的情况下，你可以用笛卡尔距离作为启发式，或者你可以使用切比雪夫距离，又称为棋盘距离。

一些简单的搜索代码可以在C语言实现的程序中找到，你可以将其改编成Pascal版本。

0

你可以将这个问题转化为图论问题，然后应用其中一个标准算法。

在一个图中，考虑棋盘上所有的格子作为节点。对于给定的一个格子x，所有国王可以移动到的格子y都与x相连。例如c4与b3、b4、b5、c3、c5、d3、d4、d5相连。删除所有被阻挡的节点及其连接。

现在，可以使用Dijkstra算法来解决最短路径问题。

这基本上就是@asd-tm在他/她的解决方案中实现的内容，但我认为为一般情况实现Dijkstra算法并将其用于特殊情况可能会导致更清晰、更易于理解的代码。因此，这是一个单独的答案。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接