解决汽车加油问题的有效算法

1.问题描述

一辆汽车加满油后可以行驶M km，两城市间距离为N，旅途中有加油站，设计一个有效算法，指出要想从一城市到另一城市，汽车应在哪些加油站停靠加油，使沿途加油次数最少。

2.问题分析

先分析一下，对于这个问题有以下几种情况：设加油次数为k，共n个加油站，每个加油站间距离为a[i]，i=0,1,2,3,…,n。

（1） 始点到终点的距离N＜M，则加油次数k=0。

（2） 始点到终点的距离N＞M，则有以下几种情况：

① 加油站间的距离相等，即a[i]=a[j]=L=M，则加油次数最少k=n；

② 加油站间的距离相等，即a[i]=a[j]=L＞M，则不可能到达终点；

③ 加油站间的距离相等，即a[i]=a[j]=L＜M，则加油次数k=N/(L× )；

④ 加油站间的距离不相等，即a[i]!=a[j]，则加油次数k可以通过贪心算法求解。

分析该问题是否满足用贪心算法解决问题的两个特征。

① 贪心选择性质，也就是按贪心选择策略最终能够得到问题最优解的性质。(www.xing528.com)

本问题的最优解是要求最少加油次数，而采用的贪心选择策略是“让汽车跑最远的距离，直到无法到达才加油”的策略，那么相反“汽车加油次数”也就最少了。这里贪心选择策略是不到万不得已不加油，即除非油箱里的油不足以开到下一个加油站才进行加油，贪心选择策略得到的解为（x1,x2,…,xn），其中，xi取值{0,1}，它是最优解。用反证法简单说明一下，假设最优解（y1,y2,…,ym）（其中yi取值{0,1}）不是按照此贪心选择得到的。设最优解中在某加油站i，汽车仍有足够的油跑到下面某个加油站i+s时就加了油，即yi=1，那么在第i+s个加油站yi+s取值有两种情况，即yi+s=0或者yi+s=1。按照贪心策略，若yi+s=0，那么按贪心选择策略令yi=0,yi+s=1，加油次数仍为最少；若yi+s=1，那么令yi=0，则加油次数更少。这就说明贪心选择能使得加油次数更少，与假设矛盾。所以，由贪心选择策略可以得到最终最优解，汽车加油问题满足贪心选择性质。

② 最优子结构性质，也就是问题的最优解包含其子问题的最优解。

本问题是要求出最少加油次数，而子问题就是在已经走过一定距离后，在剩余距离加油次数最少。同样用反证法来简单说明，如果最优解（x1,…,xn）中不包含子问题的最优解（xi,…,xn），则设子问题最优解（yi,…,yn）为在剩余距离下加油次数最少，则用其替换（xi,…,xn），得到（x1,…,yi,…,yn），比原解更优，与原最优解（x1,…,xn）相矛盾。所以原问题最优解包含子问题最优解，问题满足最优子结构性质。

3.解决问题

最终，汽车加油问题可以由贪心选择策略来解决，算法步骤如下。

步骤1：初始状态，将汽车加满油。

步骤2：如果到达终点，则解题完成；否则转步骤3。

步骤3：能够到达下一个加油站，则不加油，xi=0，转步骤2；若不能到达下一个加油站，则在该加油站加油，xi=1，转步骤2。

具体算法程序如下：

算法的时间复杂度在于每一个加油站处都要计算一下汽车是否能行驶到下一个加油站处，n个加油站处共需计算n次，循环了n次，因此算法的时间复杂度为O(n)。