5

同時に行われる決定を最適化して、妥当な時間で迅速な結果を見つけるための最良のアルゴリズムを探しています。同時実行は多くの「ティック」を実行し、場合によっては決定を下す必要があります。最終的には目標状態に到達します。（非常に悪い決定をした場合、目標状態に到達することは決してありません）

多くの目標状態があります。ティック数が最も少ない目標状態を見つけたい（ティックは実際の生活ではおよそ1秒に相当する）。基本的には、できるだけ数秒で目標に到達するためにどの決定を下すかを決定したい。

問題のあるドメインに関するいくつかのポイント：

  • すぐに、解決策につながる一連の選択肢を生成できます。最適ではありません。
  • 何が適切な決定であるかを判断するための合理的なヒューリスティック関数があります
  • ノードからゴールまでの最小の時間コストを決定するための合理的な機能があります。

アルゴリズム：

  • この問題を約10秒間処理してから、可能な限り最善の答えを出す必要があります。
  • 私はA*が私に最適な解決策を見つけるだろうと信じています。問題は、決定木が非常に大きくなり、十分な速さで計算できないことです。
  • IDA *は、10秒で最初のいくつかの良い選択肢を与えてくれますが、ゴールまでの道が必要です。

現時点では、目標への既知の最適ではないパスから始めて、おそらくシミュレートされたアニーリングを使用して、10秒以上かけて改善を試みることを考えています。

この種の問題を解決するために研究するのに良いアルゴリズムは何でしょうか？

4

2 に答える 2

1

いくつかの事実を明らかにしましょう。

1）どの決定が最良であるかを確実に知る唯一の方法は、考えられるすべての決定をテストし、いくつかの基準に基づいて結果を評価することです。

2）考えられるすべての決定を行うことを決定する時間がない可能性が非常に高いため、将来、決定を評価する範囲を制限する必要があります。

3）私たちは最高の動きをする可能性は非常に低いです。頻繁にだけでなく、これまでに。決定が2、3しかない場合を除いて、決定を下すたびに、到達できなかったより良い決定があった可能性があります。

4）以前の決定がどのようにうまくいったかを利用することができます。

これらすべてをまとめると...決定が下されたときに、30ティック先に何が起こるかを評価し、30ティックで、実際に起こったことが30ティック前にシミュレートしたものと一致するかどうかを確認できます。もしそうなら、私たちは決定が予測可能な結果につながることを知っているので、その決定をあまり使わないでください。そうしなかった場合、または期待よりも良い結果が得られた場合は、その決定をさらに使用する必要があります。

理想的には、ロジックを評価する目的で、シミュレーションのシミュレーションでロジックを使用します。次に、「実際の」シミュレーションに到達すると、より適切な決定をより早く選択できる可能性が高くなります。もちろん、シミュレーションのシミュレーション結果ではなく、実際のシミュレーション結果の結果に高い重みを付けてください。

于 2011-02-24T01:03:23.013 に答える
1

最大不一致検索またはビーム検索の制限をますます緩く繰り返して、制限付き不一致検索を見てください。

優れたヒューリスティックがあれば、それを使用して個々の選択肢を比較できるはずです-限られた不一致の検索では、部分的なソリューションを比較して、ビーム検索では。

部分解の拡張がどれだけ優れているかについて上限を設定できるかどうかを確認してください。次に、ヒューリスティックからの結果、または深さを増す一連の反復検索でこれまでに見つかった最良の結果を打ち負かすために拡張できない可能性のある部分的なソリューションを取り除くことができます。

于 2011-02-24T05:46:03.167 に答える