ターン ベースの戦略ゲームをプログラミングしていて、特別なシングル ペア最短経路問題があります。私は非負のゼロ以外のエッジの重みを持つ重み付き有向グラフを持っています。ここに、グループとして一緒に移動するさまざまな移動タイプを持つユニットである複数の旅行者のキャッチがあります。グラフの各エッジは、移動の種類に応じて、ユニットごとに異なる重みを持っています。
通常は、たとえば次のように使用します。最短経路問題を解くダイクストラ アルゴリズム。しかし、複数のユニットがグループとして一緒に移動し、各ユニットのエッジの重みが異なる場合、最適なパスが単独で移動する単一のユニットの最適なパスと同じではない場合があります。下から見るとわかるように
赤と緑は S から D に移動します。赤が単独で移動する場合の最適なパスは、コスト 2 の SAD であり、緑が単独で移動する場合の最適なパスは、コスト 2 の SCD です。ユニットの移動コストは 5 であるため、ユニットが一緒に移動する最適なパスは、最大移動コストが 4 の SBD です。
エッジの重みを正規化できるため、ユニット タイプごとにターンごとの移動ポイントの量が異なることは問題ではないようです。これを線形計画として定式化し、シンプレックス アルゴリズムで解決できますか? 複数の目的関数があるように思われ、最大値を最小化したいと考えています。しかし、おそらくもっと簡単な解決策はありますか?