A4B人工智能基本原理作业.doc

图搜索与问题求解
第一次作业
1。什么是状态空间图、状态（节点）、状态转换规则（边)、状态空间、隐式状态图
?求解过程的本质是什么？
，试分别设计该问题的状态、状态转换规则、状态空间，并描述求解过程
（1）传教士与野人问题:传教士（M）与野人（C）数目均为五人，渡船（Ｂ）最多可乘3人。　
（2）翻钱币问题:三枚钱币，能否从下面状态翻动三次后出现全正或全反状态
反
正
反
正
正
正
反
反
反
初始状态θs
目标状态集合{θ0 , θ7}
（３)已知桶、罐和瓶分别能存放水5０00ml、３500ml、1５00ｍl，现在桶中有５00０ml水，如何只利用这三件容器把水分成两份，每份250０ml
（４)Ｎ皇后问题就是在N*N的棋盘上放置N个皇后的方法解，满足每行、每列和对角线上只允许出现一个皇后,

第二次
ﻩ１．什么是启发性信息、完备的搜索、启发函数、加权状态图？
2．深度优先搜索和广度优先搜索过程的OＰEN表有何不同？
？
？
ﻩ5。为“倒水”问题设计一个启发函数
第三次
1。什么是与等价？什么是或等价?试分别用一个例子说明。
？什么是端节点？什么是与节点、或节点？
３。与或图搜索的可见性判别条件是什么?
／或/树,请分别按和代价法及最大代价法求解树的代价。
A
B
C
D
t2
t3
t4
t1
与/或树
5
6
2
1
7
2
2
3
E
　 5．　设有如图所示的博弈树,其中最下面的数字是假设的估值，请对该博弈树作如下工作:
（1) 计算各节点的倒推值；
利用α-β剪枝技术剪去不必要的分枝。
博弈树
3
0
5
-3
3
6
-2
3
5
4
-3
0
6
8
-3
3
6
9
S0
A
B
C
D
E
F
G
H
I
J
K
L
N
M
第四次
1、请将下列语句翻译成命题公式
(1）如果交通不堵塞，老王将准时到达火车站
（2）你去听课,他也去听课
(3）如果明天不下雪，我就去登山
(4）尽管他参加了考试,但他没有通过考试
２、请将下列语句翻译成谓词公式
(1）有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。
（2）他每天下午都去打篮球.
(3）西安市的夏天既干燥又炎热。
（4）并不是每一个人都喜欢吃臭豆腐。　
（5）喜欢读《三国演义》的人必读《水浒》。
(6）欲穷千里目，更上一层楼。
第5次

(1）$ｘ＄y（P（x，ｙ） ÙQ(x，y）)
（2)"x "y(P(x，y）　®Q(x,y))
(３)"x$y(（Ｐ（x，ｙ）　ÚQ（x，y)) ®R(ｘ,ｙ）)
ﻩ（4）"x　（Ｐ（ｘ) ®$y　(Ｐ（y) ÙR（x，y））)
（5）$x（P（ｘ) Ù"x(Ｐ(ｙ） ®R