最短経路の問題

最短パス問題は、グラフ理論研究における古典的なアルゴリズム問題であり、グラフ内の 2 つのノード (ノードとパスで構成される) 間の最短パスを見つけることを目的としています。最短経路問題は、組み合わせ最適化の分野における古典的な問題の 1 つであり、コンピュータサイエンス、交通工学、通信工学、システム工学、オペレーションズリサーチ、情報理論、制御理論などの多くの分野で広く使用されています。ダイクストラのアルゴリズムは、古典的な最短経路アルゴリズムです。

アルゴリズムの具体的な形式は次のとおりです。 (推奨学習: PHP ビデオ チュートリアル )

開始点を決定する最短経路の問題、つまり開始ノードが与えられた場合の最短経路を見つける問題。

終点を求める最短経路問題 - 始点を求める問題とは逆に、この問題は終点ノードがわかっている場合の最短経路を求める問題です。無向グラフではこの問題は始点を求める問題と全く等価ですが、有向グラフではすべてのパスの方向を反転して始点を求める問題と等価です。

始点と終点の間の最短パスを決定する問題。つまり、始点と終点が与えられた場合に、2 つのノード間の最短パスを見つけます。

グローバル最短パス問題 - グラフ内のすべての最短パスを見つけます。

ダイクストラ アルゴリズム

ダイクストラ アルゴリズムは古典的な最短経路アルゴリズムです。その基本的な考え方は、最短経路を見つけた頂点を保存する集合 S を設定することです。 S の初期状態には、ソース点 v のみが含まれます。vi∈V-S の場合、ソース点 v から vi への有向辺が最短経路であると想定されます。今後、最短経路 v, ..., vk が得られるたびに、集合 S に vk が追加され、経路 v, ..., vk, vi が元の仮説と比較され、パスの長さが短い方が最短パスとして選択され、集合 V 内のすべての頂点が集合 S に追加されるまで上記の処理が繰り返されます。このアルゴリズムは、グローバルに最適な最短経路を見つけるために使用されます。ネットワーク ノードの数が多く、ネットワーク エッジの数が多い場合、メモリ使用量が多くなり、時間計算量が高くなるなどの欠点があります。また、ダイクストラのアルゴリズムでは、次の問題を解決できません。点制約を適切に通過しなければならない最短経路の問題。

アリのコロニー アルゴリズム

アリのコロニー アルゴリズムは、1991 年に Dorigo、Maniezzo、Colorni によって初めて提案されました。これは、アリの食物を求める行動に由来しています。研究の結果、アリの個体間ではフェロモンと呼ばれるフェロモンの一種によって情報が伝達されることがわかってきました。アリは歩行中に周囲のフェロモンの強さを感知し、フェロモン濃度の高い方向に移動し、餌を見つけると巣に戻る途中の目印としてフェロモンを放出し、仲間が発見した後、フェロモンを放出します。この道沿いで食べ物を見つける。仲間のうちの複数のアリが餌を見つけたものの、通路の長さが異なる場合、アリが短い通路を往復するのに要する時間は比較的短いため、単位時間当たりに多くのアリがその通路を通過することになります。 , したがって、フェロモン濃度が強いほど、その経路上にアリの数が増え、徐々に最適な経路が選択されていきます。

分類

は 2 つのサブ問題、つまり単一ソース最短パス問題とすべての頂点ペア間の最短パス問題に分割できます。前者は、グラフ内の特定の頂点から他のすべての頂点への最短経路を見つけることです。主なアルゴリズムには、ディクシャーのアルゴリズムが含まれます。後者は、グラフ内の頂点の各ペア間の最短経路を見つけることです。主なアルゴリズムは、フロイドのアルゴリズムです。 . ドイツ語アルゴリズムなど。

PHP 関連の技術記事をさらに詳しく知りたい場合は、PHP グラフィック チュートリアル 列にアクセスして学習してください。

以上が最短経路の問題の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。