グラフ内のノード間の最短経路は、いくつかのアルゴリズム（Dikstra、A-starなど）によって見つけることができます。
しかし、この問題にはどのようなアプリケーションがありますか？（私はすでにかなりの数を知っていますが、もっと多くの例を見たいと思います）。
応募/回答は1つだけお願いします！アプリケーションと、それを最短経路問題に変換する方法を説明します。
28239 次
11 に答える
6
高速道路で結ばれている多数の都市が与えられた場合、ニューヨークからシカゴまでの最短経路を見つけます。
高速道路の交通量と長さがパスの重みです。
于 2010-12-10T18:32:15.920 に答える
5
最短経路アルゴリズムを使用して、ワード ラダー パズルを解くことができます。
たとえば、「cat」、「bat」、「bag」、「bog」、「dog」のように、一度に 1 文字ずつ変更して、「cat」という単語を「dog」という単語に変更します。
于 2012-05-06T17:12:03.213 に答える
4
最短経路問題は、列生成と呼ばれる手法によって解決できる最適化問題のクラス全体の基礎を形成します。例としては、車両のルーティングの問題、存続可能なネットワーク設計の問題などがあります。そのような問題にはマスター問題があります(通常は線形プログラム) 各列はパスを表します (車両ルーティング問題のパスを、車両が通ることができる候補ルートの 1 つと考えてください。ネットワーク設計問題のパスを、商品が通る可能性のあるルートと考えてください)。ソースと宛先の間で送信できます)。マスター問題は繰り返し解かれます。毎回、ソリューションのメトリックを使用して、個別の問題 (列生成サブ問題と呼ばれる) が解決されます。この問題は、最短経路の問題であることが判明します (通常、側面の制約または負の弧の長さが問題を NP-Hard にします)。新しい有用なパスが取得された場合、それは元のマスター問題に追加され、パスのより大きなサブセットで再解決され、ますます優れた (通常は低コストの) ソリューションにつながります。
于 2010-12-11T14:16:23.770 に答える
2
与えられたコンピューターのネットワーク (ピアツーピア アプリケーションなど) で、マシン A からマシン B への最短パスを見つけます。
于 2010-12-10T18:31:18.463 に答える
2
ビデオ ゲームでは、これらのアルゴリズムは、マップ上の 2 点間の最短経路を見つけるためによく使用されます。このコンテキストで呼ばれる「パスファインディング」は、AI がルートをプロットするために使用したり、ゲーム エンジンがルートのプロットでユーザーを支援するために使用したりできます。
于 2010-12-10T18:32:34.613 に答える
2
おそらく使用されていることがわかる 1 つの例は、特定の量のバッテリー充電または燃料で特定のポイントを移動する必要がある事前設定されたポイント デバイスです。
軍隊では、偵察する必要がある事前設定されたポイントを持つ特定の小さな無人航空機/デバイスがあります。非常に長い距離を移動する必要があるため、そのような小さなデバイスでは、それを制御しようとするとコストがかかりすぎます。最遠点に到達する前にラジコンが劣化します。そこでアルゴリズムの出番です。
物を偵察して解放したいポイントを設定するだけです。すべてのポイントをカバーするために移動した最短経路を見つけさせます。主要なツールを必要としないため、より手頃な価格でポータブルです。
于 2010-12-10T18:37:21.627 に答える
2
ソーシャル ネットワーク... 2 人の間の最短経路を見つける (分離度)
于 2010-12-10T19:28:21.543 に答える
1
于 2010-12-10T18:43:48.897 に答える
1
最短経路は、SNA (ソーシャル ネットワーク分析) で媒介中心性を計算するためによく使用されます。通常、絆が強い人は、最短経路でコミュニケーションをとる傾向があります。人（ノード）間の最短経路をグラフで知ることで、隠れた強い絆を知ることができます。いくつかのメトリックを計算するだけで、グラフで多くの興味深いことを発見できます。
于 2014-02-08T03:19:36.910 に答える