我現在面臨一個難題矩陣路徑尋找最優算法：在不適合完全到內存
想象我有地圖是整個國家的，由細胞的一個巨大的矩陣表示。每個單元代表1平方米的領土。每個單元表示爲介於0和1之間的double值，表示遍歷單元的成本。
地圖顯然不適合在內存中。
我試圖圍繞一種方式來計算機器人從起點到終點的最佳路徑。我的第一個想法是製作一個類似TCP的移動窗口，在移動機器人周圍繪製真實地圖的小地圖，並在其中執行A *算法，但是我遇到了牆壁很大的地圖存在的一些問題，尋路等...
我正在搜索關於類似A *算法的文獻，並且我無法想象這個問題的解決方案的近似值。
我想知道是否有人遇到了類似的問題，或者可以幫助提出可能的解決方案！
感謝提前:)
因爲我不知道確切的數據，這裏的一些信息，可能是有用的：
的最短路徑的部分路徑本身就是一個最短路徑。即你可能會將你的矩陣分成子矩陣並找到（全部）最短路徑。請注意，您不必儲存全部結果：您可以通過不保存完整路徑來節省內存，但只是信息：路徑從A到B。中間節點可能稍後再計算或存儲在文件中供以後使用。您甚至可以預先計算某些區域的最短路徑。
另一種方法是你可能能夠以某種方式壓縮你的矩陣。即如果您的大面積區域只包含同一個號碼，則只需存儲該號碼和該區域的尺寸即可。
另一種方法（預先計算一些最短路徑）是爲了生成不同級別的地圖細節。考慮到美國的地圖，這可能看起來如下：最粗糙的細節包含紐約，洛杉磯，芝加哥，達拉斯，費城，休斯頓和菲尼克斯等城市。級別越高，它們包含的城市越多，但是 - 另一方面，整個地圖的較小區域由它們顯示。
您的問題是否有任何特殊結構，例如，三角不等式是否成立/您能保證最短路徑不會來回跳動嗎？你想多次執行查詢嗎？ （如果是這樣，你可以做預處理，將分攤在多個查詢。）你需要確切的最低限度的解決方案，或將在一個epsilon因素內的東西是好的？
一個想法是，你可以粗化矩陣 - 形成100米乘100平方米，並確定通過100乘100平方的最短路徑距離。現在這將適合內存（大約1千兆字節），您可以運行Dijkstra，然後展開100 \ times 100 square的每一步。
另外，你有沒有試過運行Dijkstra算法的向前 - 向後版本？即，從源頭擴展並同時搜索接收器，並在有交叉點時停止。
順便說一下，爲什麼你需要這樣精細的粒度級別？
這個問題沒有任何特殊的結構，它只是每個節點上有權重的矩陣的特例。查詢應該只執行一次，確切的解決方案會很好，但它應該是計算上合理的，所以一個足夠好的解決方案是可以的。這個想法與phimuemue表達的一樣，但應該使用低存儲器算法。問題是什麼？ – CatOsMandros 2010-11-01 21:32:37
這裏有一些想法，可能工作
您可以將路徑建模爲分段線性曲線。如果你有31條線段，那麼你的曲線完全由60個數字來描述。每一個可能的曲線中有一個成本，所以成本以下表格上的功能
成本（X1，X2，X3 ..... X60）
現在你的問題是要找到全局最優解60個變量的函數。您可以使用標準方法來執行此操作。一個想法是使用遺傳算法。另一個想法是使用蒙特卡洛方法，如並行回火
http://en.wikipedia.org/wiki/Parallel_tempering
只要你有一個有希望的路徑，那麼你可以使用它作爲一個出發點，找到成本函數的局部最小值。也許你可以使用一些插值來使你的成本函數是可微的。然後，您可以使用牛頓法（或者BFGS）來查找成本函數的局部mimima。
http://en.wikipedia.org/wiki/Local_minimum
http://en.wikipedia.org/wiki/BFGS
你的問題有點類似於在尋找化學反應系統路徑的問題。也許你可以在戴維斯威爾士的「能源景觀」一書中找到一些啓發。
但我也有一些問題：
>您是否有必要找到最佳路徑，或者您只是在尋找一條好路徑？確切的解決方案會很好，但它應該是計算上合理的，所以一個足夠好的解決方案是好的 – CatOsMandros 2010-11-07 09:51:42
你有多少計算機的功率和時間？有限的，但時間不是限制，所以它沒關係... – CatOsMandros 2010-11-07 09:52:17
機器人可以做出急轉彎，還是你需要額外的物理模型來提高成本函數？我不必關心那個:)。 – CatOsMandros 2010-11-07 09:54:50
具有不同層次的細節將是一個不錯的主意。如果我理解正確，一個9x9的矩陣可以分成3x3的矩陣，其中每個單元本身就是一個3x3矩陣，其值由啓發函數決定。和A *一樣，啓發函數不應該高估成本，也不會找到最佳路徑。讓我感到困惑的是，當我計算每個子矩陣內的路徑時，我應該如何定位開始點和結束點？ – CatOsMandros 2010-11-01 17:16:52