創建公交路線

什麼是可用於創建公交路線的好算法或一類算法？創建公交路線

我在考慮用來解決旅行推銷員或哈密爾頓路徑問題的算法，但事實上，這兩個問題都沒有解決如何在兩站之間移動的問題。

我想算法至少有以下特點：

產生一個相對優化的路徑（我的理解，這個問題可能是NP完全，所以一個好的啓發式是罰款）
能處理具有不同權重的路徑部分（例如，在該路徑的該部分上行進的時間）
可以被迫使用給定的起點和終點（我認爲這不會是這樣的問題）

可以做到這一點的代碼，或類似的東西，將不勝感激（尤其是在C＃中），但一個好的算法本身就沒有問題。

注意：雖然有很多算法可以找到兩點之間的最短路徑，但我不知道我希望停止的順序。因此，除非我應該使用兩種算法的組合（我懷疑是這種情況），那些算法不會做我想做的事情（如果您認爲他們這樣做，請解釋）。

編輯：假設我知道所有需要做的停靠點。

來源

2012-01-01 soandos

看來，這樣做的方法涉及使用Floyd-Warshall算法，然後使用一種算法來解決旅行商問題。

這解決了所有「可選」頂點（交叉點）的問題，並使用旅行推銷員算法來確定停靠點的命中順序。

來源

2012-01-01 04:08:47 soandos

我用Djikstra的算法：http://en.wikipedia.org/wiki/Dijkstras_algorithm

沿着邊緣行進的成本不只是距離，但直到「下一個」總線從給定節點出發，也與時間有關。注意：當它停在一個節點時，你可能已經在總線上了。

來源

2012-01-01 00:22:49

我想你誤會了。我不想搭公車，我想創建公交路線。不知道Djisksra如何在這種情況下工作... – soandos 2012-01-01 00:24:19

請參閱編輯。我不認爲你的答案適用。 – soandos 2012-01-01 00:29:32

我仍然不明白，我仍然認爲Dijkstra的算法適用，因爲它告訴你要製造的停止。所有的道路通向羅馬，迪傑斯特拉的算法告訴你最好的。雖然維基百科指的是最短路徑，但算法實際上適用於最低成本。所以應用與您的標準相關的成本。如果您想知道每個節點中有多少人，請將其作爲您的標準添加，並且這應該告訴您從A到B的最佳路徑，以便您可以撿到最多的人。 – 2012-01-01 09:17:55

您可以在這裏稍微修改/假設使用旅行推銷員算法來解決點＃2（具有不同權重的路徑的一部分）。

比方說，從點路徑「A」至「B」點有2個權重（比如說，交通在某個時間點）

即使它的單一路徑，我們可以假設一個簡化的問題「虛擬頂點「，在」A「和」B「之間的點」C「，其在每個邊中將具有固定的權重。

A -------重量= 10 ------ ------ c ^重量= 15 ------乙

在這個新的曲線圖中，運行該旅行推銷員算法。

來源

2012-01-01 00:28:59

我想你明白了。這個問題使得這個問題與旅行商不同（正如我理解的那樣，如果我錯了，請糾正我）是有很多頂點我不需要命中（即每個未使用的交點）。有旅行推銷員算法可以做到這一點嗎？ – soandos 2012-01-01 00:31:37

那麼，如果你絕對不需要頂點命中，那麼你可以將通向該頂點的所有邊的權重增加到「無窮大」，並且推銷員問題機制將「自然地」避開那些邊。你的想法？ – 2012-01-01 00:37:05

圖上的所有交點都應該是虛擬頂點。他們應該有選擇地被擊中，而不是從未被擊中，或總是被擊中。 – soandos 2012-01-01 00:39:21

公交路線是由人而不是電腦創建的。只有人知道誰需要去哪裏以及經常出差。您至少需要這樣的數據來思考如何找到最適合人們需求的路線。關於這一點，我認爲你的問題是不明確的。

來源

2012-01-01 00:32:53

請參閱編輯以獲得澄清，但我認爲您不正確。我不希望一個計劃告訴我停車位應該在哪裏，但是按照什麼順序，以及在每一站停車的路徑。這似乎是一個非常明確的問題對我來說...... – soandos 2012-01-01 00:35:10

關鍵是你需要*定義約束* - 並且有**幾十個** - 然後只是應用Dijkstra的算法。 – 2012-01-01 00:39:19

Dijkstra算法適用於兩點之間的最短路徑。對於這個問題（正如我看到的那樣，如果我錯了，請糾正）我首先需要確定點的命中順序。迪克斯特拉不會這樣做。 – soandos 2012-01-01 00:40:52

創建公交路線

回答

相關問題