algorithm - 最低コストのパスを見つけるための欲張りアルゴリズムの選択

Question

私は数字のピラミッドを持っています。各数字は、関連付けられたポイントの数を表します。欲張りアルゴリズムを使用して、ピラミッドの上部から下部に到達するためのコストが最も低いパスを見つける必要があります。情報に基づいていない検索アルゴリズムと情報に基づいた検索アルゴリズムについて読んだことがありますが、それでも何を選択すればよいかわかりません。この種の問題に最も適しているのは何ですか？貪欲な最良優先探索/A*探索またはその他？これは非常に単純な問題ですが、これらすべてのアルゴリズムを使用して、最適なオプションを知ることはできません。そして、私が言ったように、それは欲張りアルゴリズムでなければなりません。

Answer 1

私があなたを正しく理解しているなら、あなたのピラミッドでは常に左または右に降りるオプションがあり、一番下に到達するためのコストはあなたが通過するすべてのノードの合計です。

この場合は、下から上に向かって作業してください。下から2行目から始めます。行の各ノードについて、下の行の左右の子を確認します。安価な子ノードのコストを、現在のノードに追加します。ルート/ピークになるまで、行を上に移動して繰り返します。各ノードには、そこから最下部までの最も安価なパスのコストが含まれます。コストの安い子ノードを選択して、貪欲に下降します。

Answer 2

ここで正しくない欲張りアルゴリズムを使用する必要がない場合。この種の問題では、当然「動的計画法」と呼ばれる手法を使用します。

ピラミッドのすべての正方形を無限大で初期化します（バックアップを作成します）。ただし、独自の値を持つ初期点は除きます。

そして、ピラミッドを上から下へ、行ごとに処理します。最初の行から可能な限りどこにでも移動しようとし（したがって、1つだけがtopになります）、2番目の行のノードを更新して、topの値とその値を指定します。次に、2番目の行に移動し、次の行のノードを更新します。

以前にそのノードへのより良いルート（1つ左に配置されたノードからつながる）を見つけた可能性があるため、新しく作成されたルートが「高速」である場合にのみ更新します。（したがって、無限の初期化を行いました。つまり、最初はルートが実際に存在するかどうかはわかりません）。あるレベルのピラミッドの処理が終了すると、ノードに配置されているノードへの可能な限り最良のルートがあることがわかります。すぐ下のレベル。

少し複雑に聞こえても、実装は非常に簡単ですが、問題が発生しないことを願っています。

Answer 3

必要なのはダイクストラアルゴリズムです。これはA*検索よりも簡単ですが、DFSがそれを行うと思います。あなたが本当に何を望んでいるのかわかりません。