我的IDDFS算法使用鄰接矩陣找到我的圖的最短路徑。它顯示瞭解決方案有多深(我知道這是從起點到終點連接在一起的點的數量)。
我想獲得這些點數組。使用IDDFS創建路徑陣列
例如:
假設解決方案是在深度5找到的,所以我想要有點數組{{0,2,3,4,6})。
深度3:數組{1,2,3}。
這裏是C++算法:
(我不知道如果算法「知道」如果進行了走訪這點再次訪問了在搜索或不 - 我幾乎圖表初級)
int DLS(int node, int goal, int depth,int adj[9][9])
{
int i,x;
if (depth >= 0)
{
if (node == goal)
return node;
for(i=0;i<nodes;i++)
{
if(adj[node][i] == 1)
{
child = i;
x = DLS(child, goal, depth-1,adj);
if(x == goal)
return goal;
}
}
}
return 0;
}
int IDDFS(int root,int goal,int adj[9][9])
{
depth = 0;
solution = 0;
while(solution <= 0 && depth < nodes)
{
solution = DLS(root, goal, depth,adj);
depth++;
}
if(depth == nodes)
return inf;
return depth-1;
}
int main()
{
int i,u,v,source,goal;
int adj[9][9] = {{0,1,0,1,0,0,0,0,0},
{1,0,1,0,1,0,0,0,0},
{0,1,0,0,0,1,0,0,0},
{1,0,0,0,1,0,1,0,0},
{0,1,0,1,0,1,0,1,0},
{0,0,1,0,1,0,0,0,1},
{0,0,0,1,0,0,0,1,0},
{0,0,0,0,1,0,1,0,1},
{0,0,0,0,0,1,0,1,0}
};
nodes=9;
edges=12;
source=0;
goal=8;
depth = IDDFS(source,goal,adj);
if(depth == inf)printf("No solution Exist\n");
else printf("Solution Found in depth limit (%d).\n",depth);
system("PAUSE");
return 0;
}
我使用IDDFS而不是其他路徑尋找算法的原因是我想將深度更改爲指定的數字以搜索確切長度的路徑(但我不確定這是否會起作用)。
如果有人會建議使用其他算法找到指定長度的路徑使用鄰接矩陣,請讓我知道它。
但我想沒有最短的路徑,但更長。我會給算法指定的路徑長度,它應該爲我找到這樣一個。我不知道如何使用這些算法來解決這個問題。 –