0

ターン ベースの戦略ゲームをプログラミングしていて、特別なシングル ペア最短経路問題があります。私は非負のゼロ以外のエッジの重みを持つ重み付き有向グラフを持っています。ここに、グループとして一緒に移動するさまざまな移動タイプを持つユニットである複数の旅行者のキャッチがあります。グラフの各エッジは、移動の種類に応じて、ユニットごとに異なる重みを持っています。

通常は、たとえば次のように使用します。最短経路問題を解くダイクストラ アルゴリズム。しかし、複数のユニットがグループとして一緒に移動し、各ユニットのエッジの重みが異なる場合、最適なパスが単独で移動する単一のユニットの最適なパスと同じではない場合があります。下から見るとわかるように

例の写真

赤と緑は S から D に移動します。赤が単独で移動する場合の最適なパスは、コスト 2 の SAD であり、緑が単独で移動する場合の最適なパスは、コスト 2 の SCD です。ユニットの移動コストは 5 であるため、ユニットが一緒に移動する最適なパスは、最大移動コストが 4 の SBD です。

エッジの重みを正規化できるため、ユニット タイプごとにターンごとの移動ポイントの量が異なることは問題ではないようです。これを線形計画として定式化し、シンプレックス アルゴリズムで解決できますか? 複数の目的関数があるように思われ、最大値を最小化したいと考えています。しかし、おそらくもっと簡単な解決策はありますか?

4

1 に答える 1

0

複数の旅行者をグループで旅行させたい場合は、あなたが提案したように、ある種の最適化アルゴリズムを使用して最適なものを見つける必要があります。

一方、グループ全体の最適化が必要ない場合(時間がかかる場合があります)、ヒューリスティックまたは近似最適化アルゴリズムを使用してみてください。

あなたのゲームの詳細がわからないので、どのヒューリスティックがあなたに役立つかはわかりません. おそらく、各グループ (フライヤー、スイマー、地上ユニットなど) から代表を選択することで検索スペースを少し最小限に抑え、選択したユニットの最適なグループのパスを見つけることができます。

于 2013-02-14T13:04:06.540 に答える