浅析计算机人工智能启发式搜索函数

《浅析计算机人工智能启发式搜索函数》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、浅析计算机人工智能启发式搜索函数　　摘要：阐述了人工智能的核心问题及启发式搜索函数的基本概念，介绍了4种经典问题启发式搜索函数的选择及其研究中遇到的难题，并从中求解来探讨解决问题的思路。　　关键词：人工智能；问题求解；启发式搜索函数　　中图分类号：TP18文献标识码：A文章编号：1009-3044(xx)08-10ppp-0c　　　　人工智能问题广义地说，都可以看作是一个问题求解过程，因此问题求解是人工智能的核心问题，它通常是通过在某个可能的解答空间中寻找一个解来进行的。在问题求解过程中，人们所面临的大多数现实问题往往没有确定性的算法，通常需要用搜索算法来解决。目标和

2、达到目标的一组方法称为问题，搜索就是研究这些方法能够做什么的过程。问题求解一般需要考虑两个基本问题：首先是使用合适的状态空间表示问题，其次是测试该状态空间中目标状态是否出现。　　　　1什么是启发式搜索函数　　　　在人工智能中有很大一类问题的求解技术依赖于搜索。启发式方法就是采用有利于问题自身特征信息来引导搜索过程的方法，在学生学习过程中启发式函数的选取至关重要，决定整个算法的效率与成败。启发式搜索通常用于两种不同类型的问题：前向推力和反向推理。前向推理一般用于状态空间的搜索。在前向推理中，推理是从预定义的初始状态出发向目标状态反向方向执行；反向推理一般用于问题归约中。

3、在反向推理中，推理是从给定的目标状态向初始状态执行。　　用来评估节点重要性的函数称为评估函数。评估函数f(x)定义为从初始节点S0出发，约束地经过节点x到达目标节点Sg的所有路径中最小路径代价的估计值。其一般形式为：　　　　其中，g(x)表示从初始节点S0到节点x的实际代价；h(x)表示从x到目标节点Sg的最优路径的评估代价，它体现了问题的启发式信息，其形式要根据问题的特征确定，h(x)称为启发式函数。因此，启发式方法把问题状态的描述转换成了对问题解决程度的描述，这一程度用评估函数的值来表示。　　　　滑动积木游戏启发式搜索函数　　　　滑动积木块游戏的棋盘结构及某一种将

4、牌的初始排列结构如下：　　　　其中B表示黑色将牌，W表示白色将牌，E表示空格。游戏的规定走法是：　　任意一个将牌可以移入相邻的空格，规定其耗散值为1；　　任意一个将牌可相隔1个或2个其他的将牌跳入空格，规定其耗散值等于跳过将牌的数目；游戏要达到的目标是使所有白将牌都处在黑将牌的左边。对这个问题，定义一个启发函数h(n)，并给出利用这个启发函数用算法A求解时所产生的搜索树。可定义h为：h＝B右边的W的数目　　　　很多知识对求解问题有好处，这些知识并不一定要写成启发函数的形式，很多情况下，也不一定能清晰的写成一个函数的形式。由题意，在目标状态下，一个扇区的数字之和等于12

5、，一个相对扇区的数字之和等于24，而一个阴影扇区或者非阴影扇区的数字之和为48。　　为此，我们可以将目标进行分解，首先满足阴影扇区的数字之和为48。为了这个目标我们可以通过每次转动圆盘45o实现。在第一个目标被满足的情况下，我们再考虑第二个目标：每一个相对扇区的数字和为24。在实现这个目标的过程中，我们希望不破坏第一个目标。为此我们采用转动90o的方式实现，这样即可以调整相对扇区的数字和，又不破坏第一个目标。在第二个目标实现之后，我们就可以实现最终目标：扇区内的数字和为12。同样我们希望在实现这个目标的时候，不破坏前两个目标。为此我们采用转动180o的方式实现。这样同

6、样是即可以保证前两个目标不被破坏，又可以实现第三个目标。　　经过这样的分析以后，我们发现该问题就清晰多了。当然，是否每一个第一、第二个目标的实现，都能够实现第三个目标呢？有可能不一定。在这种情况下，就需要在发现第三个目标不能实现时，重新试探其他的第一、第二个目标。　　　　传教士野人问题启发式搜索函数　　　　传教士野人问题，n个传教士和n个野人从河的一边摆渡到河的另一边，为安全起见，任何时候传教士的数目不能小于野人的数目，渡船每次渡k个人，N＝5，k≤3的M－C问题，找到相应的启发函数。定义h1=M+C-2B，其中M，C分别是在河的左岸的传教士人数和野人人数。B＝1表示

7、船在左岸，B＝0表示船在右岸。也可以定义h2=M+C，h1是满足A*条件的，而h2不满足。　　要说明h(n)＝M+C不满足A*条件是很容易的，只需要给出一个反例就可以了。比如状态(1,1,1)，h(n)=M+C=1+1=2，而实际上只要一次摆渡就可以达到目标状态，其最优路径的耗散值为1。所以不满足A*的条件。　　下面我们来证明h(n)＝M+C-2B是满足A*条件的。　　我们分两种情况考虑。先考虑船在左岸的情况。如果不考虑限制条件，也就是说，船一次可以将三人从左岸运到右岸，然后再有一个人将船送回来。这样，船一个来回可以运过河2人，而船仍然在左岸。而最后