|
近年来，人工智能成为了一个越来越火热的名词，今天笔者将带领大家学习最基本的知识，确定性推理，在学习这部分知识之前，希望你有一些离散数学的基础，这样可以帮助你更快的学习。1.启发式搜索与评价函数与8数码问题
首先是我们的老朋友，8数码问题，在8数码问题求解方法中深度优先，广度优先以及代价树算法被称为盲目搜索，而A以及A* 算法被称为启发式搜索，在这里笔者将以启发式搜索为例为大家讲述8数码问题。
首先来看什么是A算法以及什么是A* 算法
A算法 ：在图搜索算法中，如果能在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对OPEN表中的节点进行排序，则该搜索算法为A算法。
A算法中计算的是错误的数字的个数+深度，而在A* 算法中我们需要计算的是位置错误的数字移动到正确位置所需的步骤之和+深度
由于估价函数中带有问题自身的启发性信息，
可根据搜索过程中选择扩展节点的范围，将启发式搜索算法分为
全局择优搜索算法： 从OPEN表的所有节点中选择一个估价函数值最小的一个进行扩展。
局部择优搜索算法：仅从刚生成的子节点中选择一个估价函数值最小的一个进行扩展。
下图所示为A算法解决8数码问题，简单说明一下，要从初始状态S0到目标状态Sg，首先进行第一层扩展，将空格上下左右移动得到第二层，第二层第一个结果里位置错误的数字共有3个，加上深度为1，所以为4，同理计算出其他的，由于4是最小的将其进行拓展以此类推直到找到目标Sg。
接下来是A*算法，与A不同的是计算的是错误数字移动到正确位置所需要移动的步数，例如第二层第一个，错位数字为128，共需移动5步，所以f6，依次类推进行计算、2.消解原理的证明问题
已知
F: (∀x)((∃y)(A(x, y)∧B(y))→(∃y)(C(y)∧D(x, y)))
G: ﹁(∃x)C(x)→(∀x)(∀y)(A(x, y)→﹁B(y))
求证G是F的逻辑结论。
证明：先把G否定，并放入F中，得到的{F, ﹁G}：
{(∀ x)((∃ y)(A(x,y)∧B(y))→(∃ y)(C(y)∧D(x,y))),
﹁(﹁(∃ x)C(x)→(∀ x)(∀ y)(A(x,y)→﹁ B(y)))}
再把{F,﹁G}化成子句集，得到
(1) ﹁A(x,y)∨﹁ B(y) ∨C(f(x))
(2) ﹁ A(u,v)∨﹁ B(v) ∨D(u,f(u))
(3) ﹁ C(z)
(4) A(m,n)
(5) B(k)
最后应用谓词逻辑的消解原理对上述子句集进行消解，其过程为：
(6) ﹁ A(x,y)∨﹁ B(y) (1)和(3)消解，取σ={f(x)/z}
(7) ﹁ B(n) (4)和(6)消解，取σ={m/x,n/y}
(8) NIL (5)和(7)消解，取σ={n/k}
因此，G是F 的逻辑结论。
上述消解过程可用如下消解树来表示
“快乐学生”问题
假设：任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过所有考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。
求证：张是快乐的。
解：先定义谓词：
Pass(x, y)：x可以通过y考试
Win(x, prize)：x能获得奖励
Study(x) ：x肯学习
Happy(x)：x是快乐的
Lucky(x) ：x是幸运的
再将问题用谓词表示如下：
“任何通过计算机考试并奖的人都是快乐的”
(∀x)(Pass(x, computer)∧Win(x, prize)→Happy(x))
“任何肯学习或幸运的人都可以通过所有考试”
(∀x) (∀ y) (Study(x)∨Lucky(x)→Pass(x, y))
“张不肯学习但他是幸运的”
﹁Study(zhang)∧Lucky(zhang)
“任何幸运的人都能获奖”
(∀x) (Lucky(x)→Win(x, prize))
结论“张是快乐的”的否定
﹁Happy(zhang)
将上述谓词公式转化为子句集如下：
(1) ﹁Pass(x, computer)∨﹁Win(x, prize)∨Happy(x)
(2) ﹁Study(y)∨Pass(y, z)
(3) ﹁Lucky(u)∨Pass(u, v)
(4) ﹁Study(zhang)
(5) Lucky(zhang)
(6) ﹁Lucky(w)∨Win(w, prize)
(7) ﹁ Happy(zhang) (结论的否定)
按消解原理进行消解，消解树如下：3.消解原理求解问题
已知：“张和李是同班同学，如果x和y是同班同学，则x的教室也是y的教室，现在张在302教室上课。”
问：“现在李在哪个教室上课？”
解：首先定义谓词
C(x, y)：x和y是同班同学
At(x, u)：x在u教室上课。
把已知前提用谓词公式表示如下：
C(zhang, li)
(∀x) (∀y) (∀u) (C(x, y)∧At(x, u)→At(y,u))
At(zhang, 302)
把目标的否定用谓词公式表示如下：
﹁(∃v)At(li, v)
把上述公式化为子句集：
C(zhang, li)
﹁C(x, y)∨﹁At(x, u)∨At(y, u)
At(zhang, 302)
把目标的否定化成子句式，并用下面的重言式代替：
﹁At(li,v) ∨At(li,v)
把此重言式加入前提子句集中，得到一个新的子句集，
对这个新的子句集，应用消解原理求出其证明树。
求解过程如下图所示。该证明树的根子句就是所求的答案，即“李明在302教室”。
已知：A,B,C三人中有人从不说真话，也有人从不说假话。某人向这三人分别提出同一个问题：谁是说谎者？
A答：“B和C都是说谎者”；
B答：“A和C都是说谎者”；
C答：“A和B中至少有一个是说谎者”。
问：求谁是老实人，谁是说谎者？
解：首先定义谓词
T(x)：表示x说真话
把已知前提用谓词公式表示如下：
有人从不说真话：¬T(C )∨¬T(A)∨¬T(B)
有人从不说假话：T(C )∨T(A)∨T(B)
根据“A答：B和C都是说谎者”，则
若A说真话：T(A)→¬T(B)∧¬T(C )
若A说假话： ¬T(A)→T(B)∨T(C )
同理：
根据“B答：A和C都是说谎者”，则
T(B)→¬T(A)∧¬T©
¬T(B)→T(A)∨T©
根据“C答：A和B中至少有一个是说谎者”，则
T( C)→¬T(A)∨¬T(B)
¬T(C )→T(A)∧T(B)
把上述公式化成子句集，得到前提子句集S：
¬T(A)∨¬T(B)
¬T(A)∨¬T(C )
T(C )∨T(A)∨T(B)
¬T(B)∨¬T(C )
¬T(C )∨¬T(A)∨¬T(B)
T(A)∨T(C )
T(B)∨T(C )
先求谁是老实人，结论的否定为： ¬ (∃x)T(x)
把目标的否定化成子句式，并用下面的重言式代替：
¬T(x)∨T(x)
把此重言式加入前提子句集S，得到一个新子句集，
对这个新的子句集，应用消解原理求出其证明树。
下面证明A不是老实人，结论的否定为： ¬T(A)
将结论的否定¬ (¬T(A)) 加入并入前提子句集S中，
应用消解原理对新的子句集进行消解：
以上便是我们在确定性推理中常见的一些问题以及其解决办法，希望引发大家的思考。
|