この ウィキピディアのミニマックスまたはマキシミンの問題を理解するのに苦労しています。私が理解できないのは、問題が何を望んでいるのかということです。あるノードから別のノードへの最短パスが必要ですか? これでなければ、何よりも？最小重量または最大重量とは何ですか? 例を使用した説明は非常に役立ちます.私が正確に望むのは、最大重量の最小値は何ですか? 最小値と最大値の関係がわかりません。
質問する
633 次
2 に答える
2
例による説明: (ウィキペディアの例から派生)
マルドンとフィーリングの間のミニマックス パスは赤で示されています。
ここでは、すべてのエッジ間の最大値は 9 です。
max(8,9,7,8,9) = 9
すべてのエッジの最大値が 9 未満である可能性のあるパスはありません。
これは最短パスではないことに注意してください。最短パスは 2 つの間の直接パスで、コストは 10 ですが、10 > 9 であるため、ミニマックス パスにはなりません。
于 2013-10-22T12:00:16.927 に答える
1
問題は、パスの最小エッジが可能な限り大きくなるパスを見つけることです。
したがって、パス P = e1, ..., ek があり、ei がエッジの重みである場合、f(P) を min(e1, ..., ek) とします。f(P*) ができるだけ高くなるようにパス P* を見つける必要があります。
問題の別の可能な解釈: グラフから重み < W のすべてのエッジを削除した場合でも、ソースからターゲットへのパスが存在するように、最大重み W を見つけます。この場合、W = f(P*) です。
于 2013-10-22T11:55:30.200 に答える