我需要使用回溯法解決迷宮問題。我的迷宮有 0 個列為墻，1 個列為空單元，2 個用于訪問，3 個??用于龍。龍基本上是我可以通過的障礙，但我需要選擇最少的龍的路徑。到目前為止，我可以解決迷宮并標記一條路徑，但我似乎想不出一種相對簡單的方法來找到龍最少的路徑。請注意，我們剛剛開始在我的 uni 中使用 C 進行編碼（到目前為止，我只完成了 java/bash/一些 python），所以我對 C 和一般演算法真的很陌生。
代碼如下。
#include <stdio.h>
#define IMPOSSIBLE (N*N 1)
int counter=0;
enum {WALL,EMPTY,VISITED,DRAGON,N};
int printMaze(int maze[N][N])
{
for (int i = 0; i < N; i) {
for (int j = 0; j < N; j) {
printf("%d ",maze[i][j]);
}
printf("\n");
}
}
int solveMaze(int maze[N][N], int i, int j)
{
if (maze[i][j] == WALL){ return 0; } // If [i][j] are currently a wall (0).
if (maze[i][j] == VISITED) { return 0; } // If [i][j] are currently a mark (2).
if (maze[i][j] == DRAGON) { counter ; }
maze[i][j] = VISITED; // Mark current spot with (2).
if (i==N-1 && j==N-1) { return 1; } // reached the end (N-1,N-1) - (3,3) incase N is 4.
if ( ((i < N-1) && solveMaze(maze,i 1,j)) || ((i > 0) && solveMaze(maze,i-1,j)) || ((j < N-1) && solveMaze(maze,i,j 1)) || ((j > 0) && solveMaze(maze,i,j-1)) ) { // checking index-out-bounds recursively going around the maze
return 1;
}
maze[i][j] = EMPTY;
return 0;
}
int main() {
int maze[N][N] = { {1,1,3,3},
{3,0,1,1},
{3,0,0,1},
{1,3,3,1} };
int solved = solveMaze(maze, 0, 0);
if (solved)
{
printMaze(maze);
printf("Amount of dragons passed through in the maze: %d\n",counter);
}
else
{
printf("No solution, %d\n",IMPOSSIBLE);
}
}
我嘗試創建一個計數器來計算路上的龍數量，但我想我在遞回方面不夠流暢，無法讓它進入每條可用路徑并選擇最佳路徑。
uj5u.com熱心網友回復：
您似乎了解使用回溯遞回遍歷樹的想法。問題是您不僅需要找到一條路徑，還需要找到成本最低的路徑——即最少的龍。這意味著一般來說，您不能在找到的第一條路徑上停下來。您需要繼續前進，直到可以確定沒有更好的路徑為止。
這是一種方法：
維護一個變數來跟蹤迄今為止發現的最佳路徑上的龍數量。將其初始化為大于可沿任何路徑出現的值的值——
IMPOSSIBLE例如，您的 或INT_MAX。這與您目前正在探索的路徑上到目前為止遇到的龍的數量不同。像您已經在做的那樣執行遞回遍歷，除了
counter當您從龍節點回溯時，修復示例代碼在恢復狀態（節點內容和值）方面的問題。- 當沿這條路徑遇到的龍的數量等于迄今為止發現的最佳路徑上的龍的數量時，停止探索任何給定路徑。
- 根據前文，您可以確定，每當您發現一條到達出口的路徑時，該路徑的龍數量少于之前發現的最佳路徑（如果有的話）。相應地更新跟蹤最佳龍數量的變數。請注意，這不一定會結束搜索，但它可能會減少仍有待探索的搜索空間。
uj5u.com熱心網友回復：
解決這個問題的一種方法是將迷宮想象成 3 維圖形而不是 2D。你有三元組 (i, j, number_of_dragons) 定義圖的節點。請注意，這在極端情況下可能意味著節點數為 N^4。因此，您將需要一個大小為 [N][N][N*N] 的陣列來存盤是否訪問了給定節點（請注意，龍和墻仍然可以存盤在 [N][N] 陣列中）。要獲得從源到目標的最小路徑，只需遍歷 [target.x][target.y][i] 的值并回傳您訪問該節點的最小 i。
我可以使用像 Dijkstra 這樣的最小路徑圖演算法來提出更好的解決方案，但這似乎超出了問題的范圍。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/533950.html
標籤：C递归回溯迷宫