問題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條路徑......偶數如果我使它在不到一秒的時間內運行(我認爲它不會),那麼計算所有路徑需要幾年的時間......
我想我可能需要採取另一種方法,但我不知道,我該如何做這項工作?
你是如何將數組建模爲圖的?您可能會利用網格結構... –
請檢查這篇文章:[快速和準確估計最短路徑 大圖](http://people.mpi-inf.mpg.de/~sseufert/papers/ aspsn-cikm.pdf) – 2015-09-26 17:54:02
它是2 500 000 000,而不是250 000 000 – Sopel