最短成本路徑

我必須找到從D點到R的最短路徑。這些是固定點。這是情況的一個例子：最短成本路徑

enter image description here

盒還包含牆壁，通過它，你不能在他們通過，除非你打破他們。每個牆壁破裂都會讓你付出代價，讓我們說「a」點，其中「a」是一個正整數。每一個不涉及牆壁的舉動都需要1分。

該任務是找出所有最低成本的路徑，最少破牆數量的路徑。

因爲盒子的寬度可以達到100個單元格，所以與使用回溯無關。這太慢了。我想出了唯一的解決辦法是這樣的一個：

向東走還是南方，如果沒有牆壁
如果南方有一面牆，檢查是否有西牆上。如果西有牆，打破南牆。如果西面沒有牆，那就往西走，直到找到一個沒有牆的南面的牢房。重複這個過程，南和東，直到你超過這個順序破牆的成本。如果來自西部的路徑進入同一地點，就好像我已經打破了南牆並且花費相同或小於「a」點，則使用此路徑，否則制動南牆。
如果以上沒有任何事情發生，根據箱子的邊界制動南或東牆。

重複步驟1,2,3，直到「乘客」到達點R.在這3個步驟之間，存在「否 - 如果」關係。

你能想出更好的問題算法嗎？我用C++編程。

來源

2014-02-23 Robert Lucian Chiriac

究竟是什麼意思，「找出具有最低成本和最小斷壁的路徑」？像「在所有最低成本的路徑中，有最少數量的破牆」之類的東西？ – harold

是的，在所有最低成本的路徑中，選擇牆壁數量最少的路徑。 –

當我從D出發時，是否知道所有的牆壁都在哪裏？或者只有當我到達他們時才發現他們？ – Beta

使用Dijkstra算法，但對於成本給它1此舉不會破壞牆壁，和（a + 0.00001）爲打破一堵牆。然後狄克斯特拉會給你你想要的東西，打破所有最小成本路徑中最少的牆壁的路徑。

從概念上講，設想一個能夠跳過牆壁的旅行者 - 同時記錄成本 - 並且在面對兩條路徑的選擇時也可以分成兩個相同的旅行者，，羅伯特弗羅斯特！）。一次只有一個旅行者移動，至今爲止成本最低。那個人移動，並在地板上寫道：「我只用x來到這裏」。如果我在那裏已經找到了這樣一個音符，如果我更便宜地到達那裏，我就會刪除舊音符並寫下自己的音符;如果那個其他旅客更便宜地到達那裏，我會自殺。

來源

2014-02-23 17:29:07 Beta

:(減員 –

哪裏額外的0.00001優化來自於它是保持多少牆壁的軌道是「躍過」 –

@RobertEagle：？？是的，在同一實際成本兩個路徑之間的較量這種方式，其中一個涉及更多的牆壁將失去（並跳過牆壁，而不是打破它們是一個旅行者不能從另一個拆除執行受益）。 – Beta

這可以很容易地建模爲加權圖，然後將Dijkstra's shortest path algorithm應用於它。每個正方形都是一個節點。它連接到它相鄰的正方形的節點。根據是否有牆，連接的重量可以是1或「a」。這將使您獲得最低的成本。有可能最低成本和最少牆壁數量可能會有所不同。

來源

2014-02-23 16:52:20 azurelogic

這是一個普遍的算法（你必須自己做的實現）：

轉換矩陣爲加權圖：

對於矩陣中的每個條目，創建Vertex。
對於每個Vertex，創建一個Edges的數組，每個相鄰的Vertex一個。
對於每個Edge，根據拆分Edge所連接的兩個Vertices之間的牆的成本來定義權重。

然後，在圖表上運行Dijkstra算法（http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm）中，從開始Vertex D。作爲輸出，您將擁有從圖中Vertex D到其他Vertex的最短（最便宜）路徑，包括Vertex R。

來源

2014-02-23 16:56:02

兩部分「成本第一，然後斷壁」，可以表示爲一對（C，W），其被字典順序比較。 c是成本，w是破壁的數量。這使得它再次成爲「單一事物」（從某種意義上說），所以您可以將它放入算法等等中，只需要「成本」（作爲一個抽象的事物，它可能會增加其他成本或比較到其他成本）。

所以我們可以使用A*，採用曼哈頓距離啓發式（也許有更聰明的東西不會完全忽略牆壁，但這會起作用 - 低估距離是可以接受的）。運動成本當然不會忽視牆壁。鄰居將是所有相鄰的廣場。所有的費用都是我上面描述的那一對。

來源

2014-02-23 16:57:57 harold

提及啓發式的使用賦予這個答案比其他IMO更可靠。 –

最短成本路徑

回答

相關問題