解決すべきベスト パスの問題があります。歩行可能なタイルと歩行不可能なタイルが配置された nxn グリッドが与えられた場合、最短経路を通って点 A から点 B に到達する必要があります。トリックは、いくつかの歩行可能なタイルにポイントが含まれていることです。目標に到達したときに有効なソリューションになるには、一定数のポイントが必要です。タイルにはさまざまな数のポイントがあり (またはなし)、目標に到達するための最短経路が必要ですが、途中で少なくとも M ポイントを収集する必要もあります。
私が試したのは、2 点間の最短経路を見つける A* アルゴリズムで、ゴールに到達したときだけでなく、必要な点もある停止条件を持つようにカスタマイズしようとしました。パスをブロックしているため、作成した方法では機能しません。
この問題へのアプローチ方法や、より適した別のアルゴリズムに関する提案があれば、助けていただければ幸いです。ありがとう。
深さのレイヤーにいる場合、グラフにレイヤーを追加できますX->少なくともXポイントを収集しました。上のレイヤーから、現在のタイルのポイント数である+Nレイヤーに、グラフに適切なエッジを追加します。N
グラフは無限ですが、いくつかのエッジをトラバースするときに、レイヤーの数を頂点ハンドルに動的に追加できます。また、無限なので、finishに到達できるかどうかはわかりませんが、ベースグラフ上のパスが存在するかどうか、および少なくとも1つのポイントがあるかどうかを確認できます。
レベルに仕上げを配置する必要があります>M。
説明が必要な場合は、質問してください =)
編集
@Pyrceが言ったように、A * http://en.wikipedia.org/wiki/Consistent_heuristicを使用する予定がある場合は、一貫したヒューリスティックも提供する必要があります
他の回答/コメントでは部分的な回答しか得られないため、まだこの問題に悩まされている場合は、問題のスペースに亀裂があります。
実際には、(ほとんど) 順不同の M ポイント パスをキャプチャするために、いくつかの変更を加えて A* を使用できます。変更する必要があるのは、ヒューリスティックと終了基準だけです。
最初に、ヒューリスティックを変更して、M ポイントを通るパスを考慮する必要があります。ヒューリスティックは許容可能で一貫している必要があるため、真のパス コスト以下の値である必要があり、目標に近づくにつれて減少するだけです (単調に増加する必要があります)。
現在通っているパスは、完了しなければならない M 個のサブパスと考えることができ、それぞれが通常のパスとして機能します。したがって、単一点グラフ (終端スペースのみ) の場合、ユークリッド距離のような標準的なヒューリスティックを使用できます。これは、まっすぐな道が最適であり、理想的な状況下ではこれ以上うまくいかないことを示唆する貪欲な見積もりです (それは許容されます)。
複数のパスの場合、貪欲なアプローチは同様に、ポイント間のブロックされていない直線パスが最速であると述べています。また、これ以上離れてもスコアが高くなることはないため、一貫したヒューリスティックでもあります。困難な部分は、許容可能なヒューリスティックを維持するために、M ポイントのどの順序付けが障害物なしで最速であるかを選択することです。現在のタイルから各 M ポイント、残りの M-1 ポイントのそれぞれまでのユークリッド距離を幅優先検索することにより、すべてのタイルがウォーク可能であるグラフ内の M ポイントの最適な選択を見つけることができます。終点の広場。この操作は、到達する正方形ごとに実行する必要があるためコストがかかりますが、動的プログラミングまたは検索キャッシュを使用して、必要な償却計算をステップごとに O(M) に減らすことができます。
ここで、障害物がなければ最速の M ポイント パスを取得したら、そのパスの各ポイントと現在の位置の間のユークリッド距離をヒューリスティックとして使用できます。これは貪欲な動きの推定であるため、常に許容され (推定コストを超えることはできません)、現在のタイルとは異なる貪欲なポイントを選択するために、次の貪欲な最適ポイントから離れてコストを削減できないため、一貫性があります。認められないでしょう。
最後に、終了基準を M ポイントに到達するように変更する必要があります。ここで、最後のポイントは終了タイルです。これは、M を構築する必要なしに M グラフを歩くことを模倣します! 可能なグラフを歩きます。提供されたヒューリスティックにより、A* は基礎となるアルゴリズムを変更せずに魔法のように機能し、ジェネリック グリッドのヒューリスティックに必要な制約を維持しながら、可能な限り効果的なものになるはずです。