連接節點圖的快速路徑緩存生成

我正試圖在我正在爲連接節點圖形工作的遊戲中使用更快的尋路機制。節點分爲「網絡」和「路由器」兩種類型。連接節點圖的快速路徑緩存生成

在這幅圖中，藍色圓圈代表路由器和灰色矩形網絡。

每個網絡都會保存它連接到哪個路由器的列表，反之亦然。路由器不能直接連接到其他路由器，並且網絡不能直接連接到其他網絡。

他們所連接

路由器的路由器網絡列表中做同樣的

我需要一個算法，將繪製出的路徑，數量來衡量的網絡交叉，對於每個可能的源網絡和目標網絡，不包括源和目標是相同網絡的路徑。我現在有一個，但它速度慢得不可置信，需要花費大約兩秒來繪製路徑，這對於所有連接的玩家來說都變得非常引人注目。

當前的算法是深度優先的蠻力搜索（它在大約一個小時內被拋在一起，以獲得路徑緩存工作），它以它們遍歷的順序返回一組網絡，這解釋了它爲什麼是太慢了。有沒有更高效的算法？作爲一個側面說明，雖然這些示例圖有四個網絡，但在實踐中有55個網絡和約20個正在使用的路由器。不可能的路徑也可能發生，並且在任何時候網絡/路由器圖形拓撲都可能改變，需要重建路徑緩存。

什麼方法/算法可能會爲這種類型的圖形提供最佳結果？

來源

2010-06-01 Sukasa

如果需要，我可以提供用於在提問時構建緩存的代碼 – Sukasa 2010-06-01 05:18:03

Dijkstra的最短路徑算法是經典的，但僅設計爲靜態的圖表。

您可以嘗試在網絡上搜索動態最短過去的算法。

下面是一篇似乎相關的論文：http://www.utdallas.edu/~edsha/papers/bin/Globecom04_SPT.pdf （並可能會給你其他線索）。

本文描述了一個路由器網絡，其中每個路由器維護它自己的最短路徑表。也許你可以做類似的事情。

我建議你也看看一般的路由算法，因爲採用最短路徑總是可能造成擁塞等（我正在考慮16團隊暈！）。您可能還想要合併負載平衡等。

希望它有幫助。

來源

2010-06-02 01:50:14

在網絡環境中，流量級別/ etc不相關，因爲它只是一個簡單的高級模擬。遊戲編碼爲一種編譯爲字節碼的語言，然後進行解釋，所以這些函數需要相對輕量級（而將代碼從一個網絡移動到另一個網絡的代碼效率與不移除功能時效率相同）。只要我能夠快速建立*任何有效的路徑或快速確定沒有這樣的路徑存在（或者兩者的一些妥協），我很高興。 – Sukasa 2010-06-02 22:25:04

@Sukasa：然後，您可能會發現將圖形分解爲雙連接的組件很有用。 – 2010-06-02 23:28:20

@Moron你可能會多給點信息嗎？關於它們的維基百科文章讓我有點不確定 – Sukasa 2010-06-03 03:01:52

你可能想看看古典的網絡領域。這不是確切的答案，但應該給你一個「比蠻力」算法更好的出發點。

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

來源

2010-06-01 05:55:37 jcsf

連接節點圖的快速路徑緩存生成

回答

相關問題