1

私はAIの最初のコースを受講していますが、宿題でいくつかの問題を定義する必要があります（まだ解決していないので、定義を提供するだけです）。だから私はブール充足可能性問題について定義する必要があります ：

  1. 状態とは何ですか？
  2. 初期状態は何ですか？
  3. 最終状態とは何ですか？
  4. 演算子は何ですか？

私の質問は：式は州の一部であるべきですか？

これまでの考慮事項：

  • オペレーターはそれを変更せず、計算を通じて一定であるため、変更されません。
  • これを含めると、理論的には、より多くの状態が可能になるため、検索スペースがはるかに大きくなりますが、実際には数式を変更できないため、大きな状態になり、対応しない分岐係数が得られます。
  • 実行ごとに異なるため、状態の一部である必要があります。
4

2 に答える 2

0

このような検索を行うときは、問題のさまざまな部分を状態と見なすだけで済みますが、この場合は、問題をどのように定義するかによって決まります。

アルゴリズムの特定の実行の検索スペースは入力式によって異なりますが、その後は固定されます。つまり、nは式内の変数の数である、n個の長さのビットベクトルのスペースを検索します。したがって、数式は変化しないため、状態の一部ではありません。

反訴は、数式とベクトルのペアのより大きなスペースで検索しているというものですが、問題の一部として数式を変更できないため、検索スペースのサイズは実際には増加していません。したがって、「これを含めると、理論的には検索スペースがはるかに大きくなる」とは主張しません。そうではなく、到達可能な状態は同じであり、分岐は同じであり、問​​題を解決するために探索する必要があるスペースは同じです。

これを考えると、私の答えは、式は状態の一部ではなく、状態空間の性質を定義するということです。したがって、4つの質問に対する答えは、それぞれ何らかの方法で数式に機能的に依存しますが、状態は数式の長さにのみ依存します。

それが理にかなっていることを願っています！

于 2012-08-20T22:44:13.063 に答える
0

これは将来の読者への単なるメモです-答えではありません

ヴィック・スミスは正しいです。実際にはそうではありin theory there are more statesませんが（私の2番目の点）、それを別個の束縛空間として考えることであるという事実を見る別の方法です。たとえば、式のX or Y場合、1つのボンデージスペースがあり、not X and Y別のボンデージスペースがあり、表現に共通のノードがありません。

したがって、実行ごとに異なる可能性がありますが、それでも同じ「到達可能」状態と同じ分岐係数があります。また、実行ごとに異なる開始状態があります。

于 2012-08-31T09:43:52.913 に答える