文档介绍：算
法
设
计
与
分
析
论
文
汽车加油问题&
贪心算法实证与探讨
院系:计算机与通信工程学院
班级:计算机科学08-2班
日期:2011-6-1
汽车加油问题算法实证与探讨
贪心算法介绍
贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
贪心算法的基本思路
。
。
,得到子问题的局部最优解。
。
实现该算法的过程:
从问题的某一初始解出发;
while 能朝给定总目标前进一步 do
求出可行解的一个解元素;
由所有解元素组合成问题的一个可行解。
下面将由一个问题来具体阐述
(一) 问题描述
一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少,设计一个有效的算法,指出应在那些加油站停靠加油。
给出N,并以数组的形式给出加油站的个数及相邻距离,指出若要使沿途的加油次数最少,设计一个有效的算法,指出应在那些加油站停靠加油。要求:算法执行的速度越快越好。
(二) 问题分析(前提行驶前车里加满油)
对于这个问题我们有以下几种情况:设加油次数为k,每个加油站间距离为a[i];i=0,1,2,3……n
,则加油次数k=0;
,
A 加油站间的距离相等,即a[i]=a[j]=L=N,则加油次数最少k=n;
B 加油站间的距离相等,即a[i]=a[j]=L>N,则不可能到达终点;
C 加油站间的距离相等,即a[i]=a[j]=L<N,则加油次数k=n/N(n%N==0)或k=[n/N]+1(n%N!=0);
D 加油站间的距离不相等,即a[i]!=a[j],则加油次数k通过以下算法求解。
(三)算法描述
贪心算法的基本思想
该题目求加油最少次数,即求最优解的问题,可分成几个步骤,一般来说,每个步骤的最优解不一定是整个问题的最优解,然而对于有些问题,局部贪心可以得到全局的最优解。贪心算法将问题的求解过程看作是一系列选择,从问题的某一个初始解出发,向给定目标推进。推进的每一阶段不是依据某一个固定的递推式,而是在每一个阶段都看上去是一个最优的决策(在一定的标准下)。不断地将问题实例归纳为更小的相似的子问题,并期望做出的局部最优的选择产生一个全局得最优解。
贪心算法的适用的问题
贪心算法适用的问题必须满足两个属性:
(1)  贪心性质:整体的最优解可通过一系列局部最优解达到,并且每次的选择可以依赖以前做出的选择,但不能依赖于以后的选择。
(2)  最优子结构:问题的整体最优解包含着它的子问题的最优解。
贪心算法的基本步骤
(1)  分解:将原问题分解为若干相互独立的阶段。
(2)  解决:对于每一个阶段求局部的最优解。
(3)  合并:将各个阶段的解合并为原问题的解。
[问题分析]