私は解決するための最良の経路問題があります。 walkableタイルとwalkableタイルが入力されたnxnグリッドがある場合、私は最短経路を通ってA点からB点に到達しなければなりません。 トリックは、歩行可能なタイルの一部にポイントが含まれています。私が目標に達するときに有効な解決策になるためには、ある程度のポイントが必要です。 タイルにはさまざまなポイントがあります（またはまったくありません）。目標に到達するには最短のパスが必要ですが、途中で少なくともMポイントも集まっています。グリッド内の最適なパス
私が試したのは、2点間の最短経路を見つけ、目標に到達したときだけでなく必要な点も持って停止条件を持つようにカスタマイズしようとしたA *アルゴリズムです。私はパスをブロックしているので、私はそれを作ったように動作しません。
この問題や他のアルゴリズムに近づける方法があれば、助けていただければ幸いです。おかげさまで
を使用することを計画している場合にも、consistenヒューリスティックを提供しなければならない、言ったようにあなたがまだこの問題に悩まされている場合、他の答え/コメントはあなたに部分的な答えを与えるだけです - ここでは問題空間に亀裂があります。
実際には、（ほとんど）並べ替えられていないMポイントパスをキャプチャするために、いくつかの変更を加えてA *を使用することができます。変更する必要があるのは、ヒューリスティックおよび終了基準だけです。
まず、M点を通る経路を考慮してヒューリスティックを変更する必要があります。ヒューリスティックは許容可能で一貫性がなければならないため、真のパスコスト以下の値に等しくなければならず、目標に近づくにつれて減少する（単調増加でなければならない）。
ここでは、あなたが完了しなければならないM個のサブパスとして考えることができます。それぞれのサブパスは、通常のパスとして機能します。したがって、単一の点グラフ（終端スペースのみ）では、ユークリッド距離のような標準的なヒューリスティックを使用することができます。これは、直線的な経路が最適であり、理想的な状況（それは容認できる）の下ではうまく行かないことを示唆する貪欲な推定値です。
2つ以上のパスの場合、欲張りのアプローチでは同様に、ポイント間のブロックされていない直線パスが最も速いと言います。それは、あなたがさらに遠ざかり、さらに良いスコアを持つことができないので、やはり一貫したヒューリスティックです。難しい部分は、許容可能なヒューリスティックを維持するために、M点の順序が障害なしで最も速いピッキングです。すべてのタイルが現在のタイルからM個のポイント、M-1個の残りのポイント、...、〜までのユークリッド距離を最初に検索することで、すべてのタイルが歩行可能であるグラフ内のMポイントの最適な選択を見つけることができます終端の四角。この操作は、到達する正方形ごとに行う必要があるため高価ですが、動的プログラミングまたは検索キャッシングを使用して、必要な償却計算を1ステップあたりO（M）に減らすことができます。
障害物なしで最速になるMポイントのパスを取得すると、そのパスの各ポイントと現在の位置の間のユークリッド距離をヒューリスティックとして使用できます。これは貪欲な動きの推定値なので、常に許容されます（推定コストを上回ることはできません）。次の貪欲な最適点から離れて現在のタイルとは異なる欲張り点を選ぶことができないため、容認できないだろう。
最後に、終了点をMポイントに達するまで変更する必要があります。最後のポイントは終了するタイルです。これは、Mを構築する必要なしにMグラフを歩くことを模倣する。可能なグラフを歩く。提供されたヒューリスティックは、基本的なアルゴリズムを変更することなくA *に魔法をさせ、ジェネリックグリッド上のヒューリスティックに必要な制約を維持しながら、あなたが得られるほど効果的でなければなりません。
私は問題を自分で解決しましたが、あなたの答えは私が行ったことに最も近いものです。 – Adrian
深度がXのレイヤーにあるときに、グラフにレイヤーを追加できます - >少なくともXポイントを収集しました。上のレイヤーからレイヤー+Nにグラフの適切なエッジを追加します。ここで、Nは現在のタイルのポイントの数です。
グラフは無限ですが、いくつかのエッジをトラバースするときに、頂点ハンドルにレイヤーの数を動的に追加することができます。そして、無限になるので、フィニッシュが到達可能かどうかを知ることはできませんが、ベースグラフのパスが存在するか、少なくとも1つのポイントがあるかどうかを確認できます。
レベル>Mに仕上げを行う必要があります。
あなたには、いくつかの明確化が必要な場合は、尋ねる=）
編集
@Pyrceはあなたでは*にhttp://en.wikipedia.org/wiki/Consistent_heuristic
+1クリーンな答えのために、彼のグラフは無限大ではないかもしれませんが、ちょうど多分本当に大きいのは、あなたは順列（M）の方法でM個の点しか捕捉できないからです。また、ヒューリスティックがA *のために変更する必要があることを追加することもできます。つまり、距離はもはや2Dにはなりません。 – Pyrce
@Pyrce一般に、グラフは無限です。なぜなら、 'M'は開始と終了のような入力パラメータですからです。しかし、私はabs（cur_level - M）のような加重加算で通常のヒューリスティック（マンハッタン距離）はそれを正しく行うだろうと思う。 – kassak
はい、しかしMは固定されているアルゴリズムを開始し、変更されません。 4ポイントのMは24の可能な置換を提供し、したがってグラフサイズはN×N×（M！）= 24N^2となる。大きくても無限よりはるかに小さい。問題を開始するために、NとMの無限の可能な選択肢があることを認めます。あなたが示唆するヒューリスティックは許容可能ですが、解決ポイントの穴に落ち込んでM点に達する前に、一貫性がなくなります。 http://en.wikipedia.org/wiki/Consistent_heuristicを参照してください。ちょうどあなたがあなたの答えにそれを加えるべきだと思った。 – Pyrce
ダイクストラのアルゴリズムを見ましたか？ – Caesar
同じタイルのポイントを複数回拾うことはできますか？言い換えれば、グリッドにポイントを持つタイルを含むループがある場合、有効なパスに最終的な目的地に到着する前に必要な数のポイントを提示するループを含めることができますか？ – dasblinkenlight
@Caesar「プレーン」ダイクストラ（またはFloyd-Warshall）は、最適化タスクに2番目の次元があるため、助けにはなりません。 – dasblinkenlight