兩點之間最長的路徑

問題是我想從右上角到左下角用最大的數字總和，我只需要用12步就可以做到這一點，實際上它是一種化學反應。工程。問題，但簡要的解決方法是我提到的要點，我知道這些類型的問題在圖形和一些算法中有一些理論，但由於我是化學工程專業的學生，我不太瞭解圖表和相關算法。我很努力想出一個想法，但我實際上沒有發現任何東西，我很欣賞你的想法。兩點之間最長的路徑

注：我們被允許做水平和垂直移動僅

我以前的答案，我得到這樣的：（從下會左至右上方，這樣移動從下往上，從左到右只，從節點43將節點7）：

clc 
clear 

A = zeros(49) ; 

A(8,1) = -3.02 ; 

A(1,2) = -3.1 ; 
A(9,2) = -2.04 ; 

A(2,3) = -2.07 ; 
A(10,3) = -2.09 ; 

A(3,4) = -2.01 ; 
A(11,4) = -2.04 ; 

A(4,5) = -3.1 ; 
A(12,5) = -3.03 ; 

A(5,6) = -2.06 ; 
A(13,6) = -2.05 ; 

A(6,7) = -3.04 ; 
A(14,7) = -2.05 ; 

A(15,8) = -2.04 ; 

A(8,9) = -3.04 ; 
A(16,9) = -2.05 ; 

A(9,10) = -2.02 ; 
A(17,10) = -2.01 ; 

A(10,11) = -3.1 ; 
A(18,11) = -2.1 ; 

A(11,12) = -2.09 ; 
A(19,12) = -3.1 ; 

A(12,13) = -2.08 ; 
A(20,13) = -2.04 ; 

A(13,14) = -2.03 ; 
A(21,14) = -2.06 ; 

A(22,15) = -3.05 ; 

A(15,16) = -2.02 ; 
A(23,16) = -2.09 ; 

A(16,17) = -3.05 ; 
A(24,17) = -2.07 ; 

A(17,18) = -3.01 ; 
A(25,18) = -2.08 ; 

A(18,19) = -2.09 ; 
A(26,19) = -3.03 ; 

A(19,20) = -2.09 ; 
A(27,20) = -2.02 ; 

A(20,21) = -2.04 ; 
A(28,21) = -3.05 ; 

A(29,22) = -3.05 ; 

A(22,23) = -2.07 ; 
A(30,23) = -3.09 ; 

A(23,24) = -3.05 ; 
A(31,24) = -3.08 ; 

A(24,25) = -2.01 ; 
A(32,25) = -3.05 ; 

A(25,26) = -2.01 ; 
A(33,26) = -3.03 ; 

A(26,27) = -3.04 ; 
A(34,27) = -3.1 ; 

A(27,28) = -3.05 ; 
A(35,28) = -2.06 ; 

A(36,29) = -2.03 ; 

A(29,30) = -2.05 ; 
A(37,30) = -3.05 ; 

A(30,31) = -2.1 ; 
A(38,31) = -3.06 ; 

A(31,32) = -2.09 ; 
A(39,32) = -2.09 ; 

A(32,33) = -2.05 ; 
A(40,33) = -2.07 ; 

A(33,34) = -3.08 ; 
A(41,34) = -3.02 ; 

A(34,35) = -3.07 ; 
A(42,35) = -3.04 ; 

A(43,36) = -2.08 ; 

A(36,37) = -2.05 ; 
A(44,37) = -2.07 ; 

A(37,38) = -2.08 ; 
A(45,38) = -3.1 ; 

A(38,39) = -3.03 ; 
A(46,39) = -2.02 ; 

A(39,40) = -2.09 ; 
A(47,40) = -3.05 ; 

A(40,41) = -3.09 ; 
A(48,41) = -2.1 ; 

A(41,42) = -3.1 ; 
A(49,42) = -2.07 ; 

A(43,44) = -2.08 ; 

A(44,45) = -3.06 ; 

A(45,46) = -2.01 ; 

A(46,47) = -2.1 ; 

A(47,48) = -2.02 ; 

A(48,49) = -2.06 ; 

G = digraph(A) ; 

[path,d] = shortestpath(G,43,7) ;

，但我得到了錯誤的路徑長度，MATLAB的答案是32 .78和正確的一個必須是25.73。我找到路徑是：

答案路徑是：

來源

2016-07-15 Mohammad Hosein Khalili

可能看看Dijkstra的算法，你必須實現它來尋找效率最低的路徑，而不是最高效的路徑，但它可能會工作。 – user3716193

同意@ user3716193。首先創建一個拓撲，然後你可以使用Djikstra的算法。用f（x）= 1/x轉換你的體重，然後計算「最短路徑」 – obchardon

我建議你閱讀[this]（http://www.geeksforgeeks.org/dynamic-programming-set-6-min-cost） -path /），它非常相似，並且適應你的場景。 –

由於可用移動的限制，您可以將問題建模爲有向無環圖。如維基百科關於Longest path problem的文章所述，您可以通過將所有邊權重w轉換爲-w並在結果圖上應用Dijkstra's shortest path algorithm來解決此問題。

您的圖形是非循環的這一事實在這裏非常關鍵，因爲這意味着將不存在會導致Dijkstra失敗的負重循環。

在2015b中，MATLAB引入了新的圖功能，其中一個叫做shortestpath。這是我們將要使用的。

圖表示

首先，你需要來構建你的圖表。有幾種方法可以表示一個圖，並且在這種情況下使用哪一種方法只是一個對您更有意義的問題。無論如何，我們將把這些信息傳遞給MATLAB的digraph，只要我們給它可接受的輸入，它就可以工作。

無論哪種方式，首先需要爲節點編號（圖片中的網格交叉點）。只要你一致，你如何給他們編號並不重要。我將在第一行對節點1-49：1-7進行編號，第二行編號爲8-14，依此類推直到底行的43-49。下面是網格右上角的幾個節點的示意圖，我將其用於演示目的。（請記住，我們正在將所有邊權重更改爲負數以找到最長的路徑。）來表示此

   (-2.06)  (-3.04) 
<-------- 5 <-------- 6 <-------- 7 
      |   |   | 
      |(-3.03)  |(-2.05)  |(-2.05) 
      |   |   | 
      v (-2.08) v (-2.03) v 
<-------- 12 <-------- 13 <-------- 14 
      |   |   | 
      |(-3.10)  |(-2.04)  |(-2.06) 
      |   |   | 
      v (-2.09) v (-2.04) v 
<-------- 19 <-------- 20 <-------- 21 
      |   |   | 
      |   |   | 
      |   |   | 
      v   v   v

鄰接矩陣

一種方法是使用鄰接矩陣。對於n節點，鄰接矩陣A是n x n。在我們的例子中，我們將有一個49 x 49矩陣。如果沒有從節點i到節點j的邊，或者它是邊的權重，則矩陣A(i, j)中的每個元素是0。因此元素A(7, 6)將包含-3.04，因爲這是從節點7到節點6的邊的權重。因此，您只需創建鄰接矩陣

A = zeros(49, 49);

並開始在正確位置填充邊緣權重。

A(7, 6) = -3.04; 
A(14, 13) = -2.03; 
A(13, 12) = -2.08; 
and so on...

邊緣列表

另一種方式來表示的曲線中使用邊緣列表。使用這種方法，而不是單個n x n矩陣，您將使用長度爲m的三個向量，其中m是圖形中的邊數。第一個矢量s是每個邊的開始（源）。第二個向量t是每個邊的末端（匯）。最後一個矢量包含相應邊的權重。因此，使用鄰接矩陣示例中的三條邊，這些矩陣看起來像這樣。

s = [ 7, 14, 13, ...] 
t = [ 6, 13, 12, ...] 
w = [-3.04, -2.03, -2.08, ...]

在這裏，我們已經得到了從節點7同一邊緣具有重量-3.04節點6和14到13等

創建有向圖

爲了養活這個信息使用函數digraph創建適當結構所需的MATLAB圖算法，可以是

G = digraph(A);

或

G = digraph(s, t, w);

，這取決於你的表示選擇。

使用最短路徑算法

一旦你得到了G，它只是一個呼叫shortestpath的問題。由於我們使用原始權重的負面因素，這實際上是最長的路徑。您還需要爲其提供路徑的開始和結束節點。使用我的編號，這將是start_node = 7和end_node = 43。

path = shortestpath(G, start_node, end_node);

這是您可能需要嘗試一點的部分。該shortestpath函數實際上還有另外一個參數，您可以通過：

path = shortestpath(G, start_node, end_node, 'Method', <algorithm>);

這<algorithm>參數，可以選擇具有最短路徑算法將被使用。如果您沒有指定'Method'，從我在documentation中可以看到的情況來看，由於負邊權重，它將默認爲'Method', 'mixed'。這應該工作得很好，給你最長的路徑。看起來有趣的另一個選項是'Method', 'acyclic'，這可能會提高大圖的性能。如果你的網格總是7 x 7，那麼它可能並不重要，你可以採取默認值。

來源

2016-07-15 16:02:40 beaker

我不明白他的問題怎麼可能是非循環的。你能解釋一下嗎？他還說他最多可以做12次動作。我不認爲Dijkstra算法可以用這種方式進行修改。你知道一個方法嗎？ – shamalaia

@shamalaia我瞭解這個問題的方式，唯一可能的舉措是向左或向下。對於每個網格交叉點，（最多）有兩個有向邊出去，（最多）有兩個進入。一旦你到達了一個給定的交叉點，就沒有辦法返回到右邊，所以你永遠無法到達該節點再次。至於移動次數，我明白這是來自曼哈頓右上角和左下角之間的距離。如果我誤解了問題的結構，那麼是的，我們將不得不重新考慮解決方案。 – beaker

dunno。我明白我們可以向上/向左和向右移動：「只允許做水平和垂直移動」意味着循環是可能的。我認爲有限的動作是一種保佑。只有12次動作才能輕鬆完成。 – shamalaia

兩點之間最長的路徑

回答

相關問題