Floyd-Warshall-Algorithm を実装して、全ペア最短経路問題を解決しました。これで、簡単な変更でミニマックスまたはマキシミン パスも計算できることがわかりました。しかし、結果の意味がわかりません (ミニマックス パスとは)。ウェブでいくつかの説明を見つけましたが、混乱しています。
ミニマックス - グラフ問題のミニマックスには、パスに沿って最大コストを最小化する 2 つのノード間のパスを見つけることが含まれます。
Maximin - Minimax とは逆に、パスに沿って最小コストを最大化するパスを見つける必要があるという問題があります。
誰か他の説明や例を教えてください。
グラフ内のマキシミン パス (ボトルネック パスと呼ばれることが多い) を理解するには、次の問題を検討してください。各ノードが交差点を表し、各エッジが道路を表すグラフとして国の道路地図があります。道路にはそれぞれ重量制限があり、その重量制限を超えるトラックを運転すると、その道路は壊れてしまいます。開始位置から終了位置まで運転するトラックがあり、可能な限り最大の重量を乗せたいとします。この場合、可能な限り最大の重量を送るには、トラックをどの経路で運転する必要がありますか?
この問題について考えると、グラフ内の任意のパスについて、そのパスに沿って送信できる最大の重みは、最小容量を持つそのパスのエッジによって決定されます。その結果、最小キャパシティ エッジが最大になる、始点から終点までのパスを見つける必要があります。このプロパティを持つパスはマキシミン パスまたはボトルネック パスと呼ばれ、mot 最短パス アルゴリズムを簡単に変更することで見つけることができます。
ミニマックス パスは、反対の考え方を表します。つまり、最大エッジ キャパシティを最小化する 2 点間のパスです。
お役に立てれば！