人工智能搜索技术论文

　　人工智能的核心问题及启发式搜索函数的基本概念，介绍了4种经典问题启发式搜索函数的选择及其研究中遇到的难题，并从中求解来探讨解决问题的思路。以下是学习啦小编整理的人工智能搜索技术论文的相关资料，欢迎阅读!

　　人工智能搜索技术论文篇一

　　摘要：阐述了人工智能的核心问题及启发式搜索函数的基本概念，介绍了4种经典问题启发式搜索函数的选择及其研究中遇到的难题，并从中求解来探讨解决问题的思路。

　　关键词：人工智能;问题求解;启发式搜索函数

　　中图分类号：TP18文献标识码：A文章编号：1009-3044(2008)08-10ppp-0c

　　人工智能问题广义地说，都可以看作是一个问题求解过程，因此问题求解是人工智能的核心问题，它通常是通过在某个可能的解答空间中寻找一个解来进行的。在问题求解过程中，人们所面临的大多数现实问题往往没有确定性的算法，通常需要用搜索算法来解决。目标和达到目标的一组方法称为问题，搜索就是研究这些方法能够做什么的过程。问题求解一般需要考虑两个基本问题：首先是使用合适的状态空间表示问题，其次是测试该状态空间中目标状态是否出现。

　　1 什么是启发式搜索函数

　　在人工智能中有很大一类问题的求解技术依赖于搜索。启发式方法就是采用有利于问题自身特征信息来引导搜索过程的方法，在学生学习过程中启发式函数的选取至关重要，决定整个算法的效率与成败。启发式搜索通常用于两种不同类型的问题：(1)前向推力和(2)反向推理。前向推理一般用于状态空间的搜索。在前向推理中，推理是从预定义的初始状态出发向目标状态反向方向执行;反向推理一般用于问题归约中。在反向推理中，推理是从给定的目标状态向初始状态执行。

　　用来评估节点重要性的函数称为评估函数。评估函数f(x)定义为从初始节点S0出发，约束地经过节点x到达目标节点Sg的所有路径中最小路径代价的估计值。其一般形式为：

　　其中，g(x)表示从初始节点S0到节点x的实际代价;h(x)表示从x到目标节点Sg的最优路径的评估代价，它体现了问题的启发式信息，其形式要根据问题的特征确定，h(x)称为启发式函数。因此，启发式方法把问题状态的描述转换成了对问题解决程度的描述，这一程度用评估函数的值来表示。

　　2 滑动积木游戏启发式搜索函数

　　滑动积木块游戏的棋盘结构及某一种将牌的初始排列结构如下：

　　其中B表示黑色将牌，W表示白色将牌，E表示空格。游戏的规定走法是：

　　(1)任意一个将牌可以移入相邻的空格，规定其耗散值为1;

　　(2)任意一个将牌可相隔1个或2个其他的将牌跳入空格，规定其耗散值等于跳过将牌的数目;游戏要达到的目标是使所有白将牌都处在黑将牌的左边(左边有无空格均可)。对这个问题，定义一个启发函数h(n)，并给出利用这个启发函数用算法A求解时所产生的搜索树。可定义h为：h=B右边的W的数目

　　很多知识对求解问题有好处，这些知识并不一定要写成启发函数的形式，很多情况下，也不一定能清晰的写成一个函数的形式。由题意，在目标状态下，一个扇区的数字之和等于12，一个相对扇区的数字之和等于24，而一个阴影扇区或者非阴影扇区的数字之和为48。

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

　　经过这样的分析以后，我们发现该问题就清晰多了。当然，是否每一个第一、第二个目标的实现，都能够实现第三个目标呢?有可能不一定。在这种情况下，就需要在发现第三个目标不能实现时，重新试探其他的第一、第二个目标。

　　4 传教士野人问题启发式搜索函数

　　传教士野人问题，n个传教士和n个野人从河的一边摆渡到河的另一边，为安全起见，任何时候传教士的数目不能小于野人的数目，渡船每次渡k个人， N=5，k≤3的M-C问题，找到相应的启发函数。定义h1=M+C-2B，其中M，C分别是在河的左岸的传教士人数和野人人数。B=1表示船在左岸，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人，而船仍然在左岸。而最后剩下的三个人，则可以一次将他们全部从左岸运到右岸。所以，在不考虑限制条件的情况下，也至少需要摆渡whx04.tif次。其中分子上的"-3"表示剩下三个留待最后一次运过去。除以"2"是因为一个来回可以运过去2人，需要whx05.tif个来回，而"来回"数不能是小数，需要向上取整，这个用符号whx06.tif表示。而乘以"2"是因为一个来回相当于两次摆

　　渡，所以要乘以2。而最后的"+1"，则表示将剩下的3个运过去，需要一次摆渡。

　　再考虑船在右岸的情况。同样不考虑限制条件。船在右岸，需要一个人将船运到左岸。因此对于状态(M，C，0)来说，其所需要的最少摆渡数，相当于船在左岸时状态(M+1，C，1)或(M，C+1，1)所需要的最少摆渡数，再加上第一次将船从右岸送到左岸的一次摆渡数。因此所需要的最少摆渡数为：(M+C+1)-2+1 。其中(M+C+1)的"+1"表示送船回到左岸的那个人，而最后边的"+1"，表示送船到左岸时的一次摆渡。

　　综合船在左岸和船在右岸两种情况下，所需要的最少摆渡次数用一个式子表示为：M+C-2B。其中B=1表示船在左岸，B=0表示船在右岸。 由于该摆渡次数是在不考虑限制条件下，推出的最少所需要的摆渡次数。因此，当有限制条件时，最优的摆渡次数只能大于等于该摆渡次数。所以该启发函数h是满足A*条件的。

　　5 结束语

　　总之，计算机人工智能启发式搜索函数选取的方法比较多，试图找出问题中选取函数的相似的方法，从文中可知还没有那一个函数可以处于绝对的地位，可以适用于所有环境。如何将各种选取启发式搜索函数的思路结合起来，寻找各个问题选取函数的特点规律，在这个方面还是有很多的理论和实践值得深入研究。

下一页分享更优秀的<<<人工智能搜索技术论文