タワー ディフェンス ゲームでは、開始点、終了点、壁の数を含む NxM グリッドがあります。
敵は最初から最後まで壁を通過せずに最短経路をたどります(通常、敵はグリッドに拘束されていませんが、簡単にするために拘束されているとしましょう。どちらの場合も、斜めの「穴」を通過することはできません)。
問題(少なくともこの質問では)は、最大K 個の壁を追加して、敵がたどらなければならない経路を最大化することです。たとえば、K=14 の場合
私の直感では、(私が望んでいるように)フィニッシュに移動する前に訪問しなければならないウェイポイントを含むようにこれを一般化すると、この問題は NP 困難であることがわかります。
しかし、最適に近い解決策を見つけるためのまともなヒューリスティックはありますか?
[編集]関連する質問をここに投稿しました。
私は貪欲なアプローチを提示しますが、おそらく最適に近いでしょう（ただし、近似係数が見つかりませんでした）。アイデアは単純です。迷路の重要な場所にあるセルをブロックする必要があります。これらの場所は、迷路の接続性を測定するのに役立ちます。頂点の接続性を考慮することができ、開始点と最終点を切断する最小の頂点カット(s,f)を見つけます。その後、いくつかの重要なセルを削除します。
グラフにするには、迷路の双対を取ります。このグラフの最小(s,f)頂点カットを見つけます。次に、このカットの各頂点を調べます。頂点を削除すると、すべての s,fパスの長さが増加するか、s から f までの最小長のパスにある場合は削除されます。頂点を削除した後、上記のプロセスを k 回再帰的に繰り返します。
しかし、これには問題があります。これは、s から f へのパスを切断する頂点を削除する場合です。これを防ぐために、切断ノードにできるだけ高い重みを付けることができます。つまり、最初に最小 (s,f) 切断を計算します。切断結果が 1 つのノードのみの場合は、重み付けして、その頂点に n^3 のような高い重みを設定します。最小 s,f カットを計算します。前の計算での単一のカット頂点は、待機中のため、新しいカットに属しません。
しかし、s,f 間にパスが 1 つしかない場合 (いくつかの反復の後)、それを改善することはできません。この場合、どのカットにも属さない s から f への最短パスの 1 つからノードを削除するなど、通常の貪欲なアルゴリズムを使用できます。その後、最小頂点カットを処理できます。
各ステップのアルゴリズム実行時間は次のとおりです。
min-cut + path finding for all nodes in min-cut
O(min cut) + O(n^2)*O(number of nodes in min-cut)
また、最小カットのノード数は非常に悲観的な状況では O(n^2) を超えることはできないため、アルゴリズムは O(k n^4) ですが、通常は O(k n^3)を超えることはありません。、通常は最小カット アルゴリズムが経路検索を支配するため、通常、経路検索は O(n^2) を必要としません。
貪欲な選択は、シミュレーテッド アニーリング タイプのアルゴリズムの良い出発点だと思います。
PS: 最小頂点カットは最小エッジ カットに似ており、max-flow/min-cut のような同様のアプローチを最小頂点カットに適用できます。各頂点を 2 つの頂点、1 つの V i、1 つの V oと仮定すると、入力と出力、無向グラフを有向グラフに変換することも難しくありません。
K 個の封鎖のすべてが現在の最小長のルート上に配置されるように、解決策を探すだけで十分であることは簡単に示されます (読者への演習として証明しておきましょう)。複数の最小長のルートがある場合は、それらすべてを考慮する必要があることに注意してください。その理由は、現在の最小長のルートに残りの封鎖を配置しない場合、それは変わらないからです。したがって、検索中に最初に利用可能な封鎖をすぐに配置できます。これにより、力ずくの検索でも高速化されます。
しかし、さらに最適化があります。また、次の封鎖を現在の最小長のルートの最初の封鎖になるようにいつでも決定できます。つまり、ルートの 10 番目のマスに封鎖を配置した場合、マスに 1 をマークするように作業します。 ..9 バックトラックするまで「永久に開く」。これにより、バックトラッキング検索中に検索する正方形の数が指数関数的に節約されます。
その後、ヒューリスティックを適用して検索スペースを削減したり、並べ替えたりできます。たとえば、最初に、現在の最小長のルートの長さを最も長くする封鎖配置を試してください。次に、限られた量のリアルタイムでバックトラッキング アルゴリズムを実行し、これまでに見つかった最適なソリューションを選択できます。
私は、含まれる最大多様体問題をブール充足可能性に還元し、この部分問題への依存によって NP 完全性を示すことができると信じています。このため、提供されるアルゴリズムspin_plateは、ヒューリスティック、事前計算、および機械学習が合理的であるため、合理的です。
次のようなボードを検討してください。
..S........
#.#..#..###
...........
...........
..........F
これには、貪欲でゲートバウンドなソリューションが失敗する原因となる多くの問題があります。その 2 行目を見ると、次のようになります。
#.#..#..###
私たちの論理ゲートは、次のように並べられた 0 ベースの 2D 配列[row][column]です。
[1][4], [1][5], [1][6], [1][7], [1][8]
これを方程式として再レンダリングして、ブロックを満たすことができます。
if ([1][9] AND ([1][10] AND [1][11]) AND ([1][12] AND [1][13]):
traversal_cost = INFINITY; longest = False # Infinity does not qualify
満たされないケースとしての無限を除いて、これをバックトラックして次のように再レンダリングします。
if ([1][14] AND ([1][15] AND [1][16]) AND [1][17]:
traversal_cost = 6; longest = True
そして、私たちの隠されたブーリアン関係は、これらすべてのゲートに当てはまります。また、幾何学的証明が再帰的にフラクタル化できないことを示すこともできます。N-1これは、幅または高さの長さが正確な壁を常に作成できるためです。これは、すべての場合においてソリューションの重要な部分を表します (したがって、分割統治法は役に立ちません)。 ）。
さらに、異なる行にまたがる摂動は重要であるため、次のようになります。
..S........
#.#........
...#..#....
.......#..#
..........F
計算可能な幾何学的恒等式の完全なセットがなければ、完全な検索空間は N-SAT に縮小されることを示すことができます。
拡張により、ゲート数が無限大に近づくにつれて、これは検証が簡単で、解決が非多項式であることを示すこともできます。当然のことながら、これがタワー ディフェンス ゲームが人間にとって非常に楽しいものであり続けている理由です。明らかに、より厳密な証明が望まれますが、これは基本的なスタートです。
n-choose-k 関係で n 項を大幅に減らすことができることに注意してください。各摂動がクリティカル パス上になければならないことを再帰的に示すことができ、クリティカル パスは常に O(V+E) 時間で計算できるため (各摂動の処理を高速化するためにいくつかの最適化を行うことで)、ボードに追加された追加のタワーごとに幅優先検索を犠牲にしてスペースを検索します。
O(n^k) を決定論的解として許容できると想定できるため、ヒューリスティックなアプローチが合理的です。したがって、私のアドバイスは、問題に適用可能な機械学習技術に目を向けて、spinning_plate の回答とSoravux の回答の間のどこかに当てはまります。
0 番目の解決策:許容できるが最適ではない AI を使用します。この AI では、spinning_plate が 2 つの使用可能なアルゴリズムを提供します。実際、これらはゲームにアプローチするナイーブ プレイヤーの数を概算しており、高度な悪用可能性はあるものの、単純なプレイにはこれで十分なはずです。
一次解決策:データベースを使用します。問題の定式化を考えると、その場で最適解を計算する必要性が十分に実証されていません。したがって、情報なしでランダムなボードにアプローチするという制約を緩和すると、K各ボードの許容可能なすべての最適値を単純に事前計算できます。明らかに、これは少数のボードでのみ機能します。各構成の潜在的なボード状態では、非常に大きくなるV!ため、すべての最適値を許容できるように事前計算することはできません。V
二次的な解決策:機械学習ステップを使用します。アルゴリズムが収束するか、貪欲以外の最適なソリューションが見つからなくなるまで、非常に高いトラバーサル コストが発生するギャップを埋めるように、各ステップを進めます。ここでは非常に多くのアルゴリズムを適用できるため、プログラムの制約内で機能する正しいアルゴリズムを選択するために、古典と文献を追跡することをお勧めします。
最良のヒューリスティックは、O(V^2) トラバーサルの後に最も一般的にトラバースされたものから最も一般的でないものへと結果をソートする、局所的に状態を認識する、再帰的な深さ優先トラバーサルによって生成される単純なヒート マップである可能性があります。この出力を処理することで、すべてのボトルネックを貪欲に特定できます。パスを不可能にせずにそれを行うことは完全に可能です (これを確認するのは O(V+E) です)。
すべてをまとめると、ヒート マップとクリティカル パスの ID を組み合わせて、これらのアプローチを交差させてみることにします。ここには、問題のすべての制約を満たす優れた機能的な幾何学的証明を考え出すのに十分なものがあると思います。
明白なことを述べる危険を冒して、ここに1つのアルゴリズムがあります
1) Find the shortest path
2) Test blocking everything node on that path and see which one results in the longest path
3) Repeat K times
単純に、これには O(K*(V+ E log E)^2) がかかりますが、部分的なパスのみを再計算するだけで、少し作業を進めるだけで 2 を改善できます。
あなたが言及したように、ほとんどのブレークが単純に 1 (または 2) の長さを追加する場合、大きなゲインにつながるチョーク ポイントを見つけるのが難しいため、単純にパスをブレークしようとするのは困難です。
始点と終点の間の最小頂点カットを取ると、グラフ全体のチョーク ポイントが見つかります。1つの可能なアルゴリズムはこれです
1) Find the shortest path
2) Find the min-cut of the whole graph
3) Find the maximal contiguous node set that intersects one point on the path, block those.
4) Wash, rinse, repeat
3) が大きな部分であり、このアルゴリズムのパフォーマンスが悪い理由でもあります。あなたも試すことができます
最後のものは、最も有望かもしれないものです
グラフ全体で最小頂点カットを見つけた場合、グラフ全体のチョーク ポイントを見つけることができます。
ポイントを使用して新しい島を作成できるため、これが機能するかどうかはわかりません。しかし、壁をどこに置くかを考えるのに役立つかもしれません.
各島間の最適な K パスを追跡する長さ K の優先キューを使用して、変更された幅優先検索を使用することをお勧めします。
私は、つながった壁のすべての島について、それが光であるふりをします. （横方向と縦方向の光しか出せない特殊な光）
レイトレーシングを使用して、光が他のどの島に当たるかを確認します
Island1 (i1) は i2、i3、i4、i5 にヒットしますが、i6、i7 にはヒットしません。
次に、line(i1,i2)、line(i1,i3)、line(i1,i4)、line(i1,i5) があります。
すべてのグリッド ポイントの距離が無限大であることをマークします。開始点を 0 に設定します。
最初から幅優先検索を使用します。すべてのグリッド ポイントで、そのグリッド ポイントの距離を隣接点の最小距離にマークします。
しかし..ここにキャッチがあります..
2 つの島の間の line() 上のグリッド ポイントに到達するたびに、その距離を隣接する島の最小値として記録する代わりに、長さ K の優先キューにする必要があります。そして、K 個の最短パスを記録します。他の line() のいずれかからその line() に
このプライオリティ キューは、次の line() に到達するまで同じままです。そこで、そのポイントに入るすべてのプライオリティ キューが集約されます。
ここに考えがあります。グリッドで、隣接する壁を島にグループ化し、すべての島をグラフ ノードとして扱います。ノード間の距離は、ノードを接続する (敵をブロックする) ために必要な壁の最小数です。
その場合、最も安価なアークをブロックすることで、パスの長さを最大化することができます。
私はアルゴリズムの専門家ではありませんが、グリッドを見ると、コンウェイのライフ ゲームが何らかの形で役立つのではないかと思います。合理的な初期シードと、タワーの誕生と消滅に関する適切に選択されたルールがあれば、短期間で多くのシードとその後の世代を試すことができます。
クリープの経路の長さにはすでに適合度の尺度があるため、それに応じて最適なものを選択できます。最適なパスにどれだけ近似するかはわかりませんが、ソリューションで使用するのは興味深いことです。
このアルゴリズムがリアルタイムである必要性を示していませんが、この前提については間違っている可能性があります。その後、ブロックの位置を事前に計算できます。
事前にこれを実行してから、単純に AIをビルドすることができればまるで一種の木であるかのように岩ごとに迷路を移動する場合は、遺伝的アルゴリズムを使用してヒューリスティックの必要性を軽減できます。任意の種類の遺伝的アルゴリズム フレームワークをロードする必要があります。まず、動かないブロック (マップ) とランダムに配置された可動ブロック (AI が配置するブロック) の集団から始めます。次に、移動可能なブロック上で交叉と変換を行うことによって個体群を進化させ、計算された最長経路に多くの報酬を与えることによって個体を評価します。次に、コードにヒューリスティックを含める必要なく、リソース効率の高いパス計算機を作成するだけで済みます。進化の最後の世代では、最高ランクの個人を採用します。これが解決策となり、このマップに必要なブロック パターンになります。
遺伝的アルゴリズムは、理想的な状況下で、合理的な時間内に極大値 (または極小値) に到達できることが証明されています。これは、十分に大きなデータ セット (つまり、状況に応じて十分な大きさのマップ) の分析ソリューションでは到達できない場合があります。
このアルゴリズムを開発する言語について言及していないため、ニーズに完全に適合するフレームワークを提案することはできません。
マップが動的である場合、つまりマップがタワー ディフェンスの繰り返しで変化する可能性がある場合、ウェーブごとに新しい人口全体を再進化させるには集中的すぎる可能性があるため、この手法は避けた方がよい場合があります。