离散最优化模型课件

离散问题是整数规划、组合数学图论、网络流等许多学科讨论和研究的对象，这类问题在生产调度、交通控制、物流、管理科学和社会科学等有着广泛的用途。在我们历年的数模的竞赛中，离散问题是很重要的一个方面。如“锁具装箱”，“灾情巡视路线”等等，本身就是个典型的离散问题；也有的问题里包含着离散的子问题，如“车辆安排问题”，是个受到整数的约束的优化问题。近几年的“乘公交，看奥运”，“体能测试时间安排”，“地面搜索”,“NBA赛程的分析与评价”,“眼科病床的合理安排”,“会议筹备”等等都属于离散型问题。shumo华中农业大学李治因此，在准备数模竞赛的过程中，有必要认真的研究如何提高建立离散模型的质量。下面就离散优化问题，介绍一下常见模型、算法及如何进行算法分析等。shumo华中农业大学李治建立规划模型的要点与技巧一、准确理解题意二、选择适当的决策变量要点：

通过仔细读题，弄清楚我们最终要解决的问题是什么?是单目标问题还是多目标问题？已知条件有哪些？为了简化与解决问题，需要做哪些必要的基本假设？

需要优化的目标是由哪些因素决定的？适当引入决策变量来表示这些因素。shumo华中农业大学李治三、设法用决策变量表示目标函数四、仔细分析约束条件通常引入的决策变量有0-1变量，整数变量等。

在用决策变量表示目标函数时，有时需要引入中间变量，有时要利用取整函数、符号函数、绝对值函数等等。

决策变量满足的约束主要有两方面：一是自身应有的约束，如非负约束、取整约束等等；二是题目要求及客观实际的约束，这种约束又可分为“硬约束”与“软约束”。shumo华中农业大学李治一、多目标问题的妥协二、非线性规划的线性化三、复杂规划问题的拆分值得注意的技巧：有时可将复杂的问题分成一系列较为简单的子问题求解线性加权法；理想点法，极大极小法等有时通过引入人工变量可将非线性规划问题线性化shumo华中农业大学李治一常见离散优化模型涉及整数规划、0-1规划、组合优化和图论等：如竞赛中常涉及的有下料问题；指派问题、选址问题、装箱问题、背包问题、最短路问题、TSP（旅行商）问题等。离散优化研究那些含有有限个可行解的、日常生活中大量存在的问题，一个重要而普遍的应用领域就是考虑如何有效利用稀缺资源来提高生产力等。shumo华中农业大学李治例1现要做100套钢架,用长为2.9m、2.1m和1.5m的元钢各一根,已知原料长7.4m,问如何下料,使用的原材料最省?分析:下料方式：最省：1.所用刚架根数最少；2.余料最少下料问题离散优化模型shumo华中农业大学李治原料截成所需长度的根数下料方法ⅠⅡⅢⅣⅤⅥⅦⅧ所需根长2.9m211100002.1m021032101.5m10130234剩余料头0.10.30.901.10.20.81.4离散优化模型shumo华中农业大学李治离散优化模型写出模型后可以直接用LINGO求解shumo华中农业大学李治model:Title

钢管下料;

Min=0.1*x1+0.3*x2+0.9*x3+0*x4+1.1*x5+0.2*x6+0.8*x7+1.4*x8;2*x1+x2+x3+x4>100;2*x2+3*x3+3*x5+2*x6+x7>100;x1+x3+3*x4+

2*x6+3*x7+

4*x8>100;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);endshumo华中农业大学李治

例2

设有n件工作B1,B2,…Bn,分派给n人A1,A2,…An去做,每人只做一件工作且每件工作只派一个人去做,设Ai完成Bj的工时为cij,问应如何分派才能完成全部工作的总工时最少.每件工作只派1人每个人只做1件工作指派问题离散优化模型shumo华中农业大学李治如求6个人做6项工作的最优指派，收益情况如下表。指派问题人工作1工作2工作3工作4工作5工作61201516547217153312863912181630134128112719145—7102110326———61113shumo华中农业大学李治指派问题model:title指派问题;sets:flight/1..6/;assign(flight,flight):c,x;endsetsdata:c=20151654717153312869121816301312811271914-99710211032-99-99-9961113;enddata人工作1工作2工作3工作4工作5工作61201516547217153312863912181630134128112719145—7102110326———61113max=sum(assign:c*x);for(flight(i):sum(flight(j):x(i,j))=1;sum(flight(j):x(j,i))=1);for(assign:bin(x));endshumo华中农业大学李治选址问题离散优化模型shumo华中农业大学李治装箱问题(binpacking

problem)装箱问题在工业生产及日常生活中有广泛的用途，其应用在实际生活中无处不在，货物装运，服装裁剪，以及我们计算机科学中的存储分配、共享资源调度、文件存储都是装箱问题在实际应用中的体现。所以具有重要的研究价值。当你装一个箱子时，你会发现要使箱子尽可能装满不是一件很容易的事，你往往需要做些调整。从理论上讲，装箱问题是一个很难的组合优化问题，即使用计算机也是不容易解决的。离散优化模型shumo华中农业大学李治设有编号为1、…、n的n种物品，体积分别为v1、v2、…、vn。将这n种物品装到容量都为V的若干箱子里(更一般的装箱问题还可以要求容量不是相同的)。约定这n种物品的体积均不超过V，即对于1≤i≤n，有0＜vi≤V。不同的装箱方案所需要的箱子数目可能不同。成功装载是指能把所有物品都装入箱子。最优装载是指使用最少箱子的成功装载。

装箱问题的描述shumo华中农业大学李治装箱问题的数学表示如下(0-1规划模型)：s.t.yi=1表示箱子i装入物品，反之表示箱子i空着xij=1表示物品j装入箱子i

，反之表示物品j未放入箱子ishumo华中农业大学李治例4已知30个物品,其中6个长0.51m，6个长0.27m，6个长0.26m，余下12个长0.23m，箱子长为1m，问最少需多少个箱子才能把30个物品全部装进箱子。装箱问题的LINGO软件求解离散优化模型shumo华中农业大学李治model:sets:WP/w1..w30/:W;XZ/v1..v30/:Y;LINKS(WP,XZ):X;ENDSETSDATA:W=0.51,0.51,0.51,0.51,0.51,0.51,0.27,0.27,0.27,0.27,0.27,0.27,0.26,0.26,0.26,0.26,0.26,0.26,0.23,0.23,0.23,0.23,0.23,0.23,0.23,0.23,0.23,0.23,0.23,0.23;ENDDATAMIN=SUM(XZ(I):Y(I));C=1;!C是箱子长度;for(XZ:bin(y));!限制Y是0-1变量;for(LINKS:bin(X));!限制X是0-1变量;for(WP(I):sum(XZ(J):X(I,J))=1);!每个物品只能放入一个箱子;for(XZ(J):SUM(WP(I):W(I)*X(I,J))<=C*Y(J));!每个箱子内物品的总长度不超过箱子;end离散优化模型shumo华中农业大学李治装箱问题的分类 一维装箱问题更多的是带约束的装箱问题， 如二维装箱问题（条形装箱问题、剪裁 问题）、三维装箱问题、变容装箱问题、 有色装箱问题、对偶装箱问题等。 在竞赛中应注意区分和鉴别离散优化模型shumo华中农业大学李治有N件物品和一个容量为W的背包。第j件物品的价值是，体积是。求将哪些物品装入背包可在满足背包容量允许的前提下使价值总和最大。背包问题在经济管理、资源分配、投资决策、装载设计等领域有着重要的应用价值。一维0/1背包问题shumo华中农业大学李治设为二进制变量，如果物品j被放入背包，则，否则。背包问题的数学模型描述如下：

离散优化模型shumo华中农业大学李治例5：“超市大赢家”提供了50种商品作为奖品供中奖顾客选择,车的容量为1000dm3,奖品i占用的空间为widm3,价值为vi

元,具体的数据如下:vi={220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1}wi={80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1}。离散优化模型shumo华中农业大学李治model:sets:goods/w1..w50/:w,c,x;

endsetsdata:c=220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1;w=80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1;capacity=1000;!容量;enddatamax=sum(goods(j):c(j)*x(j));for(goods:bin(x));!限制x是0-1变量;sum(goods(J):w(j)*x(j))<capacity;p=sum(goods(J):x(j));!所装物品总件数;z=sum(goods(J):w(j)*x(j));!所装物品总体积;endshumo华中农业大学李治最短路问题与TSP问题这两个问题是图论中与优化有关的常见问题，即使不专门考察，在竞赛中经常也会以不同形式涉及。如00年钢管运输与98年灾情巡视07年“乘公交、看奥运”shumo华中农业大学李治

设一个带权的图G=(V,E)表示一交通运输网络，以图的各个顶点V代表一些城市，图的各条边E表示城市之间的交通运输路线，每条边的权值则表示此路线的长度或表示沿此路线运输所需花费的时间或运费等。运输路线往往是有方向性的，例如汽车运输有时会遇到单行路,而且不同的方向所花费的时间或尺价可能不同，例如汽车的上山和下山、水路的顺水和逆水花费的时间或代价就不相同，所以交通运输网络一般是有向图，所谓最短路径问题指的是：如果从图中某顶点出发(此点称为源点),经图的边到达另一顶点（称之为目的点）的路径不止一条，如何找到一条路径使沿此路径上各边的权值之和为最小。最短路问题(Shortestpath)shumo华中农业大学李治例6在公路网中，司机希望找到一条从城市S到T的最短路，如何选择行使路线，使所经过的路程最短。单源最短路问题

shumo华中农业大学李治model:SETS:CITIES/S,A1,A2,A3,B1,B2,C1,C2,T/:L;!属性L(i)表示城市S到城市i的最优行驶路线的路长;ROADS(CITIES,CITIES)/

!派生集合ROADS表示的是网络中的道路（弧）;S,A1S,A2S,A3 !由于并非所有城市间都有道路直接连接，所以将弧具体列出;A1,B1A1,B2A2,B1A2,B2A3,B1A3,B2B1,C1B1,C2B2,C1B2,C2C1,TC2,T/:D; !属性D(i,j)是城市i到j的直接距离（已知）;ENDSETSDATA:D=633658674678956;L=0,,,,,,,,;

!因为L(S)=0;ENDDATA

FOR(CITIES(i)|i#GT#index(S):

!这行中"index(S)"可以直接写成"1";L(i)=MIN(ROADS(j,i):L(j)+D(j,i)););!这就是前面写出的最短路关系式;end定义稀疏集合方法：枚举法CITIES（i）中的i指元素在集合中的位置顺序，index(S)即:index(CITIES，S),S在CITIES中的索引值。没有目标函数是允许的shumo华中农业大学李治旅行推销员问题（TravelSalesmanProblemorTSP问题）

设有A、B、C、D、E五个城市(n=5)之间路程如下距离矩阵W给出。假设一个推销员想从城市A出发，问是否存在一个行程安排，使得他能不重复地遍历所有城市后回到这个城市，而且所走路程最少。shumo华中农业大学李治哈密尔顿回路问题这样找从一点出发不重复地走过所有的结点，最后又回到原出发点的路径的问题，在图论中称为“哈密尔顿回路问题”“哈密尔顿回路问题”与“欧拉回路问题”的不同点“哈密尔顿回路问题”是访问每个结点一次，而“欧拉回路问题”是访问每条边一次。对图G是否存在“欧拉回路”，欧拉已给出充分必要条件，而对图G是否存在“哈密尔顿回路”至今仍未找到满足该问题的充分必要条件。欧拉回路问题也称为“中国邮递员问题”。中国数学家管梅谷于1960年首先研究并给出算法。shumo华中农业大学李治TSP问题的数学表示如下（0-1规划模型）：s.t.源至少有一条边连接到其它点xij决策变量，xij=1表示连接除源以外，每个点只有一条边进入shumo华中农业大学李治增加一个标号的水平变量（level）来构造所选的边不构成子回路的约束条件（即只能有整体回路），这是TSP问题的一个充分条件。任何含有子回路的路线都必不满足该约束条件（不管ui）如何取值；全体不含子回路的整体回路都可以满足该约束条件（只要ui取适当值）shumo华中农业大学李治证明：任何含有子回路的路线都必不满足该约束条件（不管ui）如何取值；全体不含子回路的整体回路都可以满足该约束条件（只要ui取适当值）反证：假设存在子回路，则至少有两个子回路，必然至少有一个子回路不含源点1，例如子回路4-5-6-4，把下标代入，有把这三个不等式加起来得到这是矛盾的，故假设不成立，而对整体回路，而附加约束中j≥2,不包含起点1，故不会发生矛盾。对整体回路，只要level(i)取适当值，都可以满足该约束。shumo华中农业大学李治例7已知六个城市之间的距离矩阵，求从1出发回到1的TSP路线。D=070245484223961196

702032410932136764

454324011372180798

84210931137016161857

239621362180161602900

1196764798185729000;shumo华中农业大学李治model:sets:city/1..6/:u;link(city,city):dist,x;endsetsdata:dist=070245484223961196702032410932136764454324011372180798842109311370161618572396213621801616029001196764798185729000;enddatan=size(city);min=sum(link:dist*x);for(city(k):sum(city(i)|i#ne#k:x(i,k))=1;sum(city(j)|j#ne#k:x(k,j))=1);for(city(i):for(city(j)|j#gt#1#and#i#ne#j:u(i)-u(j)+n*x(i,j)<=n-1));for(link:bin(x));endshumo华中农业大学李治问题的分析蓝色代表预计选Mevo的人数，红色代表各街区总人数例8：（08年华中联赛）选区方案shumo华中农业大学李治shumo华中农业大学李治shumo华中农业大学李治将首都的地图看作一张无向图，若街区是相邻街区，该街区间有边相连。得到其邻接矩阵W：11111111111111111111111111111111111111111111111111shumo华中农业大学李治见程序shumo华中农业大学李治二离散最优化问题的求解虽然理论上讲这些离散优化问题最优解可以通过枚举得到，但事实是不可能的，因为对于实际问题，可行解数量可能特别巨大。许多离散优化问题是经典的NP难解问题，这意味着该类问题往往不存在在多项式时间内求得精确解的算法（如果P≠NP）,因此对离散优化问题的算法的研究指的往往是对其近似算法的研究，所谓近似算法即该算法可以求得与精确解接近的结果,但不一定得到精确解。shumo华中农业大学李治离散最优化问题的求解1、回溯法2、贪婪算法3、分支定界4、动态规划回溯法：一般当问题规模较小时用回溯法能有效求解,但当问题规模较大时其求解时间耗费非常巨大。离散最优化问题的求解shumo华中农业大学李治以装箱问题为例，若将n种物品的集合分划成n个或小于n个物品的所有子集全部穷举出来，最优解当然可以找到。但所有可能划分的总数太大。对适当大的n，找出所有可能的划分要花费的时间是无法承受的。为此，可以采用非常简单的近似算法，即贪婪法。该算法依次将物品放到它第一个能放进去的箱子中，该算法虽不能保证找到最优解，但还是能找到非常好的解。2、贪婪算法（贪心法）shumo华中农业大学李治贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况。贪婪算法并不能保证最优，然而，却是一种具有直觉的倾向且一般情况下结果总是非常接近最优值。它利用的规则就是在实际环境中人工所采用的规则。算法并不保证得到最优结果，但通常所得结果与最优解相差无几，这种算法也称为启发式方法（heuristics)。贪婪算法shumo华中农业大学李治例如平时购物找钱时，为使找回的零钱的硬币数最少，不考虑找零钱的所有各种发表方案，而是从最大面值的币种开始，按递减的顺序考虑各币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种较小面值的币种。这就是在使用贪婪法。这种方法在这里总是最优，是因为银行对其发行的硬币种类和硬币面值的巧妙安排。如只有面值分别为1、5和11单位的硬币，而希望找回总额为15单位的硬币。按贪婪算法，应找1个11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币。但最优的解应是3个5单位面值的硬币。

贪婪算法shumo华中农业大学李治在贪婪算法（greedymethod）中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则（greedycriterion）。

贪婪算法shumo华中农业大学李治装箱问题的求解——贪婪算法

NF(NextFit－下次适应)算法：按照物体给定的顺序装箱：把物品wi放到它第一个能放进去的箱子中。Bj是具有最大下标的使用过的箱子，若wi的长度不大于Bj的剩余长度，则把wi放入Bj，否则把wi放入一个新的箱子Bj+1，且Bj在以后的装箱中不再使用。最后循环shumo华中农业大学李治FF(First

Fit－首次适应)算法：按照物体给定的顺序装箱：把物品wi放到第一个箱子中。B1B2…Bj是当前已经使用过的箱子，在这些箱子中找一个长度不小于wi且下标最小的箱子,将放入wi，如果不存在这样的箱子,则另开一个新箱子Bj+1,将wi放入Bj+1中。装箱问题的求解——贪婪算法

shumo华中农业大学李治在线算法：如果一个近似装箱算法在执行过程中，每当一个物品到达时，就立刻决定把该物品放入哪个箱子中，而不管后序物品如何，这种算法就被称为在线算法。下次适应算法、首次适应算法等都是在线算法，其时间复杂度都为O(n)。以上算法都称为在线适应算法，适应算法的特点是当处理当前物品，如果有已经打开的箱子中能够放下这个物品，则不打开新的箱子。装箱问题的求解——贪婪算法

shumo华中农业大学李治不失一般性，对n件物品的体积按从大到小排好序，即有v1≥v2≥…≥vn，然后按排序结果对物品重新编号即可。降序首次适应算法（FFD）:先将物体按长度从大到小排序,然后按FF算法对物体装箱.离线算法：如果算法在开始装箱之前，已经预先得到了所有物品的信息而一次性的确定装箱策略，这种算法就被称为离线算法。降序首次适应算法和降序最佳适应算法是两个重要的离线算法。这里的降序首次适应算法就是一种贪婪算法。装箱问题的求解——贪婪算法

shumo华中农业大学李治FFD算法：{输入箱子的容积；

输入物品种数n；

按体积从大到小顺序，输入各物品的体积；

预置已用箱子为空；

预置已用箱子计数器box_count为0；

for(i=0;i<n;i++){从已用的第一只箱子开始顺序寻找能放入物品i的箱子j；

if（已用箱子都不能再放物品i）

{另用一个箱子，并将物品i放入该箱子；

box_count++；}

else

将物品i放入箱子j；

}}装箱问题的求解——贪婪算法

shumo华中农业大学李治例9：利用FFD算法完成下题:设有6种物品，它们的体积分别为：60、45、35、20、20和20单位体积，箱子的容积为100个单位体积。装箱问题的求解——贪婪算法

shumo华中农业大学李治例10:多处理器调度问题

设有n个独立的作业{1,2,…,n}，由m台相同的机器进行加工处理。作业i所需的处理时间为ti。现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的子作业。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。[分析]这个问题可以看成装箱问题，也是NP完全问题。对于这一类问题，用贪婪选择策略有时可以设计出较好的近似算法。采用最长处理时间作业优先的贪婪选择策略可以设计出解多处理器调度问题的较好的近似算法。按此策略，当n≤m时，我们只要将机器i的[0,ti]时间区间分配给作业i即可。当n＞m时，我们首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理器。装箱问题的求解——贪婪算法

shumo华中农业大学李治

例如，设7个独立作业{1,2,3,4,5,6,7}由3台机器M1,M2,和M3来加工处理。各作业所需的处理时间分别为{2,14,4,16,6,5,3}。按贪婪算法产生的作业调度如图所示，所需的加工时间为17。当n＞m时，因此算法所需的计算时间复杂度为O(nlogn)。装箱问题的求解——贪婪算法

shumo华中农业大学李治例如,一个软件开发小组要在规定时间内完成一项任务,系统分析员把任务划分成各个子任务.由于每个子任务要求的花费程序员的时间不同,不合理的分派将导致各程序员贻误工期.这就是一个多处理器调度问题的应用。装箱问题的求解——贪婪算法

shumo华中农业大学李治续例5：问题自身的特性决定了该问题运用贪婪算法可以得到最优解或较优解。通常这里有三种贪婪准则:1、价值贪婪准则：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去，这种策略不能保证得到最优解。2、质量贪婪准则：从剩下的物品中选择可装入背包的重量最小的物品，在一般情况下也不一定能得到最优解。3、价值密度贪婪准则：从剩余物品中选择可装入包的cj/wj值最大的物品，即按cj/wj非递增的次序装入物品，只要正被考虑的物品装得进就装入背包，这种策略可能会得到最优解。背包问题的求解——贪婪算法shumo华中农业大学李治(1)输入物品个数n,背包的容量limitW,每个物品的重量wj和价值cj。(2)对物品按单位价值从大到小排序。(3)将排序后的物品依次装入背包。对于当前物品j,若背包剩余可装重量大于或等于wj,则将物品j装入背包,继续考虑下一个物品j+1,重复步骤3,否则得到问题的解,输出。算法流程注：1、算法主要的运算时间是用来对n个元素进行排序，故其复杂性是O（nlogn）。2、对于解决0/1背包问题，总得来讲，动态规划比贪婪算法要好些，可以得到最优解。背包问题的求解——贪婪算法shumo华中农业大学李治一维0/1背包问题方法的改进：设有n=8个体积分别为54，45，43，29，23，21，14，1的物体和一个容积为C=110的背包，问选择哪几个物体装入背包可以使其装的最满。如直接用贪婪算法，将物体由大到小顺次装入背包，到装不下时再逐个试装更小的一些，直至试到最小的一个或装满为止。按此处所给数据，先装入54和45两个，容积尚余11，最后只能再装入体积为1的一个，总体积达到100，并不算太满。此方法的好处是节省时间，主要的运算时间是用来对n个元素进行排序。背包问题的求解——贪婪算法shumo华中农业大学李治如果对上述算法作一些改进，可得到更好的结果。先从n个物体中试着取j个总体积不超过C的装入背包，剩下的(n-j)个物体则利用贪婪算法尽量往里装。此j值从零开始逐渐增加，反复进行试探，直至j达到某预先给定的常数k(0<k<n)，最后从这些结果中取其最好的一个。如果在试探中能得到一个完全装满的方案，则此过程就可提前结束。因为从n个物体中取出j个共有种方案，此值随着j的增加而增加较快，但可以证明此改进算法的复杂性为O（knk+1）,因k是常数，故仍为多项式界的算法。背包问题的求解——贪婪算法shumo华中农业大学李治按本例所给数值，取j=0时，因就是前述普通贪婪算法，已经得到100的结果；取j=1时，共有8种方案，当用29或23先装入时，可得到54+29+23+1=107的更好结果；取j=2时，共有28种方案，其中有能将背包完全装满的结果（43+23+29+14+1=110）。故知此问题当取k≥2时就可得到最优解。背包问题的求解——贪婪算法shumo华中农业大学李治由于是5个城市，环绕一圈为5条边，贪婪方法求解此问题的过程是从最小边开始，依此从小到大取边加入到回路边集中，但在将1条边加入时不能使1顶点的度数超过3，也不能形成小回路。

旅行商问题的求解——贪婪算法将城市间的距离从小到大排列有：d24(1),d13(2),d15(2),d25(3),d45(6),d35(9),d34(9),d12(14),d14(16),d23(25)。shumo华中农业大学李治d24(1)；d24(1)+d13(2)；d24(1)+d13(2)+d15(2)；d24(1)+d13(2)+d15(2)+d25(3)；d24(1)+d13(2)+d15(2)+d25(3)+[d45(6)]；（下标中5出现了3次,顶点5有三条边相连,d45(6)放弃）d24(1)+d13(2)+d15(2)+d25(3)+[d35(9)]；（下标中5出现了3次,顶点5有三条边相连,d34(6)放弃）d24(1)+d13(2)+d15(2)+d25(3)+d34(9)。得到一条回路：v1→v3→v4→v2→v5→v1是最佳的回路。旅行商问题的求解——贪婪算法shumo华中农业大学李治例11

设有六个城市，其坐标分别为a(0,0),b:(4,3),c:(1,7),d:(15,7),e(15,4),f:(18,0)。如下图所示：旅行商问题的求解——贪婪算法shumo华中农业大学李治6座城市间的距离矩阵为：旅行商问题的求解——贪婪算法shumo华中农业大学李治

求解：先将任两城市间的连线距离按从小到大的次序排列，然后从中逐个选择。但有两种情况的连线应舍弃：

(1)使任一城市的度数（连线数）超过2的连线必须舍弃；

(2)在得到经过所有点的回路前就形成小回路的连线必须舍弃。距离按从小到大的次序排列:Dde(3),Dab(5),Dbc(5),Def(5),Dae(7.07),Ddf(7.62),Dbe(11.01),Dbd(11.7),Ded(14),Dbf(14.32),Dce(14.32),Dae(15.52),Dad(16.55),Daf(18.38),Def(18.38)旅行商问题的求解——贪婪算法shumo华中农业大学李治

按贪婪算法原则，其选择过程如下：Dde；Dde+Dab；Dde+Dab+Dbc；Dde+Dab+Dbc+Def；Dde+Dab+Dbc+Def+[Dae]；(形成小回路，舍弃)Dde+Dab+Dbc+Def+[Ddf]；(形成小回路，舍弃)Dde+Dab+Dbc+Def+[Dbe]；(b顶点度数超过2，舍弃)Dde+Dab+Dbc+Def+[Dbd]；(b顶点度数超过2，舍弃)Dde+Dab+Dbc+Def+Dcd；Dde+Dab+Dbc+Def+Dcd+[Dbf]；(b顶点度数超过2，舍弃)Dde+Dab+Dbc+Def+Dcd+[Dce]；(c、e顶点度数超过2，舍弃)Dde+Dab+Dbc+Def+Dcd+[Dae]；(e顶点度数超过2，舍弃)Dde+Dab+Dbc+Def+Dcd+[Dae]；(e顶点度数超过2，舍弃)Dde+Dab+Dbc+Def+Dcd+[Dad]；(d顶点度数超过2，舍弃)Dde+Dab+Dbc+Def+Dcd+Daf；得到1条回路shumo华中农业大学李治最后得到的回路如图（a）的结果，总长度为50。旅行商问题的求解——贪婪算法shumo华中农业大学李治不过，这不是此问题的最优解，此问题的最优解为下图所示的路径(可以用分枝定界等方法求得)，总长度为48.39。用贪婪方法得到的结果同最优解相比只多了3.3%。旅行商问题的求解——贪婪算法shumo华中农业大学李治背包问题的求解——分支定界例12假定我们有四种物品要装包，限重10，各样东西价值为c={1,3,5,9},单重为w={2,3,4,7}。我们用分支定界法求解背包问题，首先对物品按单位价值从大到小编号

，使得模型为：shumo华中农业大学李治背包问题的搜索树是这样定义的，第i层的结点到它的子结点的弧表示第i种物品装包的数量，一个子结点表示一种选择。此问题的树中，第一层有两个分支，第二、三、四层分别有三、四、六个分支。x1={0,1},x2={0,1,2},x3={0,1,2,3},x4={0,1,2,3,4,5}重量和值标在相应的结点上。如果a）它的重量超过限重，或b）它的值不大于当前最好的可行值，那么，停止从这个结点向下搜索，砍去这条分支；回溯到后继一个结点。结点(x1,x2,…,xk)的重量是，而它的值为shumo华中农业大学李治shumo华中农业大学李治动态规划求下面加权有向图中从A到G的最短路：shumo华中农业大学李治最优化原理一个最优策略具有这样的性质，即不论初始状态与初始策略如何，对于先前决策所造成的状态而言，下余所有决策必构成最优决策。shumo华中农业大学李治最短路径的图上计算AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766583338422213335526643(18)(16)(13)(13)(10)(9)(12)(7)(6)(8)(7)(5)(9)(4)(3)shumo华中农业大学李治解：(1)、分支定界法(2)、贪婪法(3)、DP方法比较15比较47次48

加法138次AB2C4D3E2F2G21加法28丰富了计算结果shumo华中农业大学李治基本概念与基本方程(1)阶段：k＝1，2，…，6n=6(2)状态变量：Sk－第k阶段所处的位置状态集合如S2:(B1,B2)(3)决策变量uk

：在第k段Sk状态时决定选取的下一段的某点(4)状态转移方程：Sk＋1

＝ukshumo华中农业大学李治(6)阶段效益：

d(Sk，uk)为第k段，采取策略uk到下一状态的距离(5)最优指标函数：fk(Sk)：第k段，在Sk状态时到终点G的最短距离shumo华中农业大学李治k＝6，f6(F1)＝4f6(F2)＝3k＝5d(E1F1)+f6(F1)f5(E1)＝mind(E1F2)+f6(F2)3+4＝min=7u5(E1)=F1

5+3shumo华中农业大学李治同理f5(E2)＝5u5(E2)＝F2

f5(E3)＝9u5(E3)＝F2k＝4d(D1E1)+f5(E1)f4(D1)＝mind(D1E2)+f5(E2)2+7＝min=7u4(D1)=E2

2+5shumo华中农业大学李治同理f4(D2)＝6u4(D2)＝E2

f4(D3)＝8u4(D3)＝E2K=3……shumo华中农业大学李治k＝1d(A

B1)+f2(B1)f1(A)＝mind(A

B2)+f2(B2)5+13＝min=18u1(A)=B1

3+16shumo华中农业大学李治(三)基本方程fk(Sk)＝min{d(Skuk)+fk+1(Sk+1)}k=6,…1f7(S7)＝0或fk(Sk)＝min{d(Skuk)+fk+1(Sk+1)}k=5,…1f6(S6)＝min{d(S6u6)}shumo华中农业大学李治Dijkstra于1959年提出了解决最短路问题的一般算法，此算法可按边的权值由小到大的次序，通过贪婪选择，逐步得到由给定源点到图的其余各点间的最短路径。其基本作法是，设置一个顶点集合S，一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设vi是G的某一个顶点，我们把从源到vi且中间只经过S中顶点的路称为从源到vi的路径，并用数组dist来记录当前S中每个顶点所对应的最短路径长度。最短路问题的求解shumo华中农业大学李治①赋初值.给v0以P标号，记P(v0)＝0，其余各点vi以T标号,T(vi)＝a(v0

,vi)，并将vi的父点设为v0，记录u=v0,S={u},转向②.②更新所有的T标号和其父点.

v∈V\S,如果T(v)>P(u)+a(u,v),则令T(v)=P(u)+a(u,v),并重新记录v的父点为u,转向③.③给出下一个P标号并更新记录u和S.设T(v*

)=min{T(v),v∈V\S},给v*以P标号,P(v*)=T(v*

),重新记录u=v*,S=S+{u},转向④.④终止判断.若V\S非空,转向②;否则终止.求赋权图中单源最短路的Dijkstra算法：shumo华中农业大学李治Dijkstra算法的几点说明：①算法具有终止性.对一个p,q图G来说,只要p步迭代,就可以求出v0到其它各点的最短路.若只求