2015-09-26 96 views
5

問題Javascript:在(50000 * 50000網格)二維數組中尋找路徑?

所以,說一個想象的整數值的2D陣列,其表示網格地圖,像這樣: +-----+------+-----+-----+-----+ | 10 | 2 | 2 | 4 | 656 | +-----+------+-----+-----+-----+ | 234 | 165 | 724 | 759 | 230 | +-----+------+-----+-----+-----+ | 843 | 734 | 999 | 143 | 213 | +-----+------+-----+-----+-----+ | 242 | 2135 | 131 | 24 | 374 | +-----+------+-----+-----+-----+ | 159 | 464 | 155 | 124 | 151 | +-----+------+-----+-----+-----+

二維索引代表在一個單元格的座標地圖和數組中的值代表了遍歷該單元格地形的相對困難 - 例如,999可能是粗大的荊棘,而2,3,4可能是稍微傾斜的路徑......或其他東西。

現在,我們希望找到最容易從[X,Y]上的網格爲[Q,R]對電網

路徑(其中,這些步驟的總和是儘可能低的,換句話說) 問題域

這需要在一個現代的瀏覽器,其中一個較爲簡陋的地圖渲染運行,我們將通過所有的代禱頂點借鑑[X,Y]至[q,R] A線,在用戶輸入[q,r]之後。方便地,[X,Y]總是相同的(爲簡單起見[​​0,0])

因此,使用Djikstra算法或A *!

所以我的第一個直覺就是將數組建模爲圖,應用Dijkstra的算法並從那裏開始工作。而在上述情況下,使用5x5網格,效果很好。我遍歷每個數組索引,並使用該值和相鄰的值來生成一個節點,該節點的所有鄰居都具有加權邊緣。這建立了一個圖表,然後我可以將Djikstra的算法應用到。

但是,在實踐中,我將與數組一起工作達到50,000 x 50,000的大小!這是2.5億!

因此,顯然建立一個圖形運行Dijkstra的算法是不適用的。我的下一個想法是預先計算路徑(數據集是固定的),將它們存儲在服務器上,並在獲取目的地[q,r]時執行回調......但這是250,000,000條路徑......偶數如果我使它在不到一秒的時間內運行(我認爲它不會),那麼計算所有路徑需要幾年的時間......

我想我可能需要採取另一種方法,但我不知道,我該如何做這項工作?

+1

你是如何將數組建模爲圖的?您可能會利用網格結構... –

+0

請檢查這篇文章:[快速和準確估計最短路徑 大圖](http://people.mpi-inf.mpg.de/~sseufert/papers/ aspsn-cikm.pdf) – 2015-09-26 17:54:02

+1

它是2 500 000 000,而不是250 000 000 – Sopel

回答

3

不要構造一個明確的圖形(指針是昂貴的) - 使用座標對來表示隊列中的節點,並修改你的Dijkstra實現來直接操作你的2D數組表示。

使用類似於費用數組的數組來存儲算法計算的(最初暫定的)距離。

Dijkstra將在一次運行中計算所有節點的成本,所以如果您的起點是固定的,那麼運行一次就足夠了 - 無需運行數百萬次。

P.S:創建一個的jsfiddle上的圖像運行Dijkstra算法: https://goo.gl/5GWwMF

計算距離的所有點從鼠標點擊,在較暗的像素被解釋爲更昂貴的...

對於較大的圖像,它變得越來越慢,但到目前爲止它沒有讓它崩潰,但我認爲對於您的數據來說,它將在瀏覽器中耗盡內存。 Dijkstra實現使用以下接口來訪問圖形 - 我認爲這應該是直接提供數據結構的頂部,而不會顯式生成帶有顯式節點和邊緣的「傳統」圖形數據結構:

/** 
* The interface the Dijkstra implementation below uses 
* to access the graph and to store the calculated final 
* and intermediate distance data. 
* 
* @Interface 
*/ 
Graph = function() {}; 

/** 
* Returns the current distance for the given node. 
* @param {Object} node 
* @return {number} 
*/ 
Graph.currentDistance = function(node) {}; 

/** 
* Stores the current distance for the given node. 
* @param {Object} node 
* @param {number} distance 
*/ 
Graph.setCurrentDistance = function(node, distance) {}; 

/** 
* Returns an array of connected nodes for the given node, 
* including the distances. 
* 
* @param {Object} 
* @return {Array<{cost:number, node:Object}>} 
*/ 
Graph.connections = function(node) {}; 

PPS:添加代碼以在第一次單擊後顯示所有點擊上的短路徑。還修復了一個允許對角線移動的bug:https://goo.gl/wXGwiv

所以總而言之,雖然這可能不會在瀏覽器中擴展到50k x 50x,但我認爲這表明直接在陣列上運行的Dijkstra值得在服務器端嘗試並且與數據陣列大小相同的陣列是存儲來自單個點的所有最短路徑所需的全部數據。