再上一篇:2. 2  启发函数
上一篇:2. 3  * 搜索算法
主页
下一篇: 第 3 章  霍普费尔德神经网络
再下一篇:3. 2  连续霍氏网
文章列表

2. 4  习题

《用于最优化的计算智能》 Nirwan Ansari Edwin Hou 著 李军 边肇祺 译 清华大学出版社

1 2 3

2.1  考虑第 2. 1节中的 8 数码问题。给定起始节点为 8 5 且终止节点为

7 6 4

1 2 3

8 4 ,用A* 算法及下列各启发函数构造搜索图。

7 6 5

(1) h(n)= 0。

(2) h(n)= Misplaced(n),其中Misplaced(n)为离家将牌数。

(3) h(n)= seq(n),其中seq(n)对居于正中位置的将牌为1,而对于那些位于四周、其数码却又不按顺时针由小到大排序(跟在其后将牌数码不是比它刚好大1)的将牌为2。

2.2  计算下图g* ,h* ,f* 的值。

V= {s,a,b,c,d,e,i,j,k,l,m}

#第13页-

cost(s,a) = 1  cost(s,b) = 2  cost(s,c) = 2

cost(a,d) = 3 cost(a,i) = 4 cost(a,j) = 7

cost(b,d) = 1 cost(b,e) = 2 cost(b,i) = 1

cost(c,i) = 3 cost(c,m) = 5 cost(d,k) = 2

cost(e,j) = 1 cost(i,l) = 1 cost(i,m) = 2

2.3  考虑一个具有如下起始布局的积木游戏:

B B B W W W

其中有三个黑色将牌(B),三个白色将牌(W)和一个空格。将牌可按如下规则移动:

(1) 将牌可以代价1移到相邻的空格上去。

(2) 将牌可越过最多两个其它将牌而跳到空格上去,且代价为其跳过的将牌数。

这一游戏的目标是使所有白色将牌都在任一黑色将牌的左侧(不管空格的位置在哪

里)。为这个问题选择一个启发函数并给出搜索图产生过程。

2.4  8皇后问题是要找出一个在8 8国际象棋盘上摆放8个皇后而又使它们互不

威胁的布局(见第3章)。

(1) 设计一个表示8皇后问题布局的方案。

(2) 为8皇后问题定义一个可行的启发函数。

#第14页-