まず、知らない人のために-Anytime Algorithmは、実行可能な時間を入力として取得するアルゴリズムであり、その時間に可能な最善のソリューションを提供する必要があります。
重み付けされたA*はA*と同じですが、f関数に1つの違いがあります。
（ここで、gはノードまでのパスコストであり、hはゴールに到達するまでのパスの終わりまでのヒューリスティックです）
Original = f(node) = g(node) + h(node)
Weighted = f(node) = (1-w)g(node) +h(node)
私のいつでもアルゴリズムは、制限時間に達するまで、1から0.5までの重みを減らしてWeightedA*を実行します。
私の問題は、ほとんどの場合、これが解決策に到達するまでにかなりの時間がかかることです。10秒のようなものが与えられた場合、通常は解決策が見つかりませんが、ビームのような他のアルゴリズムは0.0001秒で解決策を見つけます。
何をすべきかアイデアはありますか？
私があなたなら、無制限のヒューリスティックを捨てます。許容できるヒューリスティックは、見つけた解の重み値が与えられた場合、最適な解の長さの最大 1/weight 倍であると言うことができるという点ではるかに優れています。
A* 派生物を実装する際の大きな問題は、データ構造です。双方向検索を実装したとき、配列リストからハッシュ拡張優先度キューと配列リストの組み合わせにオンデマンドで変更するだけで、ランタイム コストが文字通り 3 桁削減されました。
主な問題は、ほとんどの論文がセット ロジックを使用したアルゴリズムの疑似コードしか示していないことです。コードでセットを表現する方法を実際に理解するのはあなた次第です。1 つのリスト (つまり、開いているリスト) に複数の ADT を使用することを恐れないでください。Anytime Weighted A* について 100% 確信があるわけではありませんが、AWA* ではなく、Anytime Dynamic A* や Anytime Repairing A* などの他の派生物を作成しました。
もう 1 つの問題は、g 値を低く設定しすぎると、g 値が高い場合よりも解を見つけるのに時間がかかる場合があることです。よくある落とし穴は、閉じたリストで重複した状態をチェックするのを忘れていることです。その結果、(g 値が 0 に減ると無限の) ループに陥ります。ビーム検索ですぐに結果が得られる場合は、0 よりかなり高い値から始めてみてください。
ここでは、いくつかの疑似コードが役立つ可能性があります。とにかく、これらは問題に関する私の考えに過ぎません。あなたはすでにそれを解決しているかもしれません-あなたにとても良いなら:)
A* サーチが完了しているのに対し、ビーム サーチは不利な状態を除去するため、完全ではありません。解決しようとしている問題に応じて、不完全であるために解決策を見つけることができない場合 (通常、出発地から目的地までの正しいパスが多数存在する場合) は、ビーム検索に進みます。それ以外の場合は、AWA* を使用します。ただし、十分なハードウェア リソースがあれば、常に両方を並行して実行できます。