Q&A
python
1data = [ 2 [1,3,1], 3 [1,5,1], 4 [4,2,1] 5]
上記のようなデータに対して，data[0][0]を出発点，data[-1][-1]を目的地，data内の各要素をコストとして，最短経路を求める問題に取り組んでいますが，具体的な解決案が思いつきません．
この問題を解く上で重要な考え方などがありましたら教えていただけると幸いです．よろしくお願いいたします．
回答1件
0
ベストアンサー
経路の候補が少なければ全探査でも問題ないでしょう。まずはそれで実装してみましょう。
経路の候補が多くなってきたら考えるべきことは「枝刈り」です。例えば
B / \ A D-E \ / C
というグラフがあってそれぞれコストが
A -> B = 1 A -> C = 3 B -> D = 2 C -> D = 1 D -> E = 3
だとしましょう。この場合 A -> B -> D = 3 に対して A -> C -> D = 4 なので C 周りのルートを通ったら絶対コストが多くかかります。このような経路は数え上げないほうが計算が速くなるでしょう。
具体的な実装については全探査を実装してみた後に「枝刈り」を考えてみてください（ちゃんと名前もついた方法です）。
投稿2021/01/01 16:34
総合スコア2853
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2021/01/02 02:50