2012-06-03 85 views
0

我的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而不是其他路徑尋找算法的原因是我想將深度更改爲指定的數字以搜索確切長度的路徑(但我不確定這是否會起作用)。


如果有人會建議使用其他算法找到指定長度的路徑使用鄰接矩陣,請讓我知道它。

回答

1

從路徑查找算法中獲取實際路徑的想法是使用map:V->V,這樣的關鍵是一個頂點,並且該值是用於發現密鑰的頂點(源不會是密鑰,或者成爲null值的關鍵,因爲它不是從任何頂點發現的)。

路徑查找算法將在運行時修改此地圖,並且完成後 - 您可以通過迭代地從表格中讀取 - 從目標開始 - 一直到源文件 - 從而獲得您的路徑路徑按相反順序排列。

DFS:每當您發現一個新的頂點(即key)時,您插入(key,value)對。請注意,如果key已經是地圖中的關鍵字 - 則應跳過此分支。
一旦你完成探索某個路徑,並「關閉」一個頂點,你需要把它從列表中刪除,但是 - 有時你可以優化算法並跳過這個部分(它會使分支因子變小)。由於IDDFS實際上是以迭代方式執行DFS,所以您可以按照相同的邏輯進行操作,並且每次進行新的DFS迭代時 - 爲了獲得更高的深度,您可以清除舊的地圖,並從頭開始新的地圖。

其他尋路算法是BFS,A*dijkstra's algorithm。請注意,最後2個也適用於加權圖。所有這些可以在達到一定深度時終止,與在IDDFS中達到特定深度時終止DFS一樣。

+0

但我想沒有最短的路徑,但更長。我會給算法指定的路徑長度,它應該爲我找到這樣一個。我不知道如何使用這些算法來解決這個問題。 –