火車尋路算法

我正在試圖尋找火車遊戲中尋路的解決方案，其中有不同種類的分叉。我希望火車從一個鐵路走到另一個鐵路，除了尋路之外，所有的一切都實現了。火車尋路算法

我需要獲得列車列表，以便列車可以跟隨。現在，問題是我如何獲得列表。

我試過A *，沒有工作，因爲它停止搜索節點（鐵路）是否已經訪問。這是一個問題，因爲通過最長路線行駛可能是達到某一點的方式。
嘗試過洪水填充，這次它不停止搜索，如果已經訪問過，問題是我如何重建路徑，它如何選擇它不能再倒退。

事情是，有些情況下列車必須多次通過鐵路才能到達目的地。

任何想法？

起始點是A，結束B.當您看到綠色路徑是它應該旅行的方式。黑圈是列車不止一次行駛的軌道，在這種情況下是2次。

A->B

enter image description here

而且很明顯，你需要來自2黑去3紅。你不能只是去黑色 - > 2red-> 1red-> 3red。

來源

2013-10-01 marcg11

你能給時，你必須要經過一個鐵路多次的例子嗎？ –

我不明白A *有什麼問題，難道你不想走最短的路？「也許到達一個點的方式是通過最長的路線旅行。」如果一條路線存在，A *會找到它，如果有幾條，它會找到最短的一條，爲什麼你想要更長的一條。 – pseudoDust

*「也許到達一個點的方式是通過最長的路線旅行」* - 這完全是什麼意思？在什麼情況下你會不會採取最短路線？ –

展望。在圖中給出每個停靠點和每個路口兩個個節點，每個方向一列火車。 Dijkstra's algorithm完全適用於有向圖，所以一旦出現這種形式的問題，其餘的很容易。

因此，例如，在上圖中，從A開始，我們轉到junction 1。從那裏，只有一個地方移動到，junction 2，所以會有一個從A - >junction 1和從junction 1 - >junction 2箭頭。無論您選擇哪種選擇，您最終都會在junction 1，但是朝另一個方向移動，因此我們從那裏創建單獨的節點。從那裏，你可以選擇去A或B。

graph

注意，我刪除了J1的之一，因爲它是多餘的（只有一個地方可去）。

如果列車能停下腳步，轉身在停止像A，我們可以通過邊緣在兩個方向上連接這兩個節點，或只是將它們組合成一個節點。

，您可以給邊的權重，以指定的距離。

來源

2013-10-01 13:36:14

我不明白，看起來像你的形象描述了我所擁有的。 [鏈接]（http://oi39.tinypic.com/2saau7d.jpg） – marcg11

@ marcg11：我認爲你所描述的基本上是一樣的，儘管你用非常混亂的方式描述了它。但是如果你已經有了正確的設置，那究竟是什麼問題呢？ –

因此，我不需要一個連接（雙向），而需要兩個節點之間的連接。如果已經訪問過一個節點，Dijkstra的算法不會停止？我認爲這裏的問題是算法，不知何故，我需要一個可以重新檢查節點並構建路徑的算法。 – marcg11

洪水填充應該真的做到這一點（我用它在類似的情況下） - 但你只需要仔細處理開關和分段。

應該允許算法在不同的方向上傳遞相同的段，但不是相同的。即每個細分市場確實應該被視爲兩個分開。

重建應先分配號碼段，而充斥了他們，讓每一個從N-1達到標有N路徑 - 然後同時向後移動，跟蹤段應該做的，這樣的數字不斷減一。

它確實是一種BFS。在這幅畫

junctions

看來你的問題會以及由directed graph表示

來源

2013-10-01 10:12:44

讓人有些困惑，你可以張貼一些僞代碼，將是非常有益的。細分是什麼意思？我有他們之間的連接節點。 – marcg11

火車尋路算法

回答

相關問題