國王在棋盤上的最短路徑

Question

我有一個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. 

Answer 1

當前情況下的任務（僅包含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. 

ideea是以下內容。我們使用代表董事會的數組。每個單元格可以設置爲0 - 起始點，可以是-1 - 未知/無法訪問的單元格，也可以設置爲-2 - 阻止的單元格。所有正數表示從起點到達當前單元的最小轉數。

稍後我們檢查目標單元格是否包含大於0的數字。這表示國王可以移動到目標單元格。如果是這樣，我們從目標到起點找到序數相同的單元格，並將它們表示在決策數組中。

這兩個附加程序：BoardOutput和OutputTurns將控制檯的結構和決定打印出來。

Answer 2

A* Search是喜歡你的國際象棋棋盤，有點谷歌搜索所在的implementation in C，你能適應帕斯卡爾圖形良好的尋路算法。

A *通過首先使用admissible heuristic探索最有前途的路徑來確定哪些路徑（可能）是最好的，即搜索首先探索到達目標的最直接路徑，並且如果直接路徑探索更多迂迴路徑被阻止。在你的情況下，你可以使用笛卡爾距離作爲啓發式，否則你可以使用Chebyshev distance又名棋盤距離。

Answer 3

由於問題的尺寸太小，因此您不一定會使用最有效的方法。因此，您可以使用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 *空間複雜性是線性的，並且如果您使用一致的heurisitc，它將始終返回最佳解決方案。

Answer 4

您可以轉換這個圖論的問題，然後應用其中一種標準算法。

您可以考慮圖形中棋盤節點的所有字段。國王可以從一個給定的領域x移動到的所有領域都連接到x。所以c4連接到b3，b4，b5，c3，c5，d3，d4，d5。刪除所有被阻塞的節點及其連接。

現在發現你的最短路徑，可以使用Dijkstras Algorithm

這基本上就是@ ASD-TM在他/她的解決方案實現是可以解決的，但我想實現的Dijkstra算法一般情況下，並使用它的特殊情況可能會導致更清晰，更易於理解的代碼。因此，單獨的答案。