博弈是一类具有竞争性的智能活动特点双方的智能活动,任何一方都不能单独控制博弈过程,而是由双方轮流实施其控制对策的过程。
对于八数码难题按下式定义估价函数:f(x)=d(x)+h(x),其中,d(x)为节点x的深度;h(x)是所有棋子偏离目标位置的曼哈顿距离(棋子偏离目标位置的水平距离和垂直距离和),例如下图所示的初始状态S0:8的曼哈顿距离为2;2的曼哈顿距离为1;1的曼哈顿距离为1;6的曼哈顿距离为1;h(S0)=5。初始状态(S0):目标状态:
(1)用A*搜索法搜索目标,列出头三步搜索中的OPEN、CLOSED表的内容和当前扩展节点的f值。
(2)画出搜索树和当前扩展节点的f值。
(1)如下表
(2)搜索树如下图,右上角的数字是其估价函数值