次の問題を解決しようとしています: 空域を飛行する飛行機で構成され、最寄りの空港に着陸しようとする 2D タイル ゲームがあります (「n」個のゴールが存在する可能性があります)。アイデアは、衝突を回避して、飛行機が自分で最適な経路を検索するようにすることです。
そこで、A* アルゴリズムを試してみようと思ったのですが、別の制限が見つかりました。飛行機は必要に応じて高度を変更できます。そこで私は、A* と同じ哲学を 3D で実装するというアイデアを思いつきました (ノードを可能な移動に拡張し、平面を上、下、下北、上東などに移動させ、抽象的な 3D を作成します)相対高度を処理し、アルゴリズムが 3D 移動で最適なパスを見つけられるようにします)。
ヒューリスティックについては、アルゴリズムをより効率的にしたかったのでマンハッタン距離を破棄しました (優れたヒューリスティックはより効率的な検索を行い、マンハッタンはコストを過大評価し、対角移動を使用していることを知っているため)。対角距離 (マンハッタンとユークリッドの両方の側面を組み合わせたもの)、8 隣接 (対角移動でもノードを拡張) に推奨されます。しかし、私はより多くの隣接関係を持っているので、対角線距離の式を 16 隣接関係に適合させようとしていました (上北東、下南西などの上下の対角線を除く)。対角移動」(私が言及したものを除く) のコスト値は同じです (1 対角移動 = 2 直交移動であり、除外した「上下対角線」にある 3 ではありません)。
ノード A をスタート、B をゴールとし、それぞれの位置を (xa,ya,za) と (xb,yb,zb) とする
numberOfDiagonalSteps = min{|xa-xb|,|ya-yb|,|za-zb|}
マンハッタン距離 = |xa-xb| + |ya-yb| + |za-zb|
numberOfStraightSteps = manhattanDistance - 2*numberOfDiagonalSteps
そして、対角線のステップのコストが sqrt(3) であると仮定します (ご存知のように、ピタゴラス、直交コストは 1 です)。
ヒューリスティックは次のとおりです: h(n) = numberOfStraightSteps + sqrt(3)*numberOfDiagonalSteps
ええと... 私の質問の 1 つは、飛行機が動いているとき (「障害物ノード」)、アルゴリズムを更新して再実行する必要があるということです。というか…そのままやってみるか、D*-Lite を実装してみるか。
もう 1 つの質問は、時間の複雑さについてです。これらのアルゴリズムの最悪のケースが指数関数的であることは明らかですが、優れたヒューリスティックによって実際に改善することができます。しかし、問題のアルゴリズムを正確に分析する方法がわかりません。そのアルゴリズムにどのくらいの複雑さを与えることができますか、または私の場合は何をするように提案しますか?
ご清聴ありがとうございました。