0

Wumpus 世界是知识表示、推理和规划的一个例子——代理人必须探索一个由一系列相互连接的房间组成的洞穴。在山洞里的一个房间里，有一只乌普斯，如果它进入那个房间就会杀死特工。有些房间有坑，如果特工也进入其中任何一个房间，它就会死。特工有一支箭可以杀死Wumpus。目标是找到隐藏在洞穴某处的黄金，并在不被杀死的情况下返回起点。

http://www.cis.temple.edu/~giorgio/cis587/readings/wumpus.shtml

正好有一个 Wumpus。因此W1,1 ∨ W1,2 ∨ ... W4,3 ∨ W4,4

一种说最多有一个 wumpus 的方法是，对于任何 2 个方格，其中一个必须是无 wumpus 的。使用n 个正方形，我们得到n(n-1)/2 个句子，例如 ¬W1,1 ∨ ¬W1,2 。对于一个 4*4 的世界，我们从总共 155 个包含 64 个不同符号的句子开始。

我无法理解我们如何得到n(n-1)/2 个句子。还有——我们怎么知道在一个 4*4 的世界中我们总共有 155 个句子？有人可以向我解释这个概念吗？谢谢。

4

1 回答 1

0

在 4*4 的世界中，您总共有 16 个方格。我们正在为每对状态创建一个句子。不失一般性，我们可以将每个二维索引 (r,c) 转换为一维索引 (r*4 +c)。这只是一个简化步骤。从算法上讲，您可以将这些句子的创建写为：

for(i = 0; i < 16; ++i)
  for(j = i+1; j < 16; ++j)
    print ~Wi v ~Wj

然后我们可以分析为 i 循环的每次迭代所做的打印语句的数量。

i = 0：15 个句子

i = 1：14 个句子

...

i = 15: 1 句话

所以在这种情况下，句子的数量是数字 1 到 15 的总和。众所周知的公式是 n(n-1) / 2，给出的答案是 105。这与你所说的 155 的答案不同，所以我不知道你从哪里得到这个号码。155 不是该公式可以找到的数字。

另外，请注意，我使用的 n 与平方数不同；它比平方数少一。原因是您不希望像 ~W1,1 v ~W1,1 这样比较同一个正方形的语句。

于 2013-01-23T14:14:05.237 回答