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

1/7浅析计算机人工智能启发式搜索函数浅析计算机人工智能启发式搜索函数摘要阐述了人工智能的核心问题及启发式搜索函数的基本概念，介绍了4种经典问题启发式搜索函数的选择及其研究中遇到的难题，并从中求解来探讨解决问题的思路。关键词人工智能；问题求解；启发式搜索函数中图分类号TP18文献标识码A文章编号10093044XX0810PPP0C人工智能问题广义地说，都可以看作是一个问题求解过程，因此问题求解是人工智能的核心问题，它通常是通过在某个可能的解答空间中寻找一个解来进行的。在问题求解过程中，人们所面临的大多数现实问题往往没有确定性的算法，通常需要用搜索算法来解决。目标和达到目标的一组方法称为问题，搜索就是研究这些方法能够做什么的过程。问题求解一般需要考虑两个基本问题首先是使用合适的状态空间表示问题，其次是测试该状态空间中目标状态是否出现。1什么是启发式搜索函数2/7在人工智能中有很大一类问题的求解技术依赖于搜索。启发式方法就是采用有利于问题自身特征信息来引导搜索过程的方法，在学生学习过程中启发式函数的选取至关重要，决定整个算法的效率与成败。启发式搜索通常用于两种不同类型的问题前向推力和反向推理。前向推理一般用于状态空间的搜索。在前向推理中，推理是从预定义的初始状态出发向目标状态反向方向执行；反向推理一般用于问题归约中。在反向推理中，推理是从给定的目标状态向初始状态执行。用来评估节点重要性的函数称为评估函数。评估函数FX定义为从初始节点S0出发，约束地经过节点X到达目标节点SG的所有路径中最小路径代价的估计值。其一般形式为其中，GX表示从初始节点S0到节点X的实际代价；HX表示从X到目标节点SG的最优路径的评估代价，它体现了问题的启发式信息，其形式要根据问题的特征确定，HX称为启发式函数。因此，启发式方法把问题状态的描述转换成了对问题解决程度的描述，这一程度用评估函数的值来表示。3/7滑动积木游戏启发式搜索函数滑动积木块游戏的棋盘结构及某一种将牌的初始排列结构如下其中B表示黑色将牌，W表示白色将牌，E表示空格。游戏的规定走法是任意一个将牌可以移入相邻的空格，规定其耗散值为1；任意一个将牌可相隔1个或2个其他的将牌跳入空格，规定其耗散值等于跳过将牌的数目；游戏要达到的目标是使所有白将牌都处在黑将牌的左边。对这个问题，定义一个启发函数HN，并给出利用这个启发函数用算法A求解时所产生的搜索树。可定义H为HB右边的W的数目很多知识对求解问题有好处，这些知识并不一定要写成启发函数的形式，很多情况下，也不一定能清晰的写成一个函数的形式。由题意，在目标状态下，一个扇区的数字之和等于12，一个相对扇区的数字之和等于24，而一个阴影扇区或者非阴影扇区的数字之和为48。为此，我们可以将目标进行分解，首先满足阴影扇4/7区的数字之和为48。为了这个目标我们可以通过每次转动圆盘45O实现。在第一个目标被满足的情况下，我们再考虑第二个目标每一个相对扇区的数字和为24。在实现这个目标的过程中，我们希望不破坏第一个目标。为此我们采用转动90O的方式实现，这样即可以调整相对扇区的数字和，又不破坏第一个目标。在第二个目标实现之后，我们就可以实现最终目标扇区内的数字和为12。同样我们希望在实现这个目标的时候，不破坏前两个目标。为此我们采用转动180O的方式实现。这样同样是即可以保证前两个目标不被破坏，又可以实现第三个目标。经过这样的分析以后，我们发现该问题就清晰多了。当然，是否每一个第一、第二个目标的实现，都能够实现第三个目标呢有可能不一定。在这种情况下，就需要在发现第三个目标不能实现时，重新试探其他的第一、第二个目标。传教士野人问题启发式搜索函数传教士野人问题，N个传教士和N个野人从河的一边摆渡到河的另一边，为安全起见，任何时候传教士的数目不能小于野人的数目，渡船每次渡K个人，N5，K3的MC问题，找到相应的启发函数。定义H1MC2B，其5/7中M，C分别是在河的左岸的传教士人数和野人人数。B1表示船在左岸，B0表示船在右岸。也可以定义H2MC，H1是满足A条件的，而H2不满足。要说明HNMC不满足A条件是很容易的，只需要给出一个反例就可以了。比如状态1,1,1，HNMC112，而实际上只要一次摆渡就可以达到目标状态，其最优路径的耗散值为1。所以不满足A的条件。下面我们来证明HNMC2B是满足A条件的。我们分两种情况考虑。先考虑船在左岸的情况。如果不考虑限制条件，也就是说，船一次可以将三人从左岸运到右岸，然后再有一个人将船送回来。这样，船一个来回可以运过河2人，而船仍然在左岸。而最后剩下的三个人，则可以一次将他们全部从左岸运到右岸。所以，在不考虑限制条件的情况下，也至少需要摆渡次。其中分子上的“3“表示剩下三个留待最后一次运过去。除以“2“是因为一个来回可以运过去2人，需要个来回，而“来回“数不能是小数，需要向上取整，这个用符号表示。而乘以“2“是因为一个来回相当于两次摆论文联盟渡，所以要乘以2。而最后的“1“，则表示将剩下的3个运过去，需要一次摆渡。再考虑船在右岸的情况。同样不考虑限制条件。船6/7在右岸，需要一个人将船运到左岸。因此对于状态M，C，0来说，其所需要的最少摆渡数，相当于船在左岸时状态M1，C，1或M，C1，1所需要的最少摆渡数，再加上第一次将船从右岸送到左岸的一次摆渡数。因此所需要的最少摆渡数为MC121。其中MC1的“1“表示送船回到左岸的那个人，而最后边的“1“，表示送船到左岸时的一次摆渡。综合船在左岸和船在右岸两种情况下，所需要的最少摆渡次数用一个式子表示为MC2B。其中B1表示船在左岸，B0表示船在右岸。由于该摆渡次数是在不考虑限制条件下，推出的最少所需要的摆渡次数。因此，当有限制条件时，最优的摆渡次数只能大于等于该摆渡次数。所以该启发函数H是满足A条件的。结束语总之，计算机人工智能启发式搜索函数选取的方法比较多，试图找出问题中选取函数的相似的方法，从文中可知还没有那一个函数可以处于绝对的地位，可以适用于所有环境。如何将各种选取启发式搜索函数的思路结合起来，寻找各个问题选取函数的特点规律，在这个方面还是7/7有很多的理论和实践值得深入研究。参考文献1史忠植高级人工智能M科学出版社,XX2廉师友