毕业论文-水壶问题的仿真程序设计.doc

本科毕业设计(论文)题目：水壶问题的仿真程序设计院 (系)： 计算机科学与工程学院 专 业： 计算机科学与技术 学 生： 学 号： 指导教师： 2014年 06月 西安工业大学毕业设计（论文）任务书院（系）计算机科学与工程学院专业计算机科学与技术班090601姓名卢仓锋学号0906011101.毕业设计（论文）题目： 网上音像商城设计 2.题目背景和意义：网上音像商城设计旨在实现在网上提供选购音像产品，使音像产品购销更加便捷。 3.设计(论文)的主要内容（理工科含技术指标）：本课题要求学生通过复习相关课程内容；阅读有关资料，应用网络编程技术设计网上音像商城；总结毕业设计并写出论文；并通过外文资料翻译等环节的实践得到综合的工程训练。 网上音像商城分为五个大的模块： 1、商城人员管理； 2、客户管理； 3、音像产品推荐和管理； 4、信息查寻； 5、系统管理。 4.设计的基本要求及进度安排（含起始时间、设计地点）：毕业设计在大四第二学期1-18周于校内进行，其具体安排如下： 1.准备阶段（第一周-第二周）：了解课题，搜集相关资料，进行开题。 2.系统分析阶段（第三周-第四周）：确定总体设计方案，相关实现的算法设计。 3.模块编写阶段（第五周-第十周）：具体算法的实现。 4.总体实现及测试阶段（第十一周-第十四周）：完成相应的代码编写，实现所有的功能，进行总体测试，使之完全达到设计要求。 5.写毕业论文，准备毕业答辩（第十五周-第十八周）。 5.毕业设计（论文）的工作量要求 毕业论文不少于15000字 实验（时数）*或实习（天数）： 600机时 图纸（幅面和张数）*： 其他要求： 指导教师签名： 年 月 日学生签名： 年 月 日 系（教研室）主任审批： 年 月 日说明：1本表一式二份，一份由学生装订入附件册，一份教师自留。毕I-22 带*项可根据学科特点选填。水壶问题的仿真程序设计摘 要人工智能（Artificial Intelligence，AI）是当前科学技术发展的一门前沿学科，而搜索是人工智能研究的最基本问题，目前用于搜索的方法主要有盲目搜索和启发式搜索。盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题，且需要大量的时间空间作为基础。而启发式搜索则是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。而如何确定状态空间是解决搜索最重要的一个步骤,水壶问题就是搜搜问题中的一个典型例子，其求解过程就是一个状态空间的搜索过程，即由初始状态通过一条或几条路径，找到目标状态。关键字：水壶问题，人工智能，状态空间搜索，盲目搜索Simulation Program Design of the Pot ProblemAbstractAI (Artificial Intelligence, AI) is one of hottest subjects in the current research. In addition, search problem is the most basic problems in Artificial Intelligence research, including blind search and heuristic search. Blind search, known as without information search, generally applies to solve the simple problems, and needs a lot of time. Heuristic search is the method which explores all of space and then evaluates its result to get the best position. It can be achieved target base on this position. And how to determine the state space search is one of the most important step. Pot problem is a typical example of search problem, the solving process is a space search. Namely, from the initial state to the target state.Keywords: Pot Problem, Artificial Intelligence, State Space Research, blind searchII 西安工业大学学士学位论文 目 录摘 要IAbstractII1绪论11.1研究背景11.2论文研究内容11.3论文组织安排22 状态空间搜索策略32.1搜索的概念32.2状态及状态空间32.2.1状态的基本概念32.2.2 状态图示法42.2.3状态空间图的搜索策略42.2 盲目搜索52.2.1 宽度优先搜索策略52.2.2 深优先搜索策略62.3 启发式搜索72.3.1 启发式信息与估计函数72.3.2 局部最佳优先搜索82.3.3 全局最佳优先搜索92.3.4 A* 算法93 水壶问题的程序设计113.1定义状态空间113.2确定一组操作113.3 选择一种搜索策略133.4 水壶问题的搜索图133.5具体实现134 实验结果155 结论与展望195.1主要的研究成果195.2进一步的研究19致谢20参考文献21毕业设计（论文）知识产权声明22毕业设计（论文）独创性声明231绪论人工智能（Artificial Intelligence，AI）是当前科学技术发展的一门前沿学科，同时也是一门新思想，新观念，新理论，新技术不断出现的新兴学科以及正在发展的学科。而搜索是人工智能研究的最基本问题，目前用于搜索的方法主要有盲目搜索和启发式搜索。盲目搜索法不适宜决大而复杂的问题，因为要在盲目搜索中找到一个解，所需扩展的节点数目很大，并且当这些节点的扩展次序完全随意时，将耗费大量的计算时间和存储空间，搜索效率很低。启发式搜索法则是利用与问题有关的信息进行搜索，将知识或经验与搜索相结合从而达到减少搜索量，提高搜索效率的目的。1.1 研究背景人工智能是20世纪50年代中期兴起的一门新兴边缘科学，它既是计算机科学的一个分支，又是计算机科学、控制论、信息论、语言学、神经生理学、心理学、数学、哲学等多种学科相互渗透而发展起来的综合性学科。人工智能其研究目标就是制造智能机器和智能系统,实现智能化社会。具体来讲,就是要使计算机不仅具有脑智能和群智能,还要具有看、听、说、写等感知和交流能力1。简言之,就是要使计算机具有自主发现规律、解决问题和发明创造的能力,从而大大扩展和延伸人的智能,实现人类社会的全面智能化。人工智能学科的研究策略则是先部分地或某种程度地实现机器的智能，并运用智能技术解决各种实际问题特别是工程问题，从而使现有的计算机更灵活、更好用和更有用，成为人类的智能化信息处理工具，从而逐步扩展和不断延伸人的智能,逐步实现智能化。在这些年中人工智能与我们的生活息息相关，主要包括以下几个方面：1) 问题求解人工智能的第一大成就是下棋程序，在下棋程度中应用的某些技术，如向前看几步，把困难的问题分解成一些较容易的子问题，发展成为搜索和问题归纳这样的人工智能基本技术。今天的计算机程序已能够达到下各种方盘棋和国际象棋的锦标赛水平。但是，尚未解决包括人类棋手具有的但尚不能明确表达的能力，如国际象棋大师们洞察棋局的能力。另一个问题是涉及问题的原概念，在人工智能中叫问题表示的选择，人们常能找到某种思考问题的方法，从而使求解变易而解决该问题。到目前为止，人工智能程序已能知道如何考虑它们要解决的问题，即搜索解答空间，寻找较优解答。逻辑推理与定理证明。逻辑推理是人工智能研究中最持久的领域之一，其中特别重要的是要找到一些方法，只把注意力集中在一个大型的数据库中的有关事实上，留意可信的证明，并在出现新信息时适时修正这些证明。对数学中臆测的定理寻找一个证明或反证，不仅需要有根据假设进行演绎的能力，而且许多非形式的工作，包括医疗诊断和信息检索都可以和定理证明问题一样加以形式化，因此，在人工智能方法的研究中定理证明是一个极其重要的论题。2) 自然语言处理自然语言的处理是人工智能技术应用于实际领域的典型范例，经过多年艰苦努力，这一领域已获得了大量令人注目的成果。目前该领域的主要课题是：计算机系统如何以主题和对话情境为基础，注重大量的常识世界知识和期望作用，生成和理解自然语言。这是一个极其复杂的编码和解码问题。3) 智能信息检索技术。受网络技术迅猛发展的影响，信息获取和精化技术已成为当代计算机科学与技术研究中迫切需要研究的课题，将人工智能技术应用于这一领域的研究是人工智能走向广泛。4) 专家系统近年来，在“专家系统”或“知识工程”的研究中已出现了成功和有效应用人工智能技术的趋势。人类专家由于具有丰富的知识，所以才能达到优异的解决问题的能力。那么计算机程序如果能体现和应用这些知识，也应该能解决人类专家所解决的问题，而且能帮助人类专家发现推理过程中出现的差错，现在这一点已被证实。如在矿物勘测、化学分析、规划和医学诊断方面，专家系统已经达到了人类专家的水平。成功的例子如:1、Prospector系统发现了一个钼矿沉积，价值超过1亿美元。2、Dendrl系统的性能已超过一般专家的水平，可供数百人在化学结构分析方面的使用。3、MY CIN系统可以对血液传染病的诊断治疗方案提供咨询意见。经正式鉴定结果，对患有细菌血液病、脑膜炎方面的诊断和提供治疗方案已超过了这方面的专家。人工智能的研究目标是认识与模拟人类智能行为。传统的人工智能研究往往将研究重点集中于对人类单个智能品质如计算能力、推理能力、记忆能力等的研究与模拟。然而，由于人类智能行为是各种单个智能品质的综合体现，所以把人类看成有多种智能品质构成的有机整体智能体，综合考察智能体的各种智能行为与特征是当前最令人注目的研究方向。创造性地应用人工智能，是人类最大胆的设想之一。其最终的目标是创立不仅毫不逊色于自然人类的智能，而且就其潜在能力而言，更胜于它的人工智能。尽管从目前来看这一目标还相当遥远，到处存在疑点、争议，然而为了达到这一目标而开展的工作已在全速推进。那么由于脑力劳动的自动化程度不断提高，在生产领域是否不再需要人的参与了呢？对这个问题的回答包含着深刻的辩证法。随着人工智能的发展，人类在劳动手段和自然界各种力量面前，将获得迥然不同于过去的新自由，从而人类将开始摆脱因循呆板的思维劳动，而去从事真正具有创造性的工作。因循呆板和创造性间的界限不断推移，昨天被认为是创造性的，明天会被看成因循呆板的，而且可由人工智能来承担，而人类则腾出时间和精力去研究新的创造性课题，去从事水平更高的创造活动，这样人类就将永远是这一不断扩大领域的中心。思维信息加工理论认为人脑对信息处理的一个重要特点就是运用启发式，即人在进行认知活动时，常常利用一些生活中常用的启发式规则很简单地考虑几种可能性，而不是同时考虑解决问题的各种可能性，并对各种可能性进行权衡比较2。启发式是凭借经验的求解问题方法，不能保证问题一定得到解决，但却常常能有效地求解问题。启发式搜索法是人工智能解决问题的主要技术，而启发能力和搜索效率则是评价一个智能搜索系统的关键因素。在人工智能的搜索方法中, 启发式搜索是一类重要的搜索方法。它通过评估函数来计算代价, 以寻找最优的搜索方法。比如 A* 算法就是一种典型的启发式搜索算法, 被普遍应用于博弈、电脑游戏的AI设计等等。启发式算法在合理的评估函数下有着相当优秀的性能。但是, 启发式搜索需要设置精确的评估函数, 这在环境未知的复杂状态下是很难做到的。因此Crites等人提出了激励学习算法，通过奖赏函数, 让智能体在与环境的交互中自行判断动作的优劣, 它的优点在于无须事先知道环境模型, 适合于在线学习, 已证明在电梯调度、游戏、机器人导航等方面是一种有效的、实用的方法。但是，由于激励学习理论上需要通过遍历整个状态空间才能保证收敛于最优解。1.2论文研究内容给定两个水壶，一个可装4加仑的水，一个可装3加仑的水。水壶上没有任何的度量标记，有一个水泵可以用来往水壶里灌水，问题是怎样在4加仑的水壶里面恰好装入2加仑的水。本课题主要研究水壶问题中状态空间搜索的原理，并用Java程序设计语言设计仿真程序。具体研究内容如下：1) 初始状态的表示。2) 目标状态的表示。3) 动作集合的表示。4) 规划程序的设计。5) 求得的动作序列。6) 动作序列的动画演示。1.3论文组织安排论文各章节的安排如下：第一章:介绍了论文研究的背景和意义。第二章:首先通过对状态和状态空间的介绍，知道如何利用状态空间来解决现有问题。其次，介绍了目前常见的盲目搜索和启发式搜索算法。第三章:详细的论述了水壶问题的解决方案。第四章:给出了水壶问题在JAVA平台下的实验仿真结果。第五章：总结与展望。对本文工作进行了总结，针对在实验室中发现的不足之处给出了相应的分析与说明，并对下一步的研究工作进行了展望。192 状态空间搜索策略2.1搜索的概念现实世界中的大多数问题都是非结构化问题，一般不存在现成的求解方法来求解这样的问题，而只能利用已有的知识一步一步的摸索前进4。在这一个过程中，所要解决的问题是如何寻找可利用的知识、即如何确定推理路线，才能使在付出尽量少的代价的前提下把问题圆满的解决。如果存在多条路线可实现对问题的求解，那就又存在这样的问题，即如何从这多条路线中，选出一条使它求解代价最小，以提高求解程序的运行效率，像这样根据实际问题情况，按一定的策略或规则，从知识库中寻找可利用的知识，从而构造出一条使问题获得解决的推理路线的过程，称为搜索。搜索可以分为盲目搜索和启发式搜索5。盲目搜索又称为无信息搜索，即在搜索工程中，只按照预先规定的搜索控制策略进行搜索，而没有任何中间信息来改变这些控制策略6。由于这种搜索其控制策略都是预先规定的，不管什么问题都采用这样的控制策略即问题本身的特性对搜索控制策略没有任何影响，这就使得这样的搜索带有盲目性、效率不高。如果碰到复杂问题，其求解的效率可能相当低，所以盲目搜索只用于解决比较简单的问题。启发式搜索又称为有信息搜索，它是指在搜索过程中，根据问题本身的特性或搜索过程中产生的信息来不断改变或者调整搜索的方向，使搜索朝着最有希望的方向进行，加速问题的求解，并找到最优解。2.2状态及状态空间利用搜索来求解问题是在某个可能的解空间内寻找一个解，这就首先要有一种恰当的解空间的表示方法7。一般把这种可能解都表示为一个状态，然后以这些状态以及相应的算法为基础来表示和 求解问题。这种基于解答空间的问题表示和求解方法就是状态空间法。使用状态空间法，许多涉及智力的问题求解可看成在状态空间中的搜索。2.2.1状态的基本概念状态(state)是为描述某类不同事物间的差别而引入的一组最少变量的有序集合，其矢量形式如下: (2.1)式中每个元素为集合的分量，称为状态变量。给定每个分量的一组值就得到一个具体的状态，如 (2.2)算符是指使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。问题的状态空间(state space)是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。因此，可把状态空间记为三元状态(S，F，G)。状态空间的表示法对一个问题的状态描述，必须确定3件事：(1) 该状态描述方式，特别是初始状态描述；(2) 操作符集合及其对状态描述的作用；(3) 目标状态描述的特性。2.2.2 状态图示法图由节点(不一定是有限的节点)的集合构成。一对节点用弧线连接起来，从一个节点指向另一个节点。这种图叫做有向图(directed graph)。某个节点序列当j=2，3，k时，如果对于每一个都有一个后继节点存在，那么就把这个节点序列叫做从节点至节点的长度为k的路径。代价(cost) 是给各弧线指定数值以表示加在相应算符上的代价。图的显式说明 是指各节点及其具有代价的弧线由一张表明确给出。图的隐式说明 是指各节点及其具有代价的弧线不能由一张表明确给出。2.2.3状态空间图的搜索策略当把一个待求解的问题表示为状态空间以后，就可以通过对状态空间的搜索，实现对问题的求解。搜索法求解问题的基本思想是：首先讲问题的初始状态（即状态空间图中的初始节点）当作当前状态，选择适当的算符作用于当前状态，生成一组后继状态（或称为继节点），然后检查这组后继状态中是否有目标状态，如果有，则说明搜索成功，从初始状态到目标状态的一系列算符即是问题的解；若没有，则按照某种控制策略从已经生成的状态中再选择一个状态作为当前状态，重复上述过程，知道目标状态出现或者是不再有可供操作的状态及算符时为止8。对状态空间图中的某个节点，如果求出了他的后继节点，则此节点为已扩展的节点，而尚未求出他的后继节点的节点称之为扩展节点，将末扩展的节点存于一个名为OPEN的表中，而将已扩展的节点存于一个名为CLOSED的表中，他们的数据结构分别如表2.1和表2.2所示。编号状态节点父节点状态节点父节点5.1 OPEN表结构 表5.2 CLOSED 表节点状态空间图的搜索算法如下：1) 建立一个只含有初始节点S0的搜索图G，把S0放入OPEN表中；2) 建立CLOSED表，且置为空表；3) 判断OPEN表是否为空表，若为空，则问题无解，退出；4) 选择OPEN表中的第一个节点，把它从OPEN表移出，并放入CLOSED表中，将此节点记为节点n；5) 考察节点n是否为目标节点，若是，则问题有解，并成功退出。问题的解即可从图G中沿着指针从n到S0的这条路径得到；6) 扩展节点n生成一组不是n的祖先的后继节点，并将它们记作集合M，将M中的这些节点作为n的后继点加入图G中；7) 对那些未曾在G中出现过的（即未曾在OPEN表中或CLOSED表上出现过的）M中的节点，设置一个指向父节点（即节点n）的指针，并把这些节点加入OPEN表中；对于已在G中出现过的M中的那些节点，确定是否需要修改指向父节点（n节点）的指针；对于那些先前已经在G中出现并且已在CLOSED表中的那些M中的节点，确定是否需要修改通向他们的后继节点的指针；8) 按某一任意方式或某种策略重排OPEN表中节点的顺序；9) 转第（3）步。上述这一状态空间图的一般搜索算法具有通用性，但是针对第8）步对OPEN节点排序时所采用的方法不同又分为盲目搜索和启发式搜索。2.2 盲目搜索盲目搜索又称为无信息搜索，一般用于求解比较简单的问题。在本文主要介绍 种盲目搜索的方法。2.2.1 宽度优先搜索策略宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止9。广度优先搜索遍历类似于树的按层次遍历。其基本思想是：首先访问出发点Vi，接着依次访问Vi的所有未被访问过的邻接点Vi1,Vi2， ，Vit，并均标记为已访问过，然后再按照Vi1,Vi2， ，Vit的次序，访问每一个顶点的所有未曾访问过的顶点，并均标记为已访问过，以此类推，直到图中所有的初始出发点Vi1有路径相同的顶点都被访问过为止。在广度优先遍历中，先被访问的顶点，其邻接点也先被访问，即符合队列的性质：先进先出，所以在算法的实现过程中可是用一个队列，用来一次记住被访问过的顶点。算法开始时，将初始点Vi1访问后入队列，以后每从队列中删除一个元素，就一次访问它的每一个未曾访问过的邻接点，并将其入队列。当队列为空时，表明所有的与初始点有路径相通的顶点都已经访问完毕，算法到此为止。如果要在二维空间进行搜索，我们可以抽象成为以起点为根的一个连通图，这样就可以用图的广度优先搜索算法在空间进行搜索。以图2.1为例，我们假设节点E为起点，那么我们先将E点压入队列，同时将E节点标记，然后开始循环判断队列是否为空。不为空，我们就将第一个元素取出来，将与节点E所连接的所有节点放入队列。我们假设只有上、左、下、右四个方向，并且都是与E相邻的节点作为抽象后的节点。之后我们就会将节点B、D、H、F压入队列末尾中，同时将B、D、H、F节点标记，将E节点弹出队列。再继续判断队列是否为空。然后取出B节点，将节点A、C压入队列末尾，同时标记A、C节点已经遍历，再将B节点弹出。之后遍历D节点，将G节点压入队列末尾，同时标记G节点，弹出D节点。继续遍历H节点，将I节点压入队列末尾，同时标记I节点已经遍历，弹出H节点。之后依次遍历节点F、A、C、G、I，并将遍历过的节点弹出队列。当所有的节点都已经便利过，再循环知道队列为空，算法结束。ABCDEFGHI图2.1 广度优先搜索过程2.2.2 深优先搜索策略深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。深度优先搜索算法是把最近刚产生的节点优先扩展，直到达到一定深度限制。若未找到目标或无法再扩展时，在回溯到另一个结果的节点继续扩展。从初始状态S开始，利用规则生成搜索树下一层任意一个节点，检查是否出现目标状态G,若不是，继续以上操作过程，一直进行到叶节点（即不能再生成新状态节点）；当没有发现目标状态G时，回溯到上一层结果，去另一可能扩展搜索的分支，生成新状态节点；若仍然不是目标状态，就按该分支一直扩展到叶节点，若仍没有发现目标状态，采用相同的回溯办法回退到上层节点，扩展可能的分支生成新状态；如此一直进行行下去，直到找到目标状态G为止。搜索过程如图2.2所示，图中箭头上下的标号表示搜索的顺序，从图中可以看出，经过17步，从初始状态S搜索到了目标状态G。深度优先搜索算法描述为：首先定义数据结构OPEN栈和CLOSED表，其中：OPEN栈，先进后出，存放带扩展的节点；CLOSED表，存放已经被扩展过的节点。算法步骤如下：1) 把起始节点S先放到OPEN栈中；2) 如果OPEN栈为空时，则失败退出，否则继续；3) 从OPEN栈中去最前面的节点node移到CLOSED表中；4) 若node节点是叶子节点（若没有后继结点），则转向步骤2）；5) 扩展node的后继节点，产生全部后继结点，并把压入OPEN栈，各后继结点的指针指向node节点；6) 若后继结点中某一个目标节点，则找到一个解，成功推出否则转向2)循环。S11312HA21410119KIFB8317161554LJGDC76E 图2.2 深度优先搜索过程示意图2.3 启发式搜索盲目搜索所需要扩展的节点数目很大，产生的无用节点肯定非常的多，效率再燃比较低。如果能够找到一种搜索方法，能够充分利用待求解问题自身的某些特性信息，以直到搜索朝着最有利于问题求解方向发展，即再选择节点进行扩展时，选择那些最有希望的节点加以扩展，那么搜索的效率就会大大提高。这种利用问题自身特性的信息，以提高搜索效率的搜索策略，成为启发式搜索9。2.3.1 启发式信息与估计函数在搜索过程中，关键的一步是确定如何选择下一个要被考察的节点，不同的选择方法是不同的搜索策略。如果在确定被考察的节点时，能够利用被求解问题的有关特性信息，估计出各节点的重要性，那么再选择带扩展的节点时，就可以选择重要性较高的节点进行扩展，以提高求解的效率。像这样可用于指导搜索过程且与具体问题求解有关的控制信息称为启发式信息。启发式信息按其作用来分可以有三种：l 用于决定要扩展的下一个节点，以免像在宽度优先或深度优先中那样盲目地扩展。l 在扩展一个节点过程中，用于决定要生成哪一个或那几个后继结点，以免盲目地同时生成所有可能的节点。l 用于确定某些应该从搜索树中抛弃或修剪的节点。通过上述分析，可以定义决定哪个节点是下一步要扩展的节点称为“最有希望”的节点。通常可以构造一个估价函数来表示节点“希望”程度。如果估价函数f(x)，则f(x)可以是任意一种函数。如f(x)可以表示节点x处于最佳路径上的概率，也可以表示节点x到目标节点之间的距离。通常在确定估价函数时考虑两方面的因素：已经付出的代价和将要付出的代价。它的一般形式是：f(x)=g(x)+h(x) （2.3）其中g(x)为初始节点S0到节点x已实际付出的代价；h(x)是从节点x到目标节点Sg的最优路径的估计代价；搜索的启发信息主要由h(x)来体现，因此h(x)称为启发函数。估价函数f(x)考虑了从初始节点S0到目标节点Sg的代价，是一个估算值。他的作用是帮助确定OPEN表中各待扩展节点的“希望”程度，决定他们在OPEN表中的排列次序。一般地，在f(x)中，g(x)的比重越大，搜索方式就越倾向于广度优先搜索方式；h(x)的比重越大，越倾向于深度优先搜索方式。g(x)的作用代表了初始节点到目标节点的总代价估值中实际已付出的那部分，它体现了搜索的宽度优先趋势，有利于搜索算法的完备性，但影响算法的搜索效率。h(x)体现了搜索的深度优先趋势，当g(x) h(x)时，可以忽略g(x)，这会有利于搜索效率的提高，但影响搜索算法的完备性，即有可能找不到问题的解。在构造启发函数时，还要考虑两个方面的影响：1、搜索工作量；2、搜索代价。有些启发信息虽然能够大大减少搜素的工作量，但却不能保证求得最小代价路径。下面介绍两种启发式搜索策略。2.3.2 局部最佳优先搜索最佳优先搜索又称为有序搜索或择优搜索，它总是选择最有希望的节点作为下一个要扩展的节点，而这种最有希望的节点是按估价函数f(x)的值来挑选的，一般估价函数值越小，它的希望程度越大10。局部最佳优先搜索的思想类似于深度优先搜索法，但由于使用了与问题相关特性相关的估价函数来确定下一个扩展的节点，所以他是一种启发式搜索方法。其思想是：当对某一个节点进行扩展之后，对他的每一个后继结点计算估价函数f(x)的值，并在这些后继节点的范围内，选择一个f(x)的值最小的节点，作为下一个要考察的节点。由于他每次只在后继节点的范围内选择下一个要考察的节点，因此范围比较小，其算法如下：1) 把初始节点S0放入OPEN表，并计算估价函数f(S0)；2) 如果OPEN为空，则问题无解，退出；否则转3）；3) 从OPEN表中选取第一个节点（记节点n，其估价函数值最小）移入CLOSED表；4) 考察节点n是否为目标节点，若是，则求得问题的解，退出；否则转5）；5) 如果节点n可扩展，转6）；否则转2）；6) 对节点n进行扩展，并对它所有后继节点计算估价函数f(x)的值，并按估价函数f(x)从小到大的顺序依次放入OPEN表的前端；7) 为每个后继节点设置指向n的指针；8) 转第2）步。2.3.3 全局最佳优先搜索全局最佳优选搜索也是一个有信息的启发式搜索，其思想类似于宽度优先搜索，所不同的是，在确定下一个扩展节点时，以与问题特性密切相关的估价函数f(x)作为标准，不过这种方法是在OPEN表中的全部节点中选择一个估价函数值f(x)最小的节点，作为下一个被考察的节点11。其算法如下：1) 把初始节点S0放入OPEN表，并计算估价函数f(S0)；2) 如果OPEN为空，则问题无解，退出；3) 从OPEN表中选取第一个节点（记节点n，其估价函数值最小）移入CLOSED表；4) 考察节点n是否为目标节点，若是，则求得问题的解，退出；否则转5）；5) 如果节点n可扩展，转6）；否则转2）；6) 对节点n进行扩展，并对它所有后继节点计算估价函数f(x)的值，并为每个后继节点设置指向n的指针；7) 把这些后继节点都送入OPEN表，然后对OPEN表中的全部节点按照估价值从小到大的顺序排序；8) 转2）。 2.3.4 A* 算法A*算法是到目前为止最快的一种计算最短路径的算法，但它一种较优算法，即它一般只能找到较优解，而非最优解，但由于其高效性，使其在实时系统、人工智能等方面应用极其广泛12。A*算法结合了启发式方法（这种方法通过充分利用图给出的信息来动态地作出决定而使搜索次数大大降低）和形式化方法（这种方法不利用图给出的信息，而仅通过数学的形式分析，如Dijkstra算法）。它通过一个估价函数f(x)来估计图中的当前点p到终点的距离(带权值)，并由此决定它的搜索方向，当这条路径失败时，它会尝试其它路径。因而我们可以发现，A*算法成功与否的关键在于估价函数的正确选择，从理论上说，一个完全正确的估价函数是可以非常迅速地得到问题的正确解答，但一般完全正确的估价函数是得不到的，因而A*算法不能保证它每次都得到正确解答。一个不理想的估价函数可能会使它工作得很慢，甚至会给出错误的解答。它是在原有估价函数的基础上做了一些改变即：f *(x)=g*(x)+h*(x) （2.3）其中函数f *(x)表示从节点S0到节点x的一条最佳路径的实际代价加上从节点x到目标节点的一条最佳路径的代价和。g*(x)就是从节点S0到节点x之间最小的代价路径的实际代价，h*(x)则是从x节点到目标节点的最小代价路径上的代价。算法描述如下：1) OPEN：=(s)，f(s)：=g(s)+h(s)；2) LOOP： IF OPEN=THEN EXIT(FAIL)；3) n：=FIRST(OPEN)；4) IF GOAL(n) THEN EXIT(SUCCESS)；5) REMOVE(n, OPEN)， ADD(n, CLOSED)；6) EXPAND(n) mi，计算f(n, mi):=g(n, mi)+h(mi)；7) OPEN中的节点按f值从小到大排序；8) GO LOOP。为了提高解答的正确性，一般适当地降低估价函数的值，从而使之进行更多的搜索，但这是以降低它的速度为代价的，因而我们可以根据实际对解答的速度和正确性的要求而设计出不同的方案，使之更具弹性。因此他一般具有以下几种性质：1) 可采纳性可采纳性是指对于可求解的状态空间图（即从状态空间图的出世界店到目标节点有路径存在）来说，如果一个搜索算法能在有限步内终止，并且能够找到最优解，则称该算法是可采纳的。2) 单调性在A*算法中，如果对估价函数中的h(x)部分即启发函数，加以适当的单调性限制条件，就可以使他对所扩展的一些列节点的估价函数值单调递增（或飞递减），从而减少对OPEN表或者CLOSED表的检查和调整，提高搜索效率。对启发函数h(x)的单调性限制如下：a) 对所有的节点xi，如果xj是节点xi任意子节点，有h(xi)-h(xj) cost(xi, xj)。其中cost(xi, xj)是节点xi到节点xj的有向边代价。b) 设Sg是目标节点，他的启发函数的值为0，即h(Sg)=0。由此可以得到h(xi)cost(xi, xj)+ h(xj)这也就是说，节点xi到目标节点最有费用的估价不会超过从xi到其子节点xj的有向边代价上加上从xi到目标节点最优费用的估价。可以证明，当A*算法选择节点xn进行扩展时，g(xn)= g*(xn)。当A*算法的启发函数h(x)满足上述限制条件时，由A*算法所扩展的节点序列其估价函数f的值是非递减的。3) 信息性A*算法的搜索效率主要取决于启发函数h(x)，在满足h(x)h*(x)的前提下，h(x)的值越大越好。h(x)的值越大，表明他携带的与求解问题相关的信息越多，搜索过程就会在启发信息的指导下朝着目标节点前进，所走的弯路就会越少，搜索的效率就会提高。3 水壶问题的程序设计3.1定义状态空间给定两个水壶，一个可装4升水，一个能装3升水。水壶上没有任何度量标记。有一水泵可用来往壶中装水。对于该问题可将其进行抽象，用数偶(X,Y)表示状态空间的任一状态：X表示4升水壶中所装的水量，X=0，1，2，3或4；Y表示3升水壶中所装的水量，Y=0，1，2或3；初始状态为 (0,0)目标状态为 (2,?)? 表示水量不限，因为问题中未规定在3升水壶里装多少水。根据上述的表述，定义一个54的2维数组，把两个水壶的所有状态空间用图形的形式表示出来，按顺序存放于2维数组中。初始状态为(00.gif),目标状态为(2Y.gif)。Y可能是0、1、2、3。/定义状态空间Image img=new Image54;String str1=00.gif,01.gif,02.gif,03.gif, 10.gif,11.gif,12.gif,13.gif, 20.gif,21.gif,22.gif,23.gif, 30.gif,31.gif,32.gif,33.gif, 40.gif,41.gif,42.gif,43.gif；3.2确定一组操作a) (X,Y|X4)(4,Y)，4升水壶不满时，将其装满；b) (X,Y|Y3)(X，3)，3升水壶不满时，将其装满；c) (X,Y|X0)(X-D,Y)，把4升水壶中的水倒出部分水d) (X,Y|Y0)(X,Y-D) ，把3升水壶中的水倒出部分水；e) (X,Y|X0)(0，Y) ，把4升水壶中的水全部倒出；f) (X，Y|Y0)(X，0) ，把3升水壶中的水全部倒出；g) (X，Y|X+Y4Y0)(4，Y-(4-X)，把3升水壶中的水往4升水壶里倒，直至4升水壶装满为止；h) (X，Y|X+Y3X0)(X-(3-Y)，3)，把4升水壶中的水往3升水壶里倒，直至3升水壶装满为止；i) (X，Y|X+Y4Y0)(X+Y，0)，把3升水壶中的水全部倒进4升水壶里；j) (X，Y|X+Y3X0)(0，X+Y)，把4升水壶中的水全部倒进3升水壶里。用switch语句把8种操作表示出来。/定义操作 private void operate(int op) switch(op) case 1:X=4; break; case 2:Y=3; break; case 3:X=0; break; case 4:Y=0; break; case 5:int i; if(X+Y=4) i=4-X;X=4; Y=Y-i; else X=X+Y;Y=0; break; case 6:int j; if(X+Y=3) j=3-Y; Y=3; X=X-j; else Y=X+Y; X=0; break; case 7: X=X+Y; Y=0; break; case 8:Y=Y+X; X=0; break; default 3.3 选择一种搜索策略为了求解水壶问题，除了上面给出的问题描述和算子外，还应该选择一种策略控制搜索。策略为一个简单的循环控制结构：选择其左部匹配当前状态的某条规则，并按照该规则右部的描述对此状态做适当改变，然后检查改变后的状态是否为某一状态，若不是，则继续循环。这样搜索下去，直到出现(2，?)状态为止，从(0，0)到(2，?)的路径上所用的操作序列就是所求的解。3.4 水壶问题的搜索图目标状态的搜索过程有很多种情况，有的能找到目标状态，有的不行，而在整个设计过程中，只求解出能搜索出目标状态的情况，为了能让读者更清楚的看到水壶求解目标状态的搜索过程，在这里例举两种找到目标状态情况的示意图，如图3.1所示12。图3.1 水壶问题搜索图3.5具体实现解决的基本思路是利用有限状态机M，设X为4加仑水壶的水量，Y是3加仑水壶的水量。则所有可能的(X，Y)序对作为M的状态集，操作1, 2，3, 4，5, 6，7, 8 是输入字符集开始状态是(0,0)，终止状态是(2，Y)，Y可能是0,1，2,3。当一个输入串是M的语言时，这个串就是水壶问题的一个可能方案。动画的实现是先把4加仑水壶和3加仑水壶的所有状态用图片的形式表示出来，用一个二维数组存放，把两个水壶的状态图片跟它们在数组中的位置对应起来13。例如，4加仑水壶的状态此时是4，3加仑水壶的状态此时是2，它们此时的状态是(4，2)，则在存放图片的二维数组中42就存放这张状态图片。动画演示过程就是根据从初始状态到目标状态的2个水壶的状态，对应图片数组中的图片，将它们一一显示出来，这样就达到了动画演示的效果。如表3.1所示搜寻路径。4升水壶中含水升数3升水壶中含水升数所应用的规则00-032309332427025209表3.1搜寻路 西安工业大学学士学位论文 4 实验结果在JAVA环境下运行上述算法后，得到水壶问题的求解过程。动画的演示跟控制台同步，即控制台每显示一步，动画图片就跟着演示一步。动画演示如下图所示：1) 初始状态时，4加仑跟3加仑的水壶都是空的。如图3.1所示： 图3.1 初始图片2) 根据所定义的操作开始查找目标状态，先执行第一个操作，在4加仑