騎士之旅，計算從A到B所需的步驟

Question

騎士位於（a，b）位置，需要坐落在（c，d）的國王。我怎樣才能：

答：可視化的旅遊

B：從計算（A，B）至（c，d）去所需的最小步驟

我已經找到了實現基本騎士在棋盤上的一系列移動，以至於騎士只能訪問每個方格一次，但我想要更具體一些，並且步入特定位置。

我應該尋找什麼樣的算法或策略？

我正在考慮使用python

Answer 1

您可以使用BFS算法來實現上述目的。只需緩存訪問的位置，以免多次訪問某個職位。現在，無論何時您訪問目標時，您將在每個完整迭代中採取的最小步驟數量，只是探索1度分離。

假設N X M棋盤上的棋盤代表棋盤上的每個棋盤並在其上應用BFS。

class Point{ 
     int x; 
     int y; 
     int dist; 
} 

public int knight(int N, int M, int x1, int y1, int x2, int y2) { 
      Point source = new Point(x1, y1); 
      Point destination = new Point(x2, y2); 

      Queue<Point> q = new LinkedList<>(); 
      q.add(source); 
      Set<Point> hset = new HashSet<>(); 
      hset.add(source); 
      int[][] dir = {{1, 2}, {-1, 2}, {1, -2}, {-1, -2}, {2, 1}, {-2, 1}, {2, -1}, {-2, -1}}; 
      while(!q.isEmpty()){ 
       Point p = q.poll(); 

       if(p.equals(destination)){ 
        return p.dist; 
       } 

       for(int[] d : dir){ 

        int row = p.x + d[0]; 
        int col = p.y + d[1]; 
        Point temp = new Point(row, col); 
        if(row <= 0 || col <= 0 || row > N || col > M || hset.contains(temp)){ 
         continue; 
        } 
        temp.dist = p.dist + 1; 

        q.add(temp); 
        hset.add(temp); 

       } 

      } 

      return -1; //unreachable point from source position 
} 

可視化巡視會簡單得多，只需使用ArrayList等來存儲所遍歷的路徑。 另一種方法可能是將Dijkstra算法用於上述。

Answer 2

找到Knight遊覽問題的準確解決方案的最佳方法是使用Backtracking算法。看看你可以選擇的所有可能的步驟（a，b）選擇第一個步驟，然後繼續前進，直到找到死路。

如果死衚衕發生，向後退一步並探索其他選項。

這是DFS（深度優先Searh）的示例