ループに入ったりアクションを繰り返したりしないように STRIPS を変更するにはどうすればよいですか? A - B - C - D - E の領域 (トラバース問題) があるとしましょう。それらはすべて双方向です。初期状態は At(A) であり、目標は At(E) になる必要があることです。結果は
`Travel(A, B) - Travel(B, C) - Travel(C, D) - Travel(D, C) -
Travel(C, B) - Travel(B, C) - Travel(C, D) - Travel(D, E).
要するに、A - B - C - D - C - B - C - D - E と進みました。これを解決する方法と、より良い疑似コードを提供できるかどうかについてのアイデアが必要です。ありがとう！
あなたが直面している問題は、アルゴリズムが最良の回答ではなく「回答」を返していることです。問題は同形であるため、検索アルゴリズムと、それらが最短経路を見つけることを保証する方法を確認する必要があります。
これらの結果が得られる理由は多数ありますが、一般的には、使用している検索方法に関連しているはずです。ノード間に何らかの暗黙の順序設定があるため、アルゴリズムは直接「Eに進む」前に「Cに戻る」ことを試みます。
A からは B にしか行けないことに注意してください。B から C に行くことも A に行くこともできます - そしてあなたは C に行きます。アルゴリズムが A から B から A (...) への無限ループに入らない場合は、単純な深さ優先検索を適用していない可能性が高くなります。ここで重要なのは、アルゴリズムが D に到達したときに C に戻ることを決定した理由を理解することです。
アルゴリズムと入力の詳細を理解することとは別に、いくつかのアイデアを次に示します。
すでに訪問したノードのリストがあり、訪問していないノードを優先した場合、おそらくより良い/最適な答えが見つかるでしょう。それらの間の接続が変わらない場合、ノードを 2 回訪問する必要がありますか?
または、答えに到達するまでのステップ数を制限していますか? 目標に到達するまでに必要な最大ステップ数が事前にわかっている場合は、答えをそのステップ数に制限すると、最適な答えが得られるはずです。
最初の結果に達したときに停止するのではなく、単純に検索を続行し、別のソリューションを比較することも可能です。これはパフォーマンスが著しく低下する可能性がありますが、状況によっては必然的にパフォーマンスが低下することもあります。