人工智能启发式图搜索算法

启发式搜索——初识A*算法A*在游戏中有它很典型的用法，是人工智能在游戏中的代表。

A*算法在人工智能中是一种典型的启发式搜索算法，为了说清楚A*算法，先说说何谓启发式算法。

一、何谓启发式搜索算法在说它之前先提提状态空间搜索。

状态空间搜索，如果按专业点的说法，就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。

通俗点说，就是在解一个问题时，找到一个解题的过程，应用这个过程可以从求解的开始得到问题的结果。

由于求解问题的过程中分支有很多，主要是求解过程中求解条件的不确定性、不完备性造成的，使得求解的路径很多，这样就构成了一个图，我们说这个图就是状态空间。

问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。

这个寻找的过程就是状态空间搜索。

常用的状态空间搜索有深度优先和广度优先。

广度优先是从初始状态一层一层向下找，直到找到目标为止。

深度优先是按照一定的顺序，先查找完一个分支，再查找另一个分支，直至找到目标为止。

这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。

前面说的广度和深度优先搜索有一个很大的缺陷就是：他们都是在一个给定的状态空间中穷举。

这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不可预测的情况下就不可取了。

他们的效率实在太低，甚至不可完成。

在这里就要用到启发式搜索了。

启发式搜索就是在状态空间中搜索时，对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直至找到目标。

这样可以省略大量无谓的搜索路径，提高了效率。

在启发式搜索中，对位置的估价是十分重要的。

采用了不同的估价可以有不同的效果。

我们先看看估价是如何表示的。

启发中的估价是用估价函数表示的，如：f(n)=g(n)+h(n)其中f(n)是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n节点到目标节点最佳路径的估计代价。

在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。

启发式搜索算法在路径规划中的应用在现代高科技社会中，路径规划已经成为了人们生活和工作中必不可少的一部分。

比如，在物流、交通管理、游戏等领域中，都需要通过路径规划算法来找到最佳路径。

而启发式搜索算法就是应用在路径规划中的一种算法。

本文将重点介绍启发式搜索算法在路径规划中的应用。

一、路径规划概述路径规划是从起点到终点寻找最短路径的过程，是一种基本的算法问题。

在路径规划中，通常会有一些障碍物，需要绕过去。

而起点和终点之间的最短路径通常是经过这些障碍物，并绕过它们的路径。

二、启发式搜索算法概述启发式搜索算法是一种智能搜索算法，也称为A*算法。

该算法基于Dijkstra算法，对其进行了改进，使其更加有效率。

它通过估算从当前位置到目标位置的代价来选择下一个探索位置。

启发式搜索算法是一种通过权衡搜索的广度和深度进行计算路径的算法。

三、启发式搜索算法原理启发式搜索算法采用了双向搜索的策略，即从起点开始，同时向前和向后进行搜索。

通过计算当前节点到目标节点的估价函数，可以以最优的方式选择下一个节点进行扩展。

估价函数通常基于多种因素，比如当前节点到目标节点的欧几里得距离、曼哈顿距离或者其他方法。

通过比较估价函数的结果，可以得到到目标节点的最优路径。

四、启发式搜索算法应用1.物流路径规划在物流领域中，路径规划非常重要。

启发式搜索算法可以用来规划货物的最短路径。

通过考虑货物的大小、重量和目标位置等因素，可以选择最佳路径来实现交付。

2.游戏实现启发式搜索算法还可以用于游戏实现中的路径规划问题。

例如，在迷宫游戏中，启发式搜索算法可以用来寻找通向出口的最短路径。

在实现游戏中，启发式搜索算法可以提高游戏的逼真性，并提高游戏的娱乐性。

3.交通管理启发式搜索算法还可以用于交通管理领域中。

例如，在城市中，交通流量非常大，交通瓶颈点即使绕路也会遇到拥堵。

通过启发式搜索算法的路径规划方法，可以规划出最优的通行路线，并避开拥堵的瓶颈点。

1．启发式搜索算法A启发式搜索算法A，一般简称为A算法，是一种典型的启发式搜索算法。

其基本思想是：定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。

评价函数的形式如下：f（n）＝g（n）＋h（n）其中n是被评价的节点。

f（n）、g（n）和h（n）各自表述什么含义呢？我们先来定义下面几个函数的含义，它们与f（n）、g（n）和h（n）的差别是都带有一个"*"号。

g*(n)：表示从初始节点s到节点n的最短路径的耗散值；h*(n)：表示从节点n到目标节点g的最短路径的耗散值；f*(n)=g*(n)+h*(n)：表示从初始节点s经过节点n到目标节点g的最短路径的耗散值。

而f（n）、g（n）和h（n）则分别表示是对f*（n）、g*（n）和h*（n）三个函数值的的估计值。

是一种预测。

A算法就是利用这种预测，来达到有效搜索的目的的。

它每次按照f(n)值的大小对OPEN表中的元素进行排序，f值小的节点放在前面，而f值大的节点则被放在OPEN表的后面，这样每次扩展节点时，都是选择当前f值最小的节点来优先扩展。

利用评价函数f（n）＝g（n）＋h（n）来排列OPEN表节点顺序的图搜索算法称为算法A。

过程A①OPEN:＝（s），f（s）:＝g（s）+h（s）;②LOOP：IFOPEN＝（）THENEXIT（FAIL）；③n:＝FIRST（OPEN）；④IFGOAL（n）THENEXIT（SUCCESS）；⑤REMOVE（n，OPEN），ADD（n，CLOSED）；⑥EXPAND（n）→{mi}，计算f（n，mi）＝g（n，mi）+h（mi）；g（n，mi）是从s通过n到mi的耗散值，f（n，mi）是从s通过n、mi到目标节点耗散值的估计。

《人工智能》实验大作业实验题目：启发式搜索一、实验目的：熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A算法求解九宫问题，理解求解流程和搜索顺序。

二、实验方法：1.先熟悉启发式搜索算法；2.用C、C++或JAVA语言编程实现实验内容。

三、实验背景知识：1.估价函数在对问题的状态空间进行搜索时，为提高搜索效率需要和被解问题的解有关的大量控制性知识作为搜索的辅助性策略。

这些控制信息反映在估价函数中。

估价函数的任务就是估计待搜索节点的重要程度，给这些节点排定次序。

估价函数可以是任意一种函数，如有的定义它是节点x处于最佳路径的概率上，或是x节点和目标节点之间的距离等等。

在此，我们把估价函数f(n)定义为从初始节点经过n节点到达目标节点的最小代价路径的代价估计值，它的一般形式是：f(n)=g(n)+h(n)其中g(n)是从初始节点到节点n的实际代价，g(n)可以根据生成的搜索树实际计算出来；h(n)是从n到目标节点的最佳路径的代价估计，h(n)主要体现了搜索的启发信息。

2.启发式搜索过程的特性（1）可采纳性当一个搜索算法在最短路径存在的时候能保证能找到它，我们就称该算法是可采纳的。

所有A*算法都是可采纳的。

（2）单调性一个启发函数h是单调的，如果a）对所有的状态ni和nj，其中nj是ni的子孙，h(ni)-h(nj)≤cost(ni,nj),其中cost(ni,nj)是从ni到nj实际代价。

b）目标状态的启发函数值为0，即h(Goal)=0.具有单调性的启发式搜索算法在对状态进行扩展时能保证所有被扩展的状态的f值是单调递增（不减）。

（3）信息性比较两个启发策略h1和h2，如果对搜索空间中的任何一个状态n都有h1(n)≤h2(n)，就说h2比h1具有更多的信息性。

一般而言，若搜索策略h2比h1有更多的信息性，则h2比h1考察的状态要少。

人工智能基础实验报告实验名称：八数码问题姓名：张俊学号：2220092333指导老师：邓安生启发式搜索算法1.实验内容：使用启发式搜索算法求解8数码问题。

⑴编制程序实现求解8数码问题A*算法，采用估价函数()()()()wnfndnpn=+，其中：()dn是搜索树中结点n的深度；()wn为结点n的数据库中错放的棋子个数；()pn为结点n的数据库中每个棋子与其目标位置之间的距离总和。

⑵分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是()pn的上界的()hn的定义，并测试使用该估价函数是否使算法失去可采纳性。

2.实验目的熟练掌握启发式搜索A*算法及其可采纳性。

3.实验原理八数码问题是在3行和3列构成的九宫棋盘上放置数码为1到8的8个棋盘，剩下一个空格的移动来不断改变棋盘的布局，求解这类问题的方法是：给定初始布局（即初始状态）和目标布局（即目标状态），定义操作算子的直观方法是为每个棋牌制定一套可能的走步》上，下，左，右四种移动，再根据所定义的启发式搜索函数在搜索过程中选择最合适的操作算子，得到最优的路径。

实验四A*算法求解8数码问题一、实验目的熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解8数码难题，理解求解流程和搜索顺序。

二、实验原理A*算法是一种启发式图搜索算法，其特点在于对估价函数的定义上。

对于一般的启发式图搜索，总是选择估价函数f值最小的节点作为扩展节点。

因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的实际代价g(n)以及从节点n到达目标节点的估价代价h(n)，且h(n)<=h*(n)，h*(n)为n节点到目标节点的最优路径的代价。

棋盘中有一个空格，允许紧邻空格的某一将牌可以移到空格中，这样通过平移将牌可以将某一将牌布局变换为另一布局。

针对给定的一种初始布局或结构（目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。

如图1所示表示了一个具体的八数码问题求解。

图1八数码问题的求解三、实验内容1、参考A*算法核心代码，以8数码问题为例实现A*算法的求解程序（编程语言不限），要求设计两种不同的估价函数。

2、在求解8数码问题的A*算法程序中，设置相同的初始状态和目标状态，针对不同的估价函数，求得问题的解，并比较它们对搜索算法性能的影响，包括扩展节点数、生成节点数等。

3、对于8数码问题，设置与图1所示相同的初始状态和目标状态，用宽度优先搜索算法（即令估计代价h(n)＝0的A*算法）求得问题的解，记录搜索过程中的扩展节点数、生成节点数。

4、提交实验报告和源程序。

人工智能-----启发式搜索一．问题背景人工智能的宗旨是寻找一种有效的方式把智能的问题求解、规划和通信技巧应用到更广泛的实际问题中，集中于不存在算法解的问题，这也是为什么启发式搜索是一种主要的AI问题求解技术的原因。

对于人工智能系统而言，问题可能状态的数量随搜索的深入呈现指数或阶乘增长，为了明智地找出正解，将沿最有希望的路径穿越空间来降低这种复杂性，这便是启发式求解。

把没有希望的状态及这些状态的后代排除，这样便可以克服组合爆炸，找到可接受的解。

二．基本简介启发式求解对问题求解过程中下一步要采取的措施的一种精明猜测，是建立于强大的知识库的由经验总结出的求解方式。

简单的启发可以排除搜索空间的绝大部分。

启发式搜索由两部分组成：启发度量及是有这个度量进行空间搜索的算法。

下面介绍两种算法1.爬山法爬山策略在搜索中现扩展当前状态，然后再评估它的“孩子”。

而后选择“最佳的”孩子做进一步扩展；而且过程中既不保留它的兄弟姐妹，也不保留它的双亲。

因为这种策略不保存任何历史记录，所以它不具有从失败中恢复的能力。

图1使用3层预判的爬山方法遇到的局部最大化问题爬山策略的一个主要问题是容易陷入局部最大值。

如果这种策略达到了一个比其他任何孩子都好的状态，它便停止。

因此为了提高性能，需要局部改进评估多项式。

2.最佳优先搜索算法最佳优先搜索算法使用了优先级队列，使得从诸如陷入局部优先等情况中恢复成为可能，从而使启发式搜索更加灵活。

最佳优先搜索算法使用列表来维护状态：用open列表来记录搜索的当前状态，用close列表记录已经访问过的状态。

在这种算法中新加的一步是对open中的状态进行排序，排序的依据是对状态与目标“接近程度”的某种启发性估计。

最佳优先搜索算法总是选择最有希望的状态做进一步扩展。

然而由于他正在使用的启发可能被证明是错误的，所以它并不抛弃所有状态而是把他们维护在open中。

一旦发现启发将搜索引导到一条证明不正确的路径，那么算法会从open中取出一些以前产生的“次优先”的状态，从而把搜索的焦点转移到空间的另一部分。

启发式算法在人工智能问题中的应用随着人工智能（ArtificialIntelligence，简称AI）的快速发展和应用，启发式算法作为一种重要的搜索和优化技术，在解决人工智能问题中发挥了重要作用。

启发式算法通过模拟人类的启发式思考方式，能够在大规模搜索空间中高效地找到较优解。

本文将探讨启发式算法在人工智能问题中的应用，并介绍几种常见的启发式算法。

一、启发式算法在机器学习中的应用启发式算法在机器学习中有广泛的应用，其中最为常见的是遗传算法和蚁群算法。

遗传算法通过模拟生物进化过程中的基因传递和自然选择，来不断优化模型参数以达到最优解。

蚁群算法则是基于模拟蚂蚁觅食行为的启发式算法，通过模拟蚂蚁的信息素释放和信息素跟随来搜索最优路径或寻找最佳解决方案。

在深度学习中，由于其复杂的网络结构和大量的参数，优化问题变得非常困难。

启发式算法的引入可以有效地解决这一问题。

例如，深度神经网络的训练过程可以借鉴遗传算法中的交叉、变异等操作来进行参数优化，从而提高模型的性能和泛化能力。

此外，蚁群算法也可以应用于深度学习中的参数搜索和模型选择，通过模拟蚂蚁的信息传递和协作行为，能够找到更加全局最优的解。

二、启发式算法在图像处理中的应用图像处理是人工智能领域的一个重要应用方向，而启发式算法在图像处理中有着广泛的应用。

例如，模拟退火算法是一种基于统计物理学思想的全局优化算法，可以应用于图像分割、图像增强等问题中。

该算法通过随机扰动和接受概率来搜索全局最优解，能够在处理复杂的图像结构时获得较好的结果。

此外，蚁群算法在图像分析和图像识别中也具有一定的应用。

例如，在图像分割中，可以通过模拟蚂蚁的觅食行为，将图像划分为不同的区域；在图像识别中，可以通过模拟蚂蚁的信息素释放和信息素跟随来进行目标检测和图像分类。

这些启发式算法的应用能够在图像处理中实现更精确、更快速的结果。

实验报告姓名：***学号：**********班级：软件二班实验名称：启发式搜索课程名称：人工智能实验日期：2015.11.09实验环境：VisualC++实验目的以及内容：1、实验内容：使用启发式搜索算法求解八数码问题。

（1）编制程序实现求解八数码问题A*算法，采用估价函数其中：d(n)是搜索树中节点n的深度；w(n)为节点n的数据库中错放的棋子个数；p(n)为节点n的数据库中的每个棋子与其目标位置之间的距离的总和。

（2）分析上述（1）中的两种估价函数求解八数码问题的效率差别，给出一个是p(n)的上界的h(n)的定义，并测试使用该估价函数是否使算法失去可采纳性。

2、实验目的：熟练的掌握启发式搜索A*算法及其可采纳性。

3.实验原理：八数码问题是在3行和3列构成的九宫棋盘上放置数码为1到8的8个棋盘，剩下一个空格的移动来不断改变棋盘的布局，求解这类问题的方法是：给定初始布局（即初始状态）和目标布局（即目标状态），定义操作算子的直观方法是为每个棋牌制定一套可能的走步》上，下，左，右四种移动，再根据所定义的启发式搜索函数在搜索过程中选择最合适的操作算子，得到最优的路径。

启发式搜索算法一、定义启发式，又称为有启发性，是一种智能算法，它通过有效地给定的空间来求解其中一特定问题，从而找到一个最优解。

启发式算法是以概率机器学习的概念为基础，通过利用已有知识结合启发式函数来实现有效的。

二、分类启发式可以分为两类：有限空间和无限空间。

有限空间算法包括深度优先（DFS）、广度优先（BFS）等，这些算法通过有限次数的步骤状态空间，来尝试找出最佳解决方案。

而无限空间算法则是基于空间的随机加载，并根据不断变化的环境状况，来更新策略，以达到更优的最终解决方案。

三、基本原理启发式算法的主要思想是在不知道结果的情况下，通过评估当前状态来估计未来状态的最优解。

因此，启发式算法需要引入一种启发式函数，即评价函数，来评估当前状态，以更有效地空间并找出最优解。

四、算法步骤1.设置初始状态：设置初始状态，即的起点，以决定从哪里开始。

2.评估函数：定义一个评估函数，该函数可以比较当前状态与最终状态之间的差距。

讲述了搜索策略中的启发式搜索,对它的原理进行讲解,前景进行了展望。

 盲目搜索即是按预定的控制策略进行搜索[1],这种搜索具有盲目性,效率不高,不便于复杂问题的求解。

为解决此类问题,人们提出启发式搜索策略,即在搜索中加入与问题有关的启发式信息,用以指导搜索朝着最有希望的方向前进,加速问题求解的效率并找到最优解。

一、启发式搜索策略的发展历史40年代:由于实际需要,提出了启发式算法,具有快速有效的特点。

60年代:反思阶段,人们发现以前提出的启发式算法速度很快,但是解的质量不稳定,而且对大规模的问题仍然无能为力。

70年代:计算复杂性理论的提出。

人们发现贪婪算法和局部搜索算法速度快,但解不好的原因是得到的解没有全局最优性。

Holland的遗传算法的出现再次引发了人们研究启发式算法的兴趣。

80年代以后,模拟退火算法,人工神经网络,禁忌搜索等新式算法相继出现。

二、启发式搜索策略的工作原理盲目式搜索求解的过程中,节点的扩展次序是随意的,且没有利用已解决问题的特性,为此需要扩展的节点数会非常大。

启发式搜索则克服了上述缺点,它利用搜索过程中的有用信息优化搜索。

一一般搜索过程基本思想[2]:把初始结点作为当前状态,选择适用的算符对其进行操作,生成一组子状态,然后检查目标状态是否在其中出现。

启发式图搜索算法摘要：启发式搜索策略概述和有序搜索。

启发式搜索弥补盲目搜索的不足，提高搜索效率。

一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大为提高。

进行搜索技术一般需要某些有关具体问题领域的特性的信息。

所以引入了启发式图搜索算法。

启发式图搜索算法就是进行搜索技术一般需要某些有关具体问题领域的特性的信息，把此种信息叫做启发信息。

利用启发信息的搜索方法叫做启发式搜索方法。

关于图搜索的启发式搜索算法就叫做启发式图搜索算法。

启发式图搜索策略：假设初始状态、算符和目标状态的定义都是完全确定的，然后决定一个搜索空间。

因此，问题就在于如何有效地搜索这个给定空间。

启发信息按其用途可分为下列3种：(1)用于决定要扩展的下一个节点，以免像在宽度优先或深度优先搜索中那样盲目地扩展。

(2)在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节点。

(3)用于决定某些应该从搜索树中抛弃或修剪的节点。

启发信息的状态空间搜索算法，即决定哪个是下一步要扩展的节点。

这种搜索总是选择“最有希望”的节点作为下一个被扩展的节点。

这种搜索叫做有序搜索(orderedsearch)。

有关具体问题领域的信息常常可以用来简化搜索。

一个比较灵活(但代价也较大)的利用启发信息的方法是应用某些准则来重新排列每一步OPEN表中所有节点的顺序。

然后，搜索就可能沿着某个被认为是最有希望的边缘区段向外扩展。

应用这种排序过程，需要某些估算节点“希望”的量度，这种量度叫做估价函数(evalutionfunction)。

所谓的估价函数就是为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。

f(n)——表示节点n的估价函数值建立估价函数的一般方法：试图确定一个处在最佳路径上的节点的概率；提出任意节点与目标集之间的距离量度或差别量度；或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。

这些特点被认为与向目标节点前进一步的希望程度有关。

有序搜索应用某个算法(例如等代价算法)选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。

这种搜索方法叫做有序搜索(orderedsearch)或最佳优先搜索(best-firstsearch)，而其算法就叫做有序搜索算法或最佳优先算法。

尼尔逊曾提出一个有序搜索的基本算法。

估价函数f是这样确定的：一个节点的希望程序越大，其f值就越小。

被选为扩展的节点，是估价函数最小的节点。

选择OPEN表上具有最小f值的节点作为下一个要扩展的节点，即总是选择最有希望的节点作为下一个要扩展的节点。

有序状态空间搜索算法(1)把起始节点S放到OPEN表中，计算f(S)并把其值与节点S联系起来。

(2)如果OPEN是个空表，则失败退出，无解。

(3)从OPEN表中选择一个f值最小的节点i。

结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点i。

(4)把节点i从OPEN表中移出，并把它放入CLOSED的扩展节点表中。

(5)如果i是个目标节点，则成功退出，求得一个解。

(6)扩展节点i，生成其全部后继节点。

对于i的每一个后继节点j：(a)计算f(j)。

(b)如果j既不在OPEN表中，又不在CLOSED表中，则用估价函数f把它添入OPEN表。

从j加一指向其父辈节点i的指针，以便一旦找到目标节点时记住一个解答路径。

(c)如果j已在OPEN表上或CLOSED表上，则比较刚刚对j计算过的f值和前面计算过的该节点在表中的f值。

如果新的f值较小，则(i)以此新值取代旧值。

(ii)从j指向i，而不是指向它的父辈节点。

(iii)如果节点j在CLOSED表中，则把它移回OPEN表。

(7)转向(2)，即GOTO(2)。

有序搜索方法分析宽度优先搜索、等代价搜索和深度优先搜索统统是有序搜索技术的特例。

对于宽度优先搜索，选择f(i)作为节点i的深度。

对于等代价搜索，f(i)是从起始节点至节点i这段路径的代价。

有序搜索的有效性直接取决于f的选择，如果选择的f不合适，有序搜索就可能失去一个最好的解甚至全部的解。

如像解八数码难题就采用了简单的估价函数f(n)=d(n)+W(n)其中：d(n)是搜索树中节点n的深度；W(n)用来计算对应于节点n的数据库中错放的棋子个数。

因此，起始节点棋局28316475的f值等于0+4=4。

A*算法A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。

公式表示为：f(n)=g(n)+h(n),其中f(n)是节点n从初始点到目标点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。

保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)<=n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。

但能得到最优解。

如果估价值>实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

估价值与实际值越接近，估价函数取得就越好。

例如对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。

明显优于Dijstra算法的毫无无方向的向四周搜索。

主要搜索过程：创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。

遍历当前节点的各个节点，将n节点放入CLOSE中，取n节点的子节点X,->算X的估价值->While(OPEN!=NULL){从OPEN表中取估价值f最小的节点n;if(n节点==目标节点)break;else{if(XinOPEN)比较两个X的估价值f//注意是同一个节点的两个不同路径的估价值if(X的估价值小于OPEN表的估价值)更新OPEN表中的估价值;//取最小路径的估价值if(XinCLOSE)比较两个X的估价值//注意是同一个节点的两个不同路径的估价值if(X的估价值小于CLOSE表的估价值)更新CLOSE表中的估价值;把X节点放入OPEN//取最小路径的估价值if(Xnotinboth)求X的估价值;并将X插入OPEN表中;//还没有排序}将n节点插入CLOSE表中;按照估价值将OPEN表中的节点排序;//实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。

启发式搜索其实有很多的算法，比如：局部择优搜索法、最好优先搜索法等等。

当然A*也是。

这些算法都使用了启发函数，但在具体的选取最佳搜索节点时的策略不同。

象局部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点，父亲节点，而一直得搜索下去。

这种搜索的结果很明显，由于舍弃了其他的节点，可能也把最好的节点都舍弃了，因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳。

最好优先就聪明多了，他在搜索时，便没有舍弃节点（除非该节点是死节点），在每一步的估价中都把当前的节点和以前的节点的估价值比较得到一个“最佳的节点”。

这样可以有效的防止“最佳节点”的丢失。

那么A*算法又是一种什么样的算法呢？其实A*算法也是一种最好优先的算法。

只不过要加上一些约束条件罢了。

由于在一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，A*就是干这种事情的！我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。

A*算法是一个可采纳的最好优先算法。

可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。

我们说应用这种估价函数的最好优先算法就是A*算法。

哈。

你懂了吗？肯定没懂。

接着看。

举一个例子，其实广度优先算法就是A*算法的特例。

启发式图搜索算法的应用非常广范，在现代社会的很多领域都有应用如图像边缘提取的启发式搜索算法、基于启发式图搜索的最小测点集优选新算法、求图的最大独立集的启发式搜索算法、模糊图的启发式搜索算法等等都是在启发式图搜索的基础上发展起来的。

参考文献[1]杨成林田书林基于启发式图搜索最小测点集优选新算法仪器仪表学报-2008年[2]王迎庆模糊图的启发式搜索算法FA计算机工程与应用-1991年[3]吴江求图的最大独立集的启发式搜索算法计算机应用与软件-1990年[4]李长青《人工智能》中国矿业大学出版社[5]尚福华《人工智能及其应用》电子工业出版社[6]王士同《人工智能教程》电子工业出版社。