巨大迷宮的最短路徑（巨大）

我需要解決一個最短路徑算法問題（在C中）。巨大迷宮的最短路徑（巨大）

基本上我給了一個文件，其中包含一個（稀疏）矩陣的行和列的總數，非零條目的數目（稱爲門），最後這些條目的位置和值（行，列，值）。在這個迷宮中，我必須找出從條目（0,0）到任何其他點（位置也從文件中讀取）的「最便宜」路徑。每當我跨過一扇門，成本就會增加，而零的單元也不會付出任何代價。

有一些規則就像你不能通過連續的兩個或更多的門，某些值爲-1的門不能通過。最後，我必須打印通過槽的門的位置（文件中給出的）。不管我劃過多少個空單元格都沒關係。

總之，這裏的問題是，矩陣可以10⁵*10⁵或更多...我存儲在所謂的稀疏矩陣我猜非零條目，它的工作原理：

typedef struct node { 
    struct node* down; 
    struct node* right; 

    long int PL, PC, PV; 
}node ; 

typedef struct _Mat{ 
    long int NL, NC,P,x,y; //Number of lines,columns,non zero cells, and position of destination 
    node** rowList; 
    node** colList;   
}Mat

事情是我無法弄清楚下一步該做什麼。僅憑這種結構，我認爲我不能解決迷宮問題。

我應該創建一個矩陣圖（包括零），所以之後我可以應用像DiJkstras算法？我認爲這必須通過圖表來解決，但圖表將會非常龐大......其他理念是將一大羣非零單元組合在一起，並將它們視爲一個節點。這種方式圖形較小，但我不知道如何做到這一點。

如果這是最好的解決方案，我該如何實現它？還是我完全錯了？我的數據結構是無用的嗎？

來源

2013-11-28 user3045786

你做了什麼研究嗎？ http://en.wikipedia.org/wiki/Maze_solving_algorithm – ravenspoint

我認爲OPs問題是實現這個稀疏矩陣，而不是圖。 – Mailerdaimon

也許A *可以幫助你：

http://www.policyalmanac.org/games/aStarTutorial.htm

該算法可以找到一個圖，您可以將您的迷宮最優路徑。

來源

2013-11-28 13:28:38 Patrik

感謝您的信息。那麼在這個特殊情況下，A *會比Dijktras更適合（考慮一個巨大的矩陣）？ – user3045786

是的，它更適合。 A *是Dijstra的推廣。有一個啓發式搜索指南，可顯着加快算法速度。 – Patrik

巨大迷宮的最短路徑（巨大）

回答

相關問題