启发式算法例题

㈠ 经典的启发式算法包括哪些

蚁群，模拟退火，禁忌搜索，人工神经网络等。。。
推荐教材《现代优化计算方法》第二版 邢文训，谢金星 清华大学出版社
另一本补充，《最优化理论与方法》 黄平 清华大学出版社

第一本教材网上有电子版，你自己搜下

㈡ 元启发式算法的算法原理

1. 从一个或多个候选解开始作为初始值（pop（t））。
2. 根据初始值计算目标函数值
3. 基于已获得的信息，通过个体变异、组合等方法不断更新候选解域。
4. 新的候选解域进入下一轮迭代(pop(t+1))
如下图：

例如它常能发现很不错的解，但也没办法证明它不会得到较坏的解；它通常可在合理时间解出答案，但也没办法知道它是否每次都可以这样的速度求解。有时候人们会发现在某些特殊情况下，启发式算法会得到很坏的答案或效率极差，然而造成那些特殊情况的数据结构，也许永远不会在现实世界出现。因此现实世界中启发式算法常用来解决问题。启发式算法处理许多实际问题时通常可以在合理时间内得到不错的答案。有一类的通用启发式策略称为元启发式算法（metaheuristic algorithm） ，通常使用乱数搜寻技巧。他们可以应用在非常广泛的问题上，但不能保证效率。

㈢ 节约里程法的典型例题有哪些

节约里程法基本原理是几何学中三角形一边之长必定小于另外两边之和。往返发货与巡回发货车辆行走距离∆l=[2(l1+l2)]-(l1+l2+l3)=l1+l2-l3。

㈣ A*算法——启发式路径搜索

A*是一种路径搜索算法，比如为游戏中的角色规划行动路径。

A* 算法的输入是， 起点（初始状态） 和 终点（目标状态） ，以及两点间 所有可能的路径 ，以及涉及到的 中间节点（中间状态） ，每两个节点间的路径的 代价 。

一般还需要某种 启发函数 ，即从任意节点到终点的近似代价，启发函数能够非常快速的估算出该代价值。

输出是从 起点到终点的最优路径 ，即代价最小。同时，好的启发函数将使得这一搜索运算尽可能高效，即搜索尽量少的节点/可能的路径。

f(n)=g(n)+h(n)

f(n) 是从初始状态经由状态n到目标状态的代价估计

g(n) 是在状态空间中从初始状态到状态n的实际代价

h(n) 是从状态n到目标状态的最佳路径的估计代价

A*算法是从起点开始，检查所有可能的扩展点（它的相邻点），对每个点计算g+h得到f，在所有可能的扩展点中，选择f最小的那个点进行扩展，即计算该点的所有可能扩展点的f值，并将这些新的扩展点添加到扩展点列表（open list）。当然，忽略已经在列表中的点、已经考察过的点。

不断从open list中选择f值最小的点进行扩展，直到到达目标点（成功找到最优路径），或者节点用完，路径搜索失败。

算法步骤：

参考

A* 算法步骤的详细说明请参考 A*寻路算法 ，它包含图文案例清楚的解释了A*算法计算步骤的一些细节，本文不再详细展开。

看一下上面参考文档中的案例图，最终搜索完成时，蓝色边框是close list中的节点，绿色边框是open list中的节点，每个方格中三个数字，左上是f（=g+h），左下是g（已经过路径的代价），右下是h（估计未经过路径的代价）。蓝色方格始终沿着f值最小的方向搜索前进，避免了对一些不好的路径（f值较大）的搜索。（图片来自 A*寻路算法 ）

现在我们可以理解，A*算法中启发函数是最重要的，它有几种情况：

1) h(n) = 0
一种极端情况，如果h(n)是0，则只有g(n)起作用，此时A*演变成Dijkstra算法，这保证能找到最短路径。但效率不高，因为得不到启发。

2) h(n) < 真实代价
如果h(n)经常都比从n移动到目标的实际代价小（或者相等），则A*保证能找到一条最短路径。h(n)越小，A*扩展的结点越多，运行就得越慢。越接近Dijkstra算法。

3) h(n) = 真实代价
如果h(n)精确地等于从n移动到目标的代价，则A*将会仅仅寻找最佳路径而不扩展别的任何结点，这会运行得非常快。尽管这不可能在所有情况下发生，你仍可以在一些特殊情况下让它们精确地相等（译者：指让h(n)精确地等于实际值）。只要提供完美的信息，A*会运行得很完美，认识这一点很好。

4) h(n) > 真实代价
如果h(n)有时比从n移动到目标的实际代价高，则A*不能保证找到一条最短路径，但它运行得更快。

5) h(n) >> 真实代价
另一种极端情况，如果h(n)比g(n)大很多，则只有h(n)起作用，A*演变成BFS算法。

关于启发函数h、Dijkstra算法、BFS（最佳优先搜索）算法、路径规划情况下启发函数的选择、算法实现时List的数据结构、算法变种等等更多问题，请参考： A*算法

㈤ 贪心算法的例题分析

例题1、
[0-1背包问题]有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg
价值 10$ 40$ 30$ 50$ 35$ 40$ 30$
分析：
目标函数：∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M(M=150）
⑴根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
⑵每次挑选所占重量最小的物品装入是否能得到最优解？
⑶每次选取单位重量价值最大的物品，成为解本题的策略。
值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。
贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。
可惜的是，它需要证明后才能真正运用到题目的算法中。
一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：
⑴贪心策略：选取价值最大者。
反例：
W=30
物品：A B C
重量：28 12 12
价值：30 20 20
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。
⑵贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。
⑶贪心策略：选取单位重量价值最大的物品。
反例：
W=30
物品：A B C
重量：28 20 10
价值：28 20 10
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。
【注意：如果物品可以分割为任意大小，那么策略3可得最优解】
对于选取单位重量价值最大的物品这个策略，可以再加一条优化的规则：对于单位重量价值一样的，则优先选择重量小的！这样，上面的反例就解决了。
但是，如果题目是如下所示，这个策略就也不行了。
W=40
物品：A B C
重量：25 20 15
价值：25 20 15
附：本题是个DP问题，用贪心法并不一定可以求得最优解，以后了解了动态规划算法后本题就有了新的解法。
例题2、
马踏棋盘的贪心算法
123041-23 XX
【问题描述】
马的遍历问题。在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。
【初步设计】
首先这是一个搜索问题，运用深度优先搜索进行求解。算法如下：
⒈ 输入初始位置坐标x,y；
⒉ 步骤 c:
如果c> 64输出一个解，返回上一步骤c--
（x,y) ← c
计算(x,y）的八个方位的子结点，选出那些可行的子结点
循环遍历所有可行子结点，步骤c++重复2
显然⑵是一个递归调用的过程，大致如下：
C++程序： #defineN8voiddfs(intx,inty,intcount){inti,tx,ty;if(count>N*N){output_solution();//输出一个解return;}for(i=0;i<8;i++){tx=hn[i].x;//hn[]保存八个方位子结点ty=hn[i].y;s[tx][ty]=count;dfs(tx,ty,count+1);//递归调用s[tx][ty]=0;}}Pascal程序： ProgramYS;ConstFXx:array[1..8]of-2..2=（1,2,2,1,-1,-2,-2,-1）；FXy:array[1..8]of-2..2=（2,1,-1,-2,-2,-1,1,2）；VarRoad:array[1..10,1..10]ofinteger;x,y,x1,y1,total:integer;ProcereFind(x,y:integer);varNx,Ny,i:integer;BeginFori:=1to8dobegin{8个方向}If(x+FXx[i]in[1..8])and(y+FXy[i]in[1..8])Then{确定新坐标是否越界}IfRoad[x+Fxx[i],y+Fxy[i]]=0Thenbegin{判断是否走过}Nx:=x+FXx[i];Ny:=y+FXy[i];Road[Nx,Ny]:=1;{建立新坐标}If(Nx=x1）and(Ny=y1）Theninc(total)elseFind(Nx,Ny);{递归}Road[Nx,Ny]:=0{回朔}endendEnd;BEGIN{Main}Total:=0;FillChar(Road,sizeof(road),0);Readln(x,y);{读入开始坐标}Readln(x1,y1）；{读入结束坐标}If(x>10）or(y>10）or(x1>10）or(y1>10）Thenwriteln('Error'){判断是否越界}ElseFind(x,y);Writeln('Total:',total){打出总数}END.这样做是完全可行的，它输入的是全部解，但是马遍历当8×8时解是非常之多的，用天文数字形容也不为过，这样一来求解的过程就非常慢，并且出一个解也非常慢。
怎么才能快速地得到部分解呢？
【贪心算法】
其实马踏棋盘的问题很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法称为为贪心算法，也叫贪婪算法或启发式算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。这样的调整方法叫贪心策略，至于什么问题需要什么样的贪心策略是不确定的，具体问题具体分析。实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非常明显的提高，如果只要求出一个解甚至不用回溯就可以完成，因为在这个算法提出的时候世界上还没有计算机，这种方法完全可以用手工求出解来，其效率可想而知。

㈥ 什么是启发式

这两天在看关于民航调度的文章，很多文章中都提到“启发式”算法，感觉和智能算法类似，那到底算法呢？我找到如下的一些我认为比较好的解释：------------------------------------------------------------------------------------------------------------------------A heuristic (hyu-'ris-tik) is the art and science of discovery and invention. The word comes from the same Greek root as "eureka" meaning "to find". A heuristic for a given problem is a way of directing your attention fruitfully to a solution. It is different from an algorithm in that a heuristic merely serves as a rule-of-thumb or guideline, as opposed to an invariant procere. Heuristics may not always achieve the desired outcome, but can be extremely valuable to problem-solving processes. Good heuristics can dramatically rece the time required to solve a problem by eliminating the need to consider unlikely possibilities or irrelevant states. As such, it is particularly useful to those in the process of discovery and the are constantly rethinking their strategies in the face of a stubborn unknown. --------------------------------------------------------------------------------------------------------------------------启发式方法（试探法）是一种帮你寻求答案的技术，但它给出的答案是具有偶然性的（subject to chance），因为启发式方法仅仅告诉你该如何去找，而没有告诉你要找什么。它并不告诉你该如何直接从A 点到达B 点，它甚至可能连A点和B点在哪里都不知道。实际上，启发式方法是穿着小丑儿外套的算法：它的结果不太好预测，也更有趣，但不会给你什么30 天无效退款的保证。 驾驶汽车到达某人的家，写成算法是这样的：沿167 号高速公路往南行至Puyallup；从South Hill Mall 出口出来后往山上开4.5 英里；在一个杂物店旁边的红绿灯路口右转，接着在第一个路口左转；从左边褐色大房子的车道进去，就是North Cedar 路714 号。用启发式方法来描述则可能是这样：找出上一次我们寄给你的信，照着信上面的寄出地址开车到这个镇；到了之后你问一下我们的房子在哪里。这里每个人都认识我们——肯定有人会很愿意帮助你的；如果你找不到人，那就找个公共电话亭给我们打电话，我们会出来接你。算法和启发式方法之间的差别很微妙，两个术语的意思也有一些重叠。就本书的目的而言，它们之间的差别就在于其距离最终解决办法的间接程度：算法直接给你解决问题的指导，而启发式方法则告诉你该如何发现这些指导信息，或者至少到哪里去寻找它们。----------------------------------------------------------------------------------------------------------------------------从上面的启发式算法的解释可以看出，启发式算法的难点是建立符合实际问题的一系列启发式规则。

㈦ 有关启发式算法（Heuristic Algorithm）的一些总结

节选自维基网络：

启发法 （ heuristics ，源自古希腊语的εὑρίσκω，又译作：策略法、助发现法、启发力、捷思法）是指 依据有限的知识 （或“不完整的信息”）在短时间内找到问题解决方案的一种技术。

它是一种依据 关于系统的有限认知 和 假说 从而得到关于此系统的结论的分析行为。由此得到的解决方案有可能会偏离最佳方案。通过与最佳方案的对比，可以确保启发法的质量。

计算机科学的两大基础目标，就是 发现可证明其运行效率良好 且可 得最佳解或次佳解 的算法。

而启发式算法则 试图一次提供一个或全部目标 。例如它常能发现很不错的解， 但也没办法证明它不会得到较坏的解 ； 它通常可在合理时间解出答案，但也没办法知道它是否每次都可以这样的速度求解。

有时候人们会发现在某些特殊情况下，启发式算法会得到很坏的答案或效率极差， 然而造成那些特殊情况的数据结构，也许永远不会在现实世界出现 。

因此现实世界中启发式算法很常用来解决问题。启发式算法处理许多实际问题时通常可以在合理时间内得到不错的答案。

有一类的 通用启发式策略称为元启发式算法（metaheuristic） ，通常使用随机数搜索技巧。他们可以应用在非常广泛的问题上，但不能保证效率。

节选自网络：

启发式算法可以这样定义：一个 基于直观或经验构造 的算法， 在 可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解 ， 该可行解与最优解的偏离程度一般不能被预计。 现阶段，启发式算法以仿自然体算法为主，主要有蚁群算法、模拟退火法、神经网络等。

目前比较通用的启发式算法一般有模拟退火算法（SA）、遗传算法（GA）、蚁群算法（ACO）。

模拟退火算法(Simulated Annealing, SA)的思想借鉴于固体的退火原理，当固体的温度很高的时候，内能比较大，固体的内部粒子处于快速无序运动，当温度慢慢降低的过程中，固体的内能减小，粒子的慢慢趋于有序，最终，当固体处于常温时，内能达到最小，此时，粒子最为稳定。模拟退火算法便是基于这样的原理设计而成。

求解给定函数的最小值：其中，0<=x<=100,给定任意y的值，求解x为多少的时候，F(x)最小？

遗传算法（Genetic Algorithm, GA）起源于对生物系统所进行的计算机模拟研究。它是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种 高效、并行、全局搜索 的方法，能在搜索过程中自动获取和积累有关搜索空间的知识，并 自适应 地控制搜索过程以求得最佳解。

给定一组五个基因，每一个基因可以保存一个二进制值 0 或 1。这里的适应度是基因组中 1 的数量。如果基因组内共有五个 1，则该个体适应度达到最大值。如果基因组内没有 1，那么个体的适应度达到最小值。该遗传算法希望 最大化适应度 ，并提供适应度达到最大的个体所组成的群体。

想象有一只蚂蚁找到了食物，那么它就需要将这个食物待会蚂蚁穴。对于这只蚂蚁来说，它并不知道应该怎么回到蚂蚁穴。

这只蚂蚁有可能会随机选择一条路线，这条路可能路程比较远，但是这只蚂蚁在这条路上留下了记号（一种化学物质，信息素）。如果这只蚂蚁继续不停地搬运食物的时候，有其它许多蚂蚁一起搬运的话，它们总会有运气好的时候走到更快返回蚂蚁穴的路线。当蚂蚁选择的路线越优，相同时间内蚂蚁往返的次数就会越多，这样就在这条路上留下了更多的信息素。

这时候，蚂蚁们就会选择一些路径上信息素越浓的，这些路径就是较优的路径。当蚂蚁们不断重复这个过程，蚂蚁们就会更多地向更浓的信息素的路径上偏移，这样最终会确定一条路径，这条路径就是最优路径。

㈧ 什么是启发式算法

大自然是神奇的，它造就了很多巧妙的手段和运行机制。受大自然的启发，人们从大自然的运行规律中找到了许多解决实际问题的方法。对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法（Heuristic Algorithm）。现在的启发式算法也不是全部来自然的规律，也有来自人类积累的工作经验。 驾驶汽车到达某人的家，写成算法是这样的：沿167 号高速公路往南行至阳谷；从阳谷高速出口出来后往山上开4.5 英里；在一个杂物店旁边的红绿灯路口右转，接着在第一个路口左转；从左边褐色大房子的车道进去，就是某人的家。 启发式方法来描述则可能是这样：找出上一次我们寄给你的信，照着信上面的寄出地址开车到这个镇；到了之后你问一下我们的房子在哪里。这里每个人都认识我们——肯定有人会很愿意帮助你的；如果你找不到人，那就找个公共电话亭给我们打电话，我们会出来接你。

㈨ 什么是启发式搜索并以八数码难题为例,说明其原理

启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。
启发中的估价是用估价函数表示的，如：
最佳优先搜索的最广为人知的形式称为A*搜索(发音为“A星搜索”).它把到达节点的耗散g(n)
和从该节点到目标节点的消耗h(n)结合起来对节点进行评价：f(n)=g(n)+h(n)
因为以g(n)给出了从起始节点到节点n的路径耗散，而h(n)是从节点n到目标节点的最低耗散路径的估计耗散值，因此f(n)=经过节点n的最低耗散解的估计耗散.这样，如果我们想要找到最低耗散解，首先尝试找到g(n)+h(n)值最小的节点是合理的。可以发现这个策略不只是合理的:倘若启发函数h(n)满足一定的条件，A*搜索既是完备的也是最优的。
如果把A*搜索用于Tree-Search,它的最优性是能够直接分折的。在这种情况下，如果h(n)是一个可采纳启发式--也就是说，倘若h(n)从不会过高估计到达目标的耗散--A*算法是最优的。可采纳启发式天生是最优的，因为他们认为求解问题的耗散是低于实际耗散的。因为g(n)是到达节点n的确切耗散，我们得到一个直接的结论：f(n)永远不会高估经过节点n的解的实际耗散.
启发算法有：
蚁群算法，遗传算法、模拟退火算法等
蚁群算法是一种来自大自然的随机搜索寻优方法，是生物界的群体启发式行为，现己陆续应用到组合优化、人工智能、通讯等多个领域。蚁群算法的正反馈性和协同性使其可用于分布式系统，隐含的并行性更使之具有极强的发展潜力。从数值仿真结果来看，它比目前风行一时的遗传算法、模拟退火算法等有更好的适应性。

㈩ 启发式算法的最短路径

所谓的最短路径问题有很多种意思， 在这里启发式指的是一个在一个搜寻树的节点上定义的函数h(n)，用于评估从此节点到目标节点最便宜的路径。启发式通常用于资讯充分的搜寻算法，例如最好优先贪婪算法与A*。最好优先贪婪算法会为启发式函数选择最低代价的节点；A*则会为g(n) + h(n)选择最低代价的节点，此g(n)是从起始节点到目前节点的路径的确实代价。如果h(n)是可接受的（admissible）意即h(n)未曾付出超过达到目标的代价，则A*一定会找出最佳解。
最能感受到启发式算法好处的经典问题是n-puzzle。此问题在计算错误的拼图图形，与计算任两块拼图的曼哈顿距离的总和以及它距离目的有多远时，使用了本算法。注意，上述两条件都必须在可接受的范围内。