http://youtu.be/gGQ-vAmdAOI?t=23m14sで作業していた 23:14 の時点で、「拡張リスト」を使用したブランチ & バウンドは Dijkstra のアルゴリズムに非常に似ていると感じました。講義の後半で、許容可能なヒューリスティックを使用してアルゴリズムを再度拡張すると、A* が得られます。
そのため、ダイクストラのアルゴリズムはまさに分岐限定のサブクラスであると考えるようになりました。そうですか？
講義を要約すると：
検索アルゴリズムが調査されます。具体的には、単純なブランチ & バウンド ソリューションから開始します。
宛先ノードが訪問される (拡張される) まで、ソースから最短距離のノードを訪問し、その後続ノードを訪問するノードの優先キューに追加します (最小距離でソート)。これはまだサイクルを検出しておらず (例: ノードを 2 回以上訪問する)、組み合わせ爆発のためにかなり非効率的です。
単純な拡張により、アルゴリズムのパフォーマンスが大幅に向上します。どのノードが既にアクセスされたかを記憶します (拡張された、したがって拡張リスト)。ノードが 2 回アクセスされることはなくなり、アルゴリズムのパフォーマンスが大幅に向上しました。
最後の部分では、A* を取得するために許容可能なヒューリスティックがミックスに追加されます。
これが十分な情報であり、講義の例をコピーする必要がないことを願っています. そうでない場合はお知らせください。