2点間の最長経路

Question

問題は、右上から左下に桁の最大合計で移動したいということです。ちょうど12の移動でそれを行わなければなりません。 eng。問題は、しかし簡単な解決方法は、私が言及した点でした、私はこれらの種類の問題がいくつかの理論グラフといくつかのアルゴリズムを持って知っているが、私は化学工学の学生だから、グラフや関連するアルゴリズム。 アイデアを思いつくために大変な努力をしましたが、実際には何も見つかりませんでした。私はあなたのアイデアに感謝します。

• 注：移動して、下から行く（右上に左：私たちは、水平方向と垂直方向の移動、私は答えを使用して、私はこれに着い

  

  のみ

を行うことを許可されていますトップへダウンからのものと）7をノード間43から行く、右だけに左：

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です正しいものは25.73でなければなりません。私が見つける パスは：

解答経路がある：

Answer 1

利用可能な移動の制限により、問題を有向非循環グラフとしてモデル化できます。 Longest path problemのWikipediaの記事に記載されているように、すべてのエッジウェイトwを-wに変換し、結果のグラフにDijkstra's shortest path algorithmを適用すると、これを解決できます。

グラフが非周期的であるという事実は、ダイクストラが失敗する負の重みサイクルがないことを意味するため、ここでは重要です。 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行列があります。行列A(i, j)の各要素は、ノードiからノードjまでのエッジがない場合、またはエッジの重みである場合、0です。したがって、要素A(7, 6)は、ノード7からノード6までのエッジの重みであるため、-3.04を含むことになります。したがって、隣接行列を作成するだけで、適切な場所にエッジウェイトを塗りつぶすことができます。

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の3つのベクトルを使用します。ここで、mはグラフの辺の数です。最初のベクトルsは、各エッジの開始（ソース）です。 2番目のベクトルtは、各エッジの終端（シンク）です。最後のベクトルは対応する辺の重みを含む。したがって、隣接行列の例の3つのエッジを使用すると、これらの行列は次のようになります。

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

ここ

我々は重量-3.04と6をノード間7から同じエッジを持っている、と13から14など

にこの情報を供給するために有向グラフ

を作成します関数digraphを使用して適切な構造を作成する必要があるMATLABのグラフアルゴリズム

G = digraph(A); 

または

G = digraph(s, t, w); 

れ、選択した表現に依存。あなたがGを持ったら

がshortestpathアルゴリズム

を使用し、それが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になる場合、多分大したことではないでしょうし、あなたはデフォルトを取ることができます。