寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找到所需要的解。理论上，当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时，上述方法是可行的。不过，在实际应用中，很少使用这种方法，因为候选解的数量通常都非常大（比如指数级，甚至是大数阶乘），即便采用最快的计算机也只能解决规模很小的问题。对候选解进行系统检查的方法有多种，其中回溯和分枝定界法是比较常用的两种方法。按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少（无论对于最坏情形还是对于一般情形）。事实上，这些方法可以使我们避免对很大的候选解集合进行检查，同时能够保证算法运行结束时可以找到所需要的解。因此，这些方法通常能够用来求解规模很大的问题。
本章集中阐述回溯方法，这种方法被用来设计货箱装船、背包、最大完备子图、旅行商和电路板排列问题的求解算法。
1算法思想
回溯（ba c k t r a c k i n g）是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间（solution space），这个空间必须至少包含问题的一个解（可能是最优的）。在迷宫老鼠问题中，我们可以定义一个包含从入口到出口的所有路径的解空间；在具有n 个对象的0/1背包问题中（见1. 4节和2. 2节），解空间的一个合
理选择是2n 个长度为n 的0/1向量的集合，这个集合表示了将0或1分配给x 的所有可能方
法。当n=3时，解空间为{(0, 0, 0)，(0, 1, 0)，(0, 0, 1)，(1, 0, 0)，(0, 1, 1)，(1, 0, 1)，(1, 1, 0)，(1, 1, 1) }。
下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图或树。图16-1用图的形式给出了一个3×3迷宫的解空间。从(1, 1)点到(3, 3)点的每一条路径都定义了3×3迷宫解空间中的一个元素，但由于障碍的设置，有些路径是不可行的。
图16-2用树形结构给出了含三个对象的0/1背包问题的解空间。从i 层节点到i+1层
节点的一条边上的数字给出了向量x 中第i 个分量的值xi ，从根节点到叶节点的每一条路径定义了解空间中的一个元素。从根节点A 到叶节点H 的路径定义了解x=[1, 1, 1]。根据w 和c 的值，从根到叶的路径中的一些解或全部解可能是不可行的。
一旦定义了解空间的组织方法，这个空间即可按深度优先的方法从开始节点进行搜索。在迷宫老鼠问题中，开始节点为入口节点(1, 1)；在0/1背包问题中，开始节点为根节点A。开始节点既是一个活节点又是一个E-节点（expansionnode）。从E-节点可移动到一个新节点。如果能从当前的E-节点移动到一个新节点，那么这个新节点将变成一个活节点和新的E-节点，旧的E-节点仍是一个活节点。如果不能移到一个新节点，当前的E-节点就“死”了（即不再是一个活节点），那么便只能返回到最近被考察的活节点（回溯），这个活节点变成了新的E-节点。当我们已经找到了答案或者回溯尽了所有的活节点时，搜索
例4-1[迷宫老鼠]考察图16-3a 的矩阵中给出的3×3的“迷宫老鼠”问题。我们将利用图
16-1给出的解空间图来搜索迷宫。
从迷宫的入口到出口的每一条路径都与图16-1中从(1, 1)到(3, 3)的一条路径相对应。然而，图16-1中有些从(1, 1)到(3, 3)的路径却不是迷宫中从入口到出口的路径。搜索从点(1, 1)开始，该点是目前唯一的活节点，它也是一个E-节点。为避免再次走过这个位置，置m a z e(1, 1)为1。从这个位置，能移动到(1, 2)或(2,
1)两个位置。对于本例，两种移动都是可行的，因为在每一个位置都有一个值0。假定选择移动到(1, 2)，ma z e(1, 2)被置为1以避免再次经过该点。迷宫当前状态如图16-3b 所示。这时有两个活节点(1,1)(1,2)。(1, 2)成为E-节点。
在图16-1中从当前E-节点开始有3个可能的移动，其中两个是不可行的，因为迷宫在这
些位置上的值为1。唯一可行的移动是(1, 3)。移动到这个位置，并置m a z e(1, 3)为1以避免再次经过该点，此时迷宫状态为16-3c。图16-1中，从(1, 3)出发有两个可能的移动，但没有一个是可行的。所以E-节点(1, 3)死亡，回溯到最近被检查的活节点(1, 2)。在这个位置也没有可行的移动，故这个节点也死亡了。唯一留下的活节点是(1, 1)。这个节点再次变为E-节点，它可移动到(2, 1)。现在活节点为(1, 1)，(2, 1)。继续下去，能到达点(3, 3)。此时，活节点表为(1, 1)，(2, 1)，(3, 1)，(3, 2)，(3, 3)，这即是到达出口的路径。
程序5-13是一个在迷宫中寻找路径的回溯算法。
贪心算法
一、算法思想
贪心法的基本思路：
——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围。
实现该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；
二、例题分析
1、[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品
E
重量
价值
5A F 35101040B G [1**********]04C D 30503
分析：
目标函数：∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi
（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占空间最小的物品装入是否能得到最优解？
（3）每次选取单位容量价值最大的物品，成为解本题的策略。
源程序
2、[单源最短路径]一个有向图G，它的每条边都有一个非负的权值c[i,j]，“路径长度”就是所经过的所有边的权值之和。对于源点需要找出从源点出发到达其他所有结点的最短路径。
E.Dijkstra 发明的贪婪算法可以解决最短路径问题。算法的主要思想是：分步求出最短路径，每一步产生一个到达新目的顶点的最短路径。下一步所能达到的目的顶点通过如下贪婪准则选取：在未产生最短路径的顶点中，选择路径最短的目的顶点。
设置顶点集合S 并不断作贪心选择来扩充这个集合。当且仅当顶点到该顶点的最短路径已知时该顶点属于集合S。初始时S 中只含源。
设u 为G 中一顶点，我们把从源点到u 且中间仅经过集合S 中的顶点的路称为从源到u 特殊
路径，并把这个特殊路径记录下来（例如程序中的dist[i，j]）。
每次从V-S 选出具有最短特殊路径长度的顶点u，将u 添加到S 中，同时对特殊路径长度
进行必要的修改。一旦V=S，就得到从源到其他所有顶点的最短路径，也就得到问题的解。
Dijkstra.pas
3、[机器调度]现有N 项任务和无限多台机器。任务可以在机器上处理。每件任务开始时间和完成时间有下表：
任务
e a f b g c d
开始(si)
9
完成(fi)
[**************]
在可行分配中每台机器在任何时刻最多处理一个任务。最优分配是指使用的机器最少的可行分配方案。请就本题给出的条件，求出最优分配。
三、练习题：
已知5个城市之间有班机传递邮件，目的是为了寻找一条耗油量较少的飞行路线。5个城市的联系网络如图所示。图中编号的结点表示城市，两个城市之间的连线上的值表示班机沿该航线已行的耗油量，并假定从城市i 到j 和城市j 到i 之间的耗油量是相同的。分析：
1. 运用贪心思想：
在每一步前进的选择上，选取相对当前城市耗油量最小的航线；
2. 图解：若从1出发，有图：
总耗油量=141-2-5-3-4-1
但若路线改为：1-5-3-4-2-1，则总耗油量=13
所以，这样的贪心法并不能得出最佳解。
3. 改善方案：
从所有城市出发的信心过程，求最优的。
编程：
1. 数据结构：
城市联系网络图的描述(图的邻接矩阵的描述)：
const
c=array[1..5,1..5]of integer=((0,1,2,7,5),
(1,0,4,4,3),
(2,4,0,1,2),
(7,4,1,0,3));
2. 贪心过程：
begin
初始化所有城市的算途径标志；
设置出发城市V；
for i:=1to n-1do {n-1个城市}
begin
s:=从V 至所有未曾到过的城市的边集中耗油量最少的那个城市；
累加耗油量；
V:=s；
设V 城市的访问标志；
end;
最后一个城市返回第一个城市，累加耗油量；
end;
3. 主过程：实现改善方案
begin
for i:=1to n do
begin
cost1:=maxint;{初始化}
调用贪心过程，返回本次搜索耗油量cost；
if cost
end;
输出；
end.
type
dim1=array[0..11]of integer;
const
c:array[1..5,1..5]of integer=((0,1,2,7,5),
n=5;
p=5;
var
tour:dim1;
best:dim1;
visit:array[1..n]of 0..1; (1,0,4,4,3),(2,4,0,1,2),(7,4,1,0,3),(5,3,2,3,0));
cost,cost1:integer;
i,j:integer;
procedure greedy1(g:integer;var tour:dim1;var cost:integer);
var
v,s,k:integer;
function findmin:integer;
var
i,len,s1:integer;
begin
len:=maxint;
for i:=1to n do
if (iv)and (visit[i]=0)and (c[v,i]
一、分支限界法：
分支限界法类似于回溯法，也是一种在问题的解空间树T 上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T 中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使用某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
由于求解目标不同，导致分支限界法与回溯法在解空间树T 上的搜索方式也不相同。回溯法
以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。
二、分支限界法的基本思想：
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。
三、选择下一扩展结点的不同方式：
从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法。最常见的有以下两种方式：
1、队列式(FIFO)分支限界法：队列式分支限界法将活结点表组织成一个队列，并按队列的先进先出原则选取下一个结点为当前扩展结点。
2、优先队列式分支限界法：优先队列式分支限界法将活结点表组织成一个优先队列，交按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。
四、习题：
1、0-1背包：n=3,w=[16,15,15],p=[45,25,25],c=30
2、单源最短路径：求从起点到终点的最短路径。
3、装载问题：有一批共n 个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i 的
重量为wi 且
。要求确定是否有一个合理的装载方案可将这n 个集装箱装上这
2艘轮船。如果有，找出一种装载方案。
4、布线问题：印刷电路板将布线区域划分成n X m 个方格如图a 所示。精确的电路布线问题
题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。
三、选择下一扩展结点的不同方式：
从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法。最常见的有以下两种方式：
1、队列式(FIFO)分支限界法：队列式分支限界法将活结点表组织成一个队列，并按队列的先进先出原则选取下一个结点为当前扩展结点。
2、优先队列式分支限界法：优先队列式分支限界法将活结点表组织成一个优先队列，交按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。
四、习题：
1、0-1背包：n=3,w=[16,15,15],p=[45,25,25],c=30
2、单源最短路径：求从起点到终点的最短路径。
3、装载问题：有一批共n 个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i 的重量为wi 且
。要求确定是否有一个合理的装载方案可将这n 个集装箱装上这2艘轮船。如果有，找出一种装载方案。
4、布线问题：印刷电路板将布线区域划分成n X m 个方格如图a 所示。精确的电路布线问题
要求确定连接方格a 的中点到方格b 的中点的最短布线方案。在布线时，电路只能沿直线或
直角布线，如图b 所示。为了避免线路相交，已布了线的方格做了封锁标记，其它线路不允
穿过被封锁的方格。
Dijkstra 算法：
这一算法可求得有向网格N=(V,A,W)中从一给定点v 1出发到N 中任一点的最短有向路及其长度。该算法在解决关键路线问题、背包问题、某些加工顺序、中国邮递员问题等问题很有效。算法过程如下：
（0）
给所有的点一临时标号1，然后以v 1为出发点，
U 1=0, U j =w 1j (2≤j ≤n ), T j =1(1≤j ≤n ), P ={1
Q ={2, 3, , n }。
（1）
在Q 中找k ，使得U k =min U j
}
{}(j ∈Q ). 置
}→Q
P ⋃{k }→P , Q \{k
若Q ≠∅, 进入下一步（2）；若Q =∅时，算法终止，此时U j (1≤j ≤n ) 即为
点v 1至v j 的距离，T j 表示最短路（v 1, v j ）中与v j 邻近的点v Tj 。
（2）对Q 中每一个j ，如果U k +w kj
U k +w kj →U j ,
然后返回步骤（1）。
k →T j
该算法至多经过n -1次循环必结束。
下面就具体实例编制了（在Matlab 中）程序。
例：已知v i 与v j 之间的有向路长度，求自点1到点6的最短有路。
v 1
v 1v 2v 3v 4v 5v 6
clear; M=1.0e8;
w=[05M 3M M
M 042M M M M 0243M M M 05M M M M M 02M M M M M 0];N=6;%共有n 个顶点n=N;
j=[23456];T=ones(1,n);P=[1];Q=j;
v 2
50
v 3∞
40
v 4
3220
v 5∞∞
450
v 6∞∞
3
∞∞∞∞∞
∞∞∞∞
∞∞∞
∞
20
∞∞
∞
U(1:n)=w(1,:);temp=1;
while(temp
for I=1:(n-1)xx(I)=U(Q(I)); end
for I=1:(n-1)
if U(Q(I))==min(xx);
k=Q(I);P=[P,k];end end
for I2=1:(n-1)
if Q(I2)==k
k2=I2;end end Q(k2)=[];
for I3=1:length(Q)
if U(k)+w(k,Q(I3))
U(Q(I3))=U(k)+w(k,Q(I3));T(Q(I3))=k;end end n=n-1;temp=temp+1;end
for temp=1:N
disp(['第1点到第',num2str(temp),'点的最短长度为：',blanks(4),num2str(U(temp)) ])disp(['第1点到第',num2str(temp),'点的最短路中其前一点的下标为：',blanks(4),num2str(T(temp)) ])
fprintf('\n')end
寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找到所需要的解。理论上，当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时，上述方法是可行的。不过，在实际应用中，很少使用这种方法，因为候选解的数量通常都非常大（比如指数级，甚至是大数阶乘），即便采用最快的计算机也只能解决规模很小的问题。对候选解进行系统检查的方法有多种，其中回溯和分枝定界法是比较常用的两种方法。按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少（无论对于最坏情形还是对于一般情形）。事实上，这些方法可以使我们避免对很大的候选解集合进行检查，同时能够保证算法运行结束时可以找到所需要的解。因此，这些方法通常能够用来求解规模很大的问题。
本章集中阐述回溯方法，这种方法被用来设计货箱装船、背包、最大完备子图、旅行商和电路板排列问题的求解算法。
1算法思想
回溯（ba c k t r a c k i n g）是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间（solution space），这个空间必须至少包含问题的一个解（可能是最优的）。在迷宫老鼠问题中，我们可以定义一个包含从入口到出口的所有路径的解空间；在具有n 个对象的0/1背包问题中（见1. 4节和2. 2节），解空间的一个合
理选择是2n 个长度为n 的0/1向量的集合，这个集合表示了将0或1分配给x 的所有可能方
法。当n=3时，解空间为{(0, 0, 0)，(0, 1, 0)，(0, 0, 1)，(1, 0, 0)，(0, 1, 1)，(1, 0, 1)，(1, 1, 0)，(1, 1, 1) }。
下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图或树。图16-1用图的形式给出了一个3×3迷宫的解空间。从(1, 1)点到(3, 3)点的每一条路径都定义了3×3迷宫解空间中的一个元素，但由于障碍的设置，有些路径是不可行的。
图16-2用树形结构给出了含三个对象的0/1背包问题的解空间。从i 层节点到i+1层
节点的一条边上的数字给出了向量x 中第i 个分量的值xi ，从根节点到叶节点的每一条路径定义了解空间中的一个元素。从根节点A 到叶节点H 的路径定义了解x=[1, 1, 1]。根据w 和c 的值，从根到叶的路径中的一些解或全部解可能是不可行的。
一旦定义了解空间的组织方法，这个空间即可按深度优先的方法从开始节点进行搜索。在迷宫老鼠问题中，开始节点为入口节点(1, 1)；在0/1背包问题中，开始节点为根节点A。开始节点既是一个活节点又是一个E-节点（expansionnode）。从E-节点可移动到一个新节点。如果能从当前的E-节点移动到一个新节点，那么这个新节点将变成一个活节点和新的E-节点，旧的E-节点仍是一个活节点。如果不能移到一个新节点，当前的E-节点就“死”了（即不再是一个活节点），那么便只能返回到最近被考察的活节点（回溯），这个活节点变成了新的E-节点。当我们已经找到了答案或者回溯尽了所有的活节点时，搜索
例4-1[迷宫老鼠]考察图16-3a 的矩阵中给出的3×3的“迷宫老鼠”问题。我们将利用图
16-1给出的解空间图来搜索迷宫。
从迷宫的入口到出口的每一条路径都与图16-1中从(1, 1)到(3, 3)的一条路径相对应。然而，图16-1中有些从(1, 1)到(3, 3)的路径却不是迷宫中从入口到出口的路径。搜索从点(1, 1)开始，该点是目前唯一的活节点，它也是一个E-节点。为避免再次走过这个位置，置m a z e(1, 1)为1。从这个位置，能移动到(1, 2)或(2,
1)两个位置。对于本例，两种移动都是可行的，因为在每一个位置都有一个值0。假定选择移动到(1, 2)，ma z e(1, 2)被置为1以避免再次经过该点。迷宫当前状态如图16-3b 所示。这时有两个活节点(1,1)(1,2)。(1, 2)成为E-节点。
在图16-1中从当前E-节点开始有3个可能的移动，其中两个是不可行的，因为迷宫在这
些位置上的值为1。唯一可行的移动是(1, 3)。移动到这个位置，并置m a z e(1, 3)为1以避免再次经过该点，此时迷宫状态为16-3c。图16-1中，从(1, 3)出发有两个可能的移动，但没有一个是可行的。所以E-节点(1, 3)死亡，回溯到最近被检查的活节点(1, 2)。在这个位置也没有可行的移动，故这个节点也死亡了。唯一留下的活节点是(1, 1)。这个节点再次变为E-节点，它可移动到(2, 1)。现在活节点为(1, 1)，(2, 1)。继续下去，能到达点(3, 3)。此时，活节点表为(1, 1)，(2, 1)，(3, 1)，(3, 2)，(3, 3)，这即是到达出口的路径。
程序5-13是一个在迷宫中寻找路径的回溯算法。
贪心算法
一、算法思想
贪心法的基本思路：
——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围。
实现该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；
二、例题分析
1、[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品
E
重量
价值
5A F 35101040B G [1**********]04C D 30503
分析：
目标函数：∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi
（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占空间最小的物品装入是否能得到最优解？
（3）每次选取单位容量价值最大的物品，成为解本题的策略。
源程序
2、[单源最短路径]一个有向图G，它的每条边都有一个非负的权值c[i,j]，“路径长度”就是所经过的所有边的权值之和。对于源点需要找出从源点出发到达其他所有结点的最短路径。
E.Dijkstra 发明的贪婪算法可以解决最短路径问题。算法的主要思想是：分步求出最短路径，每一步产生一个到达新目的顶点的最短路径。下一步所能达到的目的顶点通过如下贪婪准则选取：在未产生最短路径的顶点中，选择路径最短的目的顶点。
设置顶点集合S 并不断作贪心选择来扩充这个集合。当且仅当顶点到该顶点的最短路径已知时该顶点属于集合S。初始时S 中只含源。
设u 为G 中一顶点，我们把从源点到u 且中间仅经过集合S 中的顶点的路称为从源到u 特殊
路径，并把这个特殊路径记录下来（例如程序中的dist[i，j]）。
每次从V-S 选出具有最短特殊路径长度的顶点u，将u 添加到S 中，同时对特殊路径长度
进行必要的修改。一旦V=S，就得到从源到其他所有顶点的最短路径，也就得到问题的解。
Dijkstra.pas
3、[机器调度]现有N 项任务和无限多台机器。任务可以在机器上处理。每件任务开始时间和完成时间有下表：
任务
e a f b g c d
开始(si)
9
完成(fi)
[**************]
在可行分配中每台机器在任何时刻最多处理一个任务。最优分配是指使用的机器最少的可行分配方案。请就本题给出的条件，求出最优分配。
三、练习题：
已知5个城市之间有班机传递邮件，目的是为了寻找一条耗油量较少的飞行路线。5个城市的联系网络如图所示。图中编号的结点表示城市，两个城市之间的连线上的值表示班机沿该航线已行的耗油量，并假定从城市i 到j 和城市j 到i 之间的耗油量是相同的。分析：
1. 运用贪心思想：
在每一步前进的选择上，选取相对当前城市耗油量最小的航线；
2. 图解：若从1出发，有图：
总耗油量=141-2-5-3-4-1
但若路线改为：1-5-3-4-2-1，则总耗油量=13
所以，这样的贪心法并不能得出最佳解。
3. 改善方案：
从所有城市出发的信心过程，求最优的。
编程：
1. 数据结构：
城市联系网络图的描述(图的邻接矩阵的描述)：
const
c=array[1..5,1..5]of integer=((0,1,2,7,5),
(1,0,4,4,3),
(2,4,0,1,2),
(7,4,1,0,3));
2. 贪心过程：
begin
初始化所有城市的算途径标志；
设置出发城市V；
for i:=1to n-1do {n-1个城市}
begin
s:=从V 至所有未曾到过的城市的边集中耗油量最少的那个城市；
累加耗油量；
V:=s；
设V 城市的访问标志；
end;
最后一个城市返回第一个城市，累加耗油量；
end;
3. 主过程：实现改善方案
begin
for i:=1to n do
begin
cost1:=maxint;{初始化}
调用贪心过程，返回本次搜索耗油量cost；
if cost
end;
输出；
end.
type
dim1=array[0..11]of integer;
const
c:array[1..5,1..5]of integer=((0,1,2,7,5),
n=5;
p=5;
var
tour:dim1;
best:dim1;
visit:array[1..n]of 0..1; (1,0,4,4,3),(2,4,0,1,2),(7,4,1,0,3),(5,3,2,3,0));
cost,cost1:integer;
i,j:integer;
procedure greedy1(g:integer;var tour:dim1;var cost:integer);
var
v,s,k:integer;
function findmin:integer;
var
i,len,s1:integer;
begin
len:=maxint;
for i:=1to n do
if (iv)and (visit[i]=0)and (c[v,i]
一、分支限界法：
分支限界法类似于回溯法，也是一种在问题的解空间树T 上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T 中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使用某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
由于求解目标不同，导致分支限界法与回溯法在解空间树T 上的搜索方式也不相同。回溯法
以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。
二、分支限界法的基本思想：
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。
三、选择下一扩展结点的不同方式：
从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法。最常见的有以下两种方式：
1、队列式(FIFO)分支限界法：队列式分支限界法将活结点表组织成一个队列，并按队列的先进先出原则选取下一个结点为当前扩展结点。
2、优先队列式分支限界法：优先队列式分支限界法将活结点表组织成一个优先队列，交按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。
四、习题：
1、0-1背包：n=3,w=[16,15,15],p=[45,25,25],c=30
2、单源最短路径：求从起点到终点的最短路径。
3、装载问题：有一批共n 个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i 的
重量为wi 且
。要求确定是否有一个合理的装载方案可将这n 个集装箱装上这
2艘轮船。如果有，找出一种装载方案。
4、布线问题：印刷电路板将布线区域划分成n X m 个方格如图a 所示。精确的电路布线问题
题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。
三、选择下一扩展结点的不同方式：
从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法。最常见的有以下两种方式：
1、队列式(FIFO)分支限界法：队列式分支限界法将活结点表组织成一个队列，并按队列的先进先出原则选取下一个结点为当前扩展结点。
2、优先队列式分支限界法：优先队列式分支限界法将活结点表组织成一个优先队列，交按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。
四、习题：
1、0-1背包：n=3,w=[16,15,15],p=[45,25,25],c=30
2、单源最短路径：求从起点到终点的最短路径。
3、装载问题：有一批共n 个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i 的重量为wi 且
。要求确定是否有一个合理的装载方案可将这n 个集装箱装上这2艘轮船。如果有，找出一种装载方案。
4、布线问题：印刷电路板将布线区域划分成n X m 个方格如图a 所示。精确的电路布线问题
要求确定连接方格a 的中点到方格b 的中点的最短布线方案。在布线时，电路只能沿直线或
直角布线，如图b 所示。为了避免线路相交，已布了线的方格做了封锁标记，其它线路不允
穿过被封锁的方格。
Dijkstra 算法：
这一算法可求得有向网格N=(V,A,W)中从一给定点v 1出发到N 中任一点的最短有向路及其长度。该算法在解决关键路线问题、背包问题、某些加工顺序、中国邮递员问题等问题很有效。算法过程如下：
（0）
给所有的点一临时标号1，然后以v 1为出发点，
U 1=0, U j =w 1j (2≤j ≤n ), T j =1(1≤j ≤n ), P ={1
Q ={2, 3, , n }。
（1）
在Q 中找k ，使得U k =min U j
}
{}(j ∈Q ). 置
}→Q
P ⋃{k }→P , Q \{k
若Q ≠∅, 进入下一步（2）；若Q =∅时，算法终止，此时U j (1≤j ≤n ) 即为
点v 1至v j 的距离，T j 表示最短路（v 1, v j ）中与v j 邻近的点v Tj 。
（2）对Q 中每一个j ，如果U k +w kj
U k +w kj →U j ,
然后返回步骤（1）。
k →T j
该算法至多经过n -1次循环必结束。
下面就具体实例编制了（在Matlab 中）程序。
例：已知v i 与v j 之间的有向路长度，求自点1到点6的最短有路。
v 1
v 1v 2v 3v 4v 5v 6
clear; M=1.0e8;
w=[05M 3M M
M 042M M M M 0243M M M 05M M M M M 02M M M M M 0];N=6;%共有n 个顶点n=N;
j=[23456];T=ones(1,n);P=[1];Q=j;
v 2
50
v 3∞
40
v 4
3220
v 5∞∞
450
v 6∞∞
3
∞∞∞∞∞
∞∞∞∞
∞∞∞
∞
20
∞∞
∞
U(1:n)=w(1,:);temp=1;
while(temp
for I=1:(n-1)xx(I)=U(Q(I)); end
for I=1:(n-1)
if U(Q(I))==min(xx);
k=Q(I);P=[P,k];end end
for I2=1:(n-1)
if Q(I2)==k
k2=I2;end end Q(k2)=[];
for I3=1:length(Q)
if U(k)+w(k,Q(I3))
U(Q(I3))=U(k)+w(k,Q(I3));T(Q(I3))=k;end end n=n-1;temp=temp+1;end
for temp=1:N
disp(['第1点到第',num2str(temp),'点的最短长度为：',blanks(4),num2str(U(temp)) ])disp(['第1点到第',num2str(temp),'点的最短路中其前一点的下标为：',blanks(4),num2str(T(temp)) ])
fprintf('\n')end