找到兩個城市之間的連接

Question

我有一個假設的問題。假設我有一堆彼此相連的城市。這個問題純粹是假設的，所以我們如何連接它們並不重要（我們可以將它們看作某種圖形）。城市之間有巴士連接，但這些連接並不十分可靠。他們增加或刪除一段隨機時間，直到我們期望他們離開一個城市的時間，以及他們到達另一個城市的時間。我如何找到一種方法將一個人從一個城市帶到另一個城市儘可能快/相對較快但有更大的可能性？ 我應該閱讀什麼樣的算法來解決這個問題？

Answer 1

這是一個非常棘手的問題，可以用博弈論的方式來解決。

想到的最好的紙張是Botea 等的Multi-modal Journey Planning in the Presence of Uncertainty。人

本文的主旨是：

• 交通（步行，公交車或出租車）的每一種模式都有一定的時間範圍內才能讓你到達目的地，以及相應的機率。
• 您需要在時間Y的X地點，因此您假定每種交通方式的最壞情況
• 假設最差，您按最可能到達目的地的路線出發。

所以，如果出租車需要60-90分鐘之間，讓你到你的目的地，但乘坐巴士70總，你需要得到您的目的地在接下來的80分鐘，你會乘坐公交車。

但是，如果您需要在接下來的65分鐘內到達目的地，您需要乘坐出租車，因爲這是唯一可以準時到達目的地的方式。

我在想你可以適應你的方法。每個城市都通過巴士路線與K個其他城市連接，這些巴士線路有相應的持續時間和這些持續時間的概率。您可以將每條公交線路都視爲不同的交通方式。

---

另一種方法是在你的圖上使用A *，試圖尋求最小化不確定性和持續時間。

第二種方法（不完全相同但相關）的相關論文是FIRM: Feedback controller-based Information-state Roadmap - A framework for motion planning under uncertainty。

雖然本文涵蓋了很多關於動力系統的內容，但關於通過路線圖（圖）提取路徑以最小化不確定性的部分將會很有用。也許你可以適應這一點，以納入速度的某些方面。

Answer 2

如果變異確實是隨機的，那麼對我來說，你可以做的最好的事情就是找到連接數最少的路徑。這可以通過Breadth First Search完成。

Answer 3

看看路由算法，如Distance Vector Routing Protocol。它們旨在用於此目的。找到其他節點的方法，即使圖形發生變化。 您可以做什麼的簡短摘要如下：

• 每個城市都存儲它到達的所有城市的列表。隨着它存儲的距離，並通過它到達城市的鄰居節點。每個城市然後告訴它的鄰居它可以到達哪個節點。如果新近接收到的鄰居信息改變了當前可能的連接，則該城市更新其列表並將該信息傳播給其他人，直到列表不再改變。
• 每當城市發現與鄰居的連接斷開或恢復時，它會更新列表並將此信息傳送給其餘所有鄰居。每個鄰居然後更新他們的列表並將信息傳播給其他鄰居。
• 注意的「無窮計數問題」

Answer 4

我不認爲這是一個可能的解決方案爲這樣的問題。然而，在一個隨機性的世界裏（例如現實世界），每一次移動都會失敗，這裏有一個模型。嘗試使用離散時間馬爾可夫鏈（DTMC）。

你的每個城市都是馬爾可夫國家。 當你試圖從城市A轉移到城市B時，有成功和失敗的可能性。 失敗意味着你留在同一個城市。

使用DTMC，您可以計算出您需要製作多少個動作，以一定概率實現您的最終城市。