人工智能第三次作业

人工智能第三次作业1.何谓估价函数，在估价函数中，g(n)和h(n)各起什么作用？答：估价函数是用来估计节点重要性的函数。估价函数)(nf被定义为从初始节点0S出发，约束经过节点n到达目标节点gS的所有路径中最小路径代价的估计值。它的一般形式为)()(g)(nhnnf，式中，g(n)是从初始节点0S到节点n的实际代价；h(n)是从节点n到目标节点gS的最优路径的估价代价。对g(n)的值，可以按指向父节点的指针，从节点n反向跟踪到初始节点0S，得到一条从初始节点0S到节点n的最小代价路径，然后把这条路径上所有有向边的代价相加，就得到g(n)的值。对h(n)的值，则需要根据问题自身的特性来确定，它体现的是问题自身的启发性信息，因此也称h(n)为启发函数2.设有如下结构的移动将牌游戏：BBWWE其中，B表示黑色将牌，W表是白色将牌，E表示空格。游戏的规定走法是：(1)任意一个将牌可移入相邻的空格，规定其代价为1；(2)任何一个将牌可相隔1个其它的将牌跳入空格，其代价为跳过将牌的数目加1。游戏要达到的目标什是把所有W都移到B的左边。对这个问题，请定义一个启发函数h(n)，并给出用这个启发函数产生的搜索树。你能否判别这个启发函数是否满足下界要求？在求出的搜索树中，对所有节点是否满足单调限制？答：设h(x)=每个W左边的B的个数，其搜索树如下:BBWE)x(*3)x(d)x(hfWBBWE)x(*3)x(d)x(hfWBBWE)x(*3)x(d)x(hfWBEWW)x(*3)x(d)x(hfBf(x)=0+12=1f(x)=1+12=13f(x)=1+12=13f(x)=2+9=11