單對最短路徑多的遊客

Question

我編程的回合策略遊戲，我有一種特殊的一對最短路徑問題。我有一個帶有非負非零邊權重的加權有向圖，這裏有多個旅行者，這就是具有不同運動類型的單位作爲一個團體一起旅行。取決於移動類型，圖表的每個邊緣對於不同的單位具有不同的權重。

通常人們會使用如。 Dijkstras算法來解決最短路徑問題。但是，如果多個單元作爲一個整體一起移動，並且每個單元的邊緣權重不同，則情況可能是最佳路徑與任何單個單元單獨移動的最佳路徑不同。如可以從中可以看出以下

用紅色和綠色的選自S移動到D.用於紅色的最佳路徑移動單獨將SAD爲2的成本和用於綠色的單獨移動將是最佳路徑SCD，成本爲2.然而，在這兩種情況下，其他單位的運動成本將爲5，因此單位一起移動時的最優路徑是SBD，最大運動成本爲4.

由於邊緣權重可以被歸一化，所以每單位類型的每轉動點似乎不成問題。這可以作爲一個線性程序公式化並用單純形算法解決嗎？看起來我們會有多個目標函數，我們希望儘量減少最大值。但是，有沒有更簡單的解決方案？

Answer 1

如果你真的想多遊客中的一組旅行，那麼你就需要使用某種優化算法，並找到最佳的，就像你建議。另一方面，如果整個組不需要（可能需要一些時間），則可以嘗試使用啓發式或近似優化算法。

因爲我不知道你的遊戲的細節，我不能說哪個啓發式可能對您有用。也許你可以通過從每個組中選擇一個代表（傳單，游泳者，地面單位等等）來使搜索空間最小化，並找出所選單元的最佳組路徑。