graph - 2ソース最適パス

Question

RXCテーブルがあるとしましょう。各セルには重みが含まれています。

行0から開始できるが、任意の列から開始できるように選択できる2つのソースがあります。

あなたの目標は、最後の行（任意の列）に到達し、重複するパスがなくなるまでテーブルを下に移動することです。そして、それはそれらの2つのパスを組み合わせた最小の重みを生成する必要があります。

解決する方法はありますか？詳細が必要な場合はお知らせください。

O（一定のXRXC）の実行時間を提供できれば、それは良いことです。

編集：各ステップでは、左、右、または下に移動できます。

例

1 9 1 9
1 9 1 9
1 2 3 9
6 3 9 9

最適なのは1-1-1-6と1-1-3-2-3です

Answer 1

Acess Denied で述べたように、行を下に移動する規則を指定してください。たとえば、次のように指定します。

You can either go directly down or right-diagonally down or left diagonally down

これは、最初のソースからの単一ソースの問題と同様に行うことができ、最適な合計を見つけてから、このパスに属するセルの重みを 0 に置き換えてから、2 番目のソースから単一ソースの問題のソリューションを再度実行できます。

final で両方のパスの合計が求められるため、この貪欲なアプローチが機能すると思います。