有一個二維數組，0表示路，-1表示墻，求其中任意兩點的最短路徑。
我們先看，怎么求一條路徑：求兩點路徑是一個數據結構上的典型的迷宮問題，很多數據結構的書上都有介紹，解決辦法如下：
從一點開始出發，向四個方向查找，每走一步，把走過的點的值+1(即本節點值+1)，防止重復行走，并把走過的點壓入堆棧(表示路徑)，如果遇到墻、或者已走過的點則不能前進，如果前方已經無路可走，則返回，路徑退棧，這樣遞歸調用，直到找到終點為止。
迷宮如下圖所示：
從(2, 1)到(6, 8)，程序如下所示：
struct Postion
{
int _X, _Y;
Postion(){}
Postion(int X, int Y)
: _X(X), _Y(Y){}
};
bool isCanGo(const int prePosValue,
const int posX,
const int posY)
{
if ( posX < 0 || posX > 9 // 越界
|| posY < 0 || posY > 9
|| maze[posX][posY] == -1 // 墻
|| maze[posX][posY] >= 1) // 走過
{
return false;
}
return true;
}
stack<Postion> path__; //路徑
Postion offset[4]; //路徑
bool shortestPath(stack<Postion> &path,
const Postion &start,
const Postion &end)
{
if ( start._X == end._X
&& start._Y == end._Y)
{
path__ = path;
return true;
}
for (int i = 0; i < 4; i++)
{
int nNextPos_X = start._X + offset[i]._X;
int nNextPos_Y = start._Y + offset[i]._Y;
if (isCanGo(maze[start._X][start._Y], nNextPos_X, nNextPos_Y))
{
maze[nNextPos_X][nNextPos_Y] = maze[start._X][start._Y] + 1;
path.push(Postion(nNextPos_X, nNextPos_Y));
if (shortestPath(path, Postion(nNextPos_X, nNextPos_Y), end))
return true;
path.pop();
}
}
return false;
}
int main(int argc, char* argv[])
{
offset[0]._X = -1; offset[0]._Y = 0; // 上
offset[1]._X = 1; offset[1]._Y = 0; // 下
offset[2]._X = 0; offset[2]._Y = -1; // 左
offset[3]._X = 0; offset[3]._Y = 1; // 右
printMat(maze);
Postion start(2, 1), end(6, 8);
maze[start._X][start._Y] = 1; // 置起點值1, 防止走回起點
shortestPath(stack<Postion>(), start, end);
printPath(path__);
printMat(maze);
return 0;
}
這時，我們經過運算，到達終點，有44步之多。如果我們調整調用offset的順序，即先左右，后上下，可能會得到更短的路徑，但無法確保在任何情況下都能得到最短路徑。
得到最短路徑的方法，解決方法如下：
每走一步，就對前方的節點賦值為此節點+1，走過的路徑也可以重復行走。但有一個條件，就是本節點+1必須小于已走過的節點的權值(墻不能走)，這樣走遍所有的節點，記錄最短的路徑。
主要修改了以下兩個函數：
bool isCanGo(const int prePosValue,
const int posX,
const int posY)
{
if ( posX < 0 || posX > 9 // 越界
|| posY < 0 || posY > 9
|| maze[posX][posY] == -1) // 墻
{
return false;
}
if (maze[posX][posY] == 0) // 未走過
return true;
else // 更近的路徑
return (prePosValue + 1) < maze[posX][posY];
}
void shortestPath(stack<Postion> &path,
const Postion &start,
const Postion &end)
{
if ( start._X == end._X
&& start._Y == end._Y)
{
if (path.size() < path__.size() || path__.empty()) // 更短的路徑
path__ = path;
return;
}
for (int i = 0; i < 4; i++)
{
int nNextPos_X = start._X + offset[i]._X;
int nNextPos_Y = start._Y + offset[i]._Y;
if (isCanGo(maze[start._X][start._Y], nNextPos_X, nNextPos_Y))
{
maze[nNextPos_X][nNextPos_Y] = maze[start._X][start._Y] + 1;
path.push(Postion(nNextPos_X, nNextPos_Y));
shortestPath(path, Postion(nNextPos_X, nNextPos_Y), end);
path.pop();
}
}
}
我上傳了兩個工程，求一條路徑的程序點此下載，求最短路徑的程序點此下載。
文章結束！愿它對您有所幫助。
posted on 2008-03-18 17:47
胡滿超 閱讀(8883)
評論(4) 編輯 收藏 引用