1

我正在学习我的第一门人工智能课程，我必须在作业中定义一些问题（还没有解决它们，只是提供一个定义）。所以我必须定义布尔可满足性问题 ：

  1. 什么是状态？
  2. 初始状态是什么？
  3. 什么是最终状态？
  4. 运营商有哪些？

我的问题是：公式应该成为状态的一部分吗？

到目前为止的考虑：

  • 运算符不会改变它，它在计算过程中是恒定的，所以它不是。
  • 如果我确实包含它，理论上搜索空间会变得更大，因为可能有更多状态，但实际上公式无法更改，所以我得到一个大状态和一个不对应的分支因子。
  • 它从一个执行到下一个执行不同，所以它应该是状态的一部分。
4

2 回答 2

0

这只是给未来读者的注释-不是答案

Vic Smith 是对的，另一种看待这一事实的方式，in theory there are more states但实际上不是（我的第二个点），只是将其视为单独的束缚空间。例如，对于公式X or Y，有一个束缚空间，对于not X and Y另一个束缚空间，它们在表示中没有公共节点。

所以它可以从一个执行到另一个执行不同，但仍然具有相同的“可达”状态和相同的分支因子。并且每次执行都有不同的开始状态。

于 2012-08-31T09:43:52.913 回答
0

在进行这样的搜索时，您只需要真正考虑问题的不同部分是一种状态，尽管我会说在这种情况下它真的归结为您如何定义问题。

算法的给定运行的搜索空间取决于输入公式，但之后是固定的，即您正在搜索 n 长度位向量的空间，其中 n 是公式中的变量数。所以公式不是状态的一部分，因为它不会变化。

相反的说法是，您正在更大的公式向量对空间中搜索，但是由于您不能将公式作为问题的一部分进行更改，因此这并没有真正增加搜索空间的大小。所以我不会声称“如果我确实包含它，理论上搜索空间会变得更大”。不是，可达状态是一样的，分支是一样的，需要探索来解决问题的空间是一样的。

鉴于此，我的回答是该公式不是状态的一部分，而是定义了状态空间的性质。因此，您的四个问题的答案都将在某种程度上在功能上取决于公式，但状态仅取决于公式的长度。

希望这是有道理的！

于 2012-08-20T22:44:13.063 回答