《图论中几个典型问题的求解(精品).ppt》由会员分享，可在线阅读，更多相关《图论中几个典型问题的求解(精品).ppt（161页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图论中几个典型问题的求解1 图的基本概念图图是是一一种种直直观观形形象象地地描描述述已已知知信信息息的的方方式式，它它使使事事物物之之间间的的关关系系简简洁洁明明了了，是是分分析析问问题题的的有有用用工工具具，很很多多实实际际问问题题可可以以用用图来描述。图来描述。一、一、图的定义图的定义 图图论论是是以以图图为为研研究究对对象象的的数数学学分分支支，在在图图论论中中，图由一些点和点之间的连线所组成图由一些点和点之间的连线所组成 称称图图中中的的点点为为顶顶点点（节节点点），称称连连接接顶顶点点的的没没有方向的线段为边，称有方向的线段为弧有方向的线段为边，称有方向的线段为弧用用V=v1,v2,
2、表表示示全全体体顶顶点点的的集集合合，用用 E=e1,e2,表表示示全全体体边边的的集集合合，如如果果对对于于E中中的的任任一一条条边边ek，在在V中中都都有有一一对对顶顶点点(vi,vj)和和它它对对应应，则则称称由由V和和E组组成成的的集集体体为为一一个个图图，记记为为G=V,E，简写为，简写为G二、基本概念二、基本概念 点点与与边边相相连连接接称称为为关关联联，与与边边e关关联联的的顶顶点点称称为为该该边边的的端端点点，与与同同一一条条边边关关联联的的两两个个顶顶点点称称为为相相邻邻顶顶点点，与与同同一一个个顶顶点点关关联联的的边边称称为为相相邻邻边边具具有有相相同同顶顶点点的的边边称称
3、为为平平行行边边，两两个个端端点点重重合合的的边边称称为为环环所所有有线线段段都都没没有有方方向向的的图图称称为为无无向向图图，所所有有线线段段都都有有方方向向的的图图称称为为有有向向图图，既既有有边边也也有有弧弧的的图图称称为为混混合合图图在在无无向向图图中中，没没有有环环和和平平行行边边的的图图称称为为简简单单图图，任任意意两两个个顶顶点点之之间间都都有有一一条条边边相相连连的的简简单单图图称称为为完完全全图图任任意意两两个个顶顶点点之之间间有且只有一条弧相连的有向图称为有且只有一条弧相连的有向图称为竞赛图竞赛图在在无无向向图图中中与与顶顶点点v关关联联的的边边的的数数目目（环环算算两两次
4、次）称称为为该该顶顶点点的的度度（或或次次数数），记记为为d(v)。度度为为奇奇数数的的顶顶点点叫叫做做奇奇点点，度度为为偶偶数数的的顶顶点点叫叫做做偶偶点点。在在有有向向图图中中，从从顶顶点点v引引出出的的边边的的数数目目称称为为该该顶顶点点的的出出度度，记记为为d+(v)，从从顶顶点点v引引入入的的边边的的数数目目称称为为该该顶顶点点的的入入度度，记记为为d-(v)，而而d(v)d+(v)+d-(v)称为称为v的的次数次数。在在图图中中，两两个个顶顶点点u和和v之之间间由由顶顶点点和和边边构构成成的的交交错错序序列列（使使u和和v相相通通）称称为为链链（通通道道），没没有有重重复复边边的的
5、通通道道称称为为迹迹，起起点点与与终终点点重重合合的的通通道道称称为为闭闭通通道道，不不重重合合的的称称为为开开通通道道，没没有有重重复复顶顶点点（必必然然边边也也不不重重复复）的的开开通通道道称称为为路路，起起点点与与终终点点重重合合的的路路称称为为圈圈（回回路路）包包含含奇奇数数个个顶顶点点（或或边边）的的圈圈称称为为奇奇圈圈，包包含含偶偶数数个个顶顶点点（或或边边）的的圈圈称称为为偶偶圈圈。如如果果顶顶点点u和和v之之间间存存在在一一条条路路，则则称称u和和v是是连连通通的的，任任意意两两个个顶顶点点都都连连通通的的图图称称为为连连通通图图无无圈圈的的连连通通图图称称为为树树，如如果果一
6、一棵棵树树T包含了图包含了图G的所有顶点，称的所有顶点，称T为为G的的生成树生成树如如果果图图G的的每每条条边边e都都对对应应一一个个实实数数C(e)，称称C(e)为为该该边边e的的权权，称称图图G为为赋赋权权图图通通常常称称赋赋权权的有向图为网络的有向图为网络图图中中边边e6和和e7是是平平行行边边，e9是是环环，顶顶点点v4是是悬悬挂点，边挂点，边e4是悬挂边是悬挂边2 最短路问题最最短短路路问问题题是是图图论论应应用用的的基基础础，很很多多实实际际问问题题，如如线线路路的的布布设设、运运输输规规划划、运运输输网网络络最最小小费费用用流流等等问问题题，都都可可以以通通过过建建立立最最短短路
7、路模模型型来来求求解解。有有些些有有深深度度的的图图与与网网络络优优化化问问题题，如如旅旅行行售售货货商商、中中国国邮邮递递员员等等问问题题，需需要要在在首首先先求求出出任任意意两两点点之之间最短路的基础上解决。间最短路的基础上解决。一、最短路的概念一、最短路的概念给给定定一一个个连连通通的的赋赋权权图图G=V,E，设设R是是连连接接节节点点vi和和vj的的一一条条路路，该该路路的的权权定定义义为为路路中中所所有有各各边边权权之之和和，如如果果路路R在在所所有有连连接接节节点点vi和和vj的的路路中权最小，则称它为中权最小，则称它为vi和和vj间的最短路。间的最短路。二、任意两点之间的最短路二
8、、任意两点之间的最短路(Floyd算法算法)Floyd算算法法利利用用距距离离矩矩阵阵进进行行迭迭代代运运算算，可可以以一一次次性性地地求求出出任任意意两两点点之之间间的的最最短短路路，该该方方法法的的思思路路有有创创意意，计计算算量量小小，编编程程较较简简单单，又又称称矩矩阵阵求解法。求解法。1算法原理算法原理 设设A=aijmn n是是图图的的权权矩矩阵阵（也也称称带带权权邻邻接接矩矩阵阵），其其中中aij是是图图上上连连接接顶顶点点i和和j的的边边的的权权，如如果果两两顶顶点点之之间间没没有有直直接接相相连连的的边边（即即两两顶顶点点不不相相邻），则邻），则aij=。令令矩矩阵阵D(0)
9、=A，作作为为迭迭代代的的初初始始矩矩阵阵，从从它它出出发发按按照照一一定定规规则则求求D(1)，又又由由D(1)按按照照类类似似的的规规则则求求D(2)，依依此此类类推推进进行行迭迭代代直直至至求求出出D(n)，设设矩阵矩阵D(m)的元素为的元素为dij(m)，迭代规则为：，迭代规则为：上上式式表表示示dij(1)在在dij(0)以以及及从从顶顶点点vi经经过过顶顶点点v1到到vj的的权权之之和和di1(0)+d1j(0)两两者者之之中中选选择择最最短短长长度度。依此规则迭代。依此规则迭代。上上式式表表示示dij(2)在在dij(1)以以及及从从顶顶点点vi经经过过顶顶点点v2到到vj的的权
10、权之之和和di2(1)+d2j(1)两两者者之之中中选选择择最最短短长长度度。依此类推，迭代公式为依此类推，迭代公式为：上上式式表表示示dij(m)在在dij(m-1)以以及及从从顶顶点点vi经经过过顶顶点点vm到到vj的的权权之之和和dim(m-1)+dmj(m-1)两两者者之之中中选选择择最最短短长长度。当度。当m=n时结束迭代。时结束迭代。2程序设计程序设计 先编写先编写Flody算法的子程序（函数）如下：算法的子程序（函数）如下：Function D,R=floyd(a)n=size(a,1);D=a;%D是初始矩阵是初始矩阵for i=1:n for j=1:n R(i,j)=j;e
11、ndendfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j)D(i,j)=D(i,k)+D(k,j);%在循环中进在循环中进行矩阵迭代行矩阵迭代 R(i,j)=R(i,k);%R是路径矩阵是路径矩阵 end end endendD,R%输出最短路矩阵和最短路的路径矩阵。输出最短路矩阵和最短路的路径矩阵。以以上上程程序序是是通通用用程程序序，只只需需输输入入初初始始距距离离矩矩阵阵，就就能能输输出出最最短短路路矩矩阵阵以以及及最最短短路路的的路路径径矩矩阵阵，将将程序以文件名程序以文件名floyd.m存盘。存盘。例例1 以以2007年年研研究
12、究生生数数学学建建模模竞竞赛赛C题题为为例例，已已知知16个个邮邮政政支支局局的的初初始始距距离离矩矩阵阵，求求任任意意两两个个节点之间的最短路。节点之间的最短路。解：编写主程序如下：解：编写主程序如下：a=0,27,44,17,11,27,42,inf,inf,inf,20,25,21,21,18,27,inf;inf,inf,inf,inf,30,inf,inf,inf,21,13,20,inf,inf,inf,inf,9,0;D,R=floyd(a);输输入入数数据据中中的的inf表表示示无无穷穷大大（两两个个顶顶点点之之间间没有边直接相连）。没有边直接相连）。运运行行以以上上程程序序，
13、求求得得最最短短路路矩矩阵阵D和和最最短短路路的的路径矩阵。路径矩阵。此处省略结果。此处省略结果。3 最小生成树一、一、最小生成树的概念最小生成树的概念树树是是图图论论中中的的一一种种简简单单而而重重要要的的图图，连连通通并并且且无无圈圈的的无无向向图图称称为为树树，常常用用T表表示示。树树有有以以下下性性质：质：(1)树中任意两点之间有唯一路径；树中任意两点之间有唯一路径；(2)树的边数等于顶点数减树的边数等于顶点数减1；(3)在树中删去任意一条边就不连通；在树中删去任意一条边就不连通；(4)在在树树中中任任意意两两个个不不相相邻邻的的顶顶点点间间添添加加一一条条边，则恰好产生一个圈。边，则
14、恰好产生一个圈。具具有有n个个顶顶点点的的无无向向连连通通图图是是树树的的充充分分必必要要条条件件是是它它有有n-1条条边边连连通通图图G的的子子图图T，如如果果它它的的顶顶点点集集与与G的的顶顶点点集集相相同同，且且T为为树树，则则称称T是是图图G的的生生成成树树，又又称称支支撑撑树树。如如果果图图的的边边有有权权（对对应应于于边边的的实实数数），则则生生成成树树上上各各边边权权的的总总和和称称为为生生成成树树的的权权，生生成成树树并并不不唯唯一一，权权达达到到最最小小的的生生成成树树称称为为最最小小生生成成树树(Minimal Spanning Tree，简称简称MST)，最小生成树不一定
15、唯一，最小生成树不一定唯一最最小小生生成成树树是是网网络络优优化化中中的的一一个个重重要要问问题题，在在网网络络设设计计中中有有广广泛泛的的应应用用，例例如如如如何何修修筑筑一一些些公公路路把把若若干干个个城城镇镇连连接接起起来来且且总总里里程程最最短短；如如何何架架设设通通讯讯网网络络将将若若干干个个地地区区连连接接起起来来且且总总费费用用最最省省；如如何何修修筑筑水水渠渠将将水水源源和和若若干干块块待待灌灌溉溉的的土土地地连连接接起起来来且且总总距距离离最最短短等等等等这这些些应应用用问问题题通通称称为为最最优连线问题，其实质是寻找图的最小生成树优连线问题，其实质是寻找图的最小生成树二、二
16、、Prim（普里姆）算法（普里姆）算法求求图图的的最最小小生生成成树树最最常常用用的的算算法法有有两两种种：Prim（普普里里姆姆）算算法法和和Kruskal（克克罗罗斯斯克克尔尔）算法，这两种方法都由贪婪法的思想发展而来。算法，这两种方法都由贪婪法的思想发展而来。贪贪婪婪法法又又称称贪贪心心法法，该该法法总总是是做做出出在在当当前前看看来来最最好好的的选选择择，也也就就是是说说该该算算法法并并不不从从整整体体最最优优考考虑虑，它它所所做做出出的的选选择择只只是是在在某某种种意意义义上上的的局局部部最最优优选选择择。虽虽然然贪贪婪婪算算法法不不能能对对所所有有问问题题都都得得到到整整体体最最优
17、优解解，但但是是它它对对某某些些问问题题能能够够得得到到整整体体最最优优解解，例例如如图图的的固固定定起起点点的的最最短短路路问问题题，最最小小生生成成树树问问题题。有有时时候候，即即使使贪贪婪婪算算法法不不能能得得到到整整体体最最优解，但其结果却是整体最优解的很好近似。优解，但其结果却是整体最优解的很好近似。Prim算算法法的的思思路路是是：把把所所有有顶顶点点分分成成部部分分（两两个个集集合合），一一个个用用S表表示示（该该集集合合中中的的顶顶点点都都涂涂成成红红色色），另另一一个个用用V-S表表示示（该该集集合合中中的的顶顶点点都都涂涂成成白白色色），开开始始时时S中中只只有有一一个个顶
18、顶点点v1，其其余余顶顶点点都都是是白白色色，在在一一个个端端点点为为红红色色，另另一一个个端端点点为为白白色色的的边边中中选选取取权权最最小小的的边边，将将该该边边涂涂红红（表表示示入入选选最最小小生生成成树树）并并且且把把该该边边的的白白色色端端点点也也涂涂红红（表表示示移移入入S中中）这这个个过过程程一一直直进进行行下下去去，S中中的的端端点点越越来来越越多多，直直到到所所有有顶顶点点都都涂涂成成红色为止，或者说红色边达到红色为止，或者说红色边达到n-1条为止。条为止。从从Prim算算法法的的思思路路中中可可以以看看出出，该该算算法法的的关关键键是是如如何何找找出出连连接接红红点点和和白
19、白点点的的所所有有边边中中找找出出权权最最小小的的边边。若若G为为完完全全图图，当当前前有有k个个红红点点，则则有有n-k个个白白点点，有有k(n-k)条条连连接接红红、白白点点的的边边，为为了了在在如如此此众众多多的的边边中中找找到到权权最最小小的的边边，可可以以分分两两步步走走，对对每每一一个个白白点点，先先从从连连接接该该点点至至k个个红红点点的的k条条中中找找出出权权最最小小的的边边作作为为候候选选边边，然然后后对对n-k个白点，从个白点，从n-k条候选边中找出权最小的边。条候选边中找出权最小的边。实现实现Prim算法的算法的Matlab编程思路如下：编程思路如下：(1)设设第第一一个
20、个红红点点是是节节点点v1。构构建建初初始始候候选选边边的的权权矩矩阵阵B。该该矩矩阵阵有有3行行，第第一一行行表表示示当当前前红红点点，开开始始时时第第一一个个红红点点是是v1，故故第第一一行行都都是是1，第第二二行行表表示示白白点点，开开始始时时白白点点的的序序号号是是2,3,n，第第三三行行表表示示连连接接红红点点和和白白点点的的边边的的权权值值。当当前前入入选选最最小小生生成成树树的的最最短短边边将将从从该该矩矩阵阵中中产产生生。初初始始最小生成树最小生成树T是空集。是空集。(2)对对B矩矩阵阵的的第第3行行排排序序，即即对对候候选选边边的的权权值值进进行行排排序序，选选取取最最短短边
21、边（权权值值最最小小的的边边），把把该该边边涂涂红红（选选入入最最小小生生成成树树的的边边集集T），该该边边的的白白色端点也涂成红色。色端点也涂成红色。(3)将将(2)选选出出的的边边移移出出B（不不参参与与下下一一轮轮竞竞选选），即即将将它它从从B矩矩阵阵中中删删除除。当当前前有有n-2个个白白点点（两两个个红红点点），对对每每个个白白点点都都有有到到两两个个红红点点的的两两条条边边，通通过过比比较较这这两两者者的的大大小小，选选出出权权值值小小的的边边，放放入入B矩矩阵阵的的相相应应位位置置上上，由由此此构构建建新新的的候候选选边边矩矩阵阵B，此时，此时B矩阵的有矩阵的有n-2列。列。(4
22、)对对新新的的B矩矩阵阵重重复复(2)和和(3)，T中中的的边边将将越越来来越越多多，B矩矩阵阵的的列列数数越越来来越越少少，当当选选入入T中中的红色边达到的红色边达到n-1条时结束运算，输出条时结束运算，输出T。按照以上思路编写按照以上思路编写Matlab程序如下：程序如下：function T,e=prim(a)T=;%T为最小生成树的边集，开始为空集。为最小生成树的边集，开始为空集。e=0;%e是最小生成树的长度，开始为是最小生成树的长度，开始为0。v=1;%v表示第一个红点是表示第一个红点是1号顶点。号顶点。n=size(a,1);%n是是总总顶顶点点数数，它它等等于于初初始始距距离离
23、矩阵矩阵a的列数。的列数。c=2:n;%c代表所有白点，开始是代表所有白点，开始是2,3,n。for j=2:n b(1,j-1)=1;b(2,j-1)=j;b(3,j-1)=a(1,j);end%以以上上一一段段程程序序生生成成3行行n-1列列的的矩矩阵阵，存存储储初初始始候候选选边边及及其其权权值值信信息息，该该矩矩阵阵的的第第一一行行都都是是1，表表示示第第一一个个红红色色点点是是1号号顶顶点点，第第二二行行表表示示白白色色点点依依次次为为2,3,n，第第三三行行表表示示所所有有连连接接红红点点和白点的边的权值和白点的边的权值while size(T,2)n-1%只只要要最最小小生生成成
24、树树的的边边数数小于小于n-1就循环就循环m,i=min(b(3,:);%从从候候选选边边中中找找出出权权值值最最小小的的边边（其其值值存存入入变变量量m，序号为，序号为i）T(:,size(T,2)+1)=b(:,i);%当当前前最最短短边边（含含起起点点、终终点点和和权权值值3个个树树中中）存入存入T中当前列，表示入选最小生成树中当前列，表示入选最小生成树 e=e+b(3,i);%累计最小生成树的长度累计最小生成树的长度 v=b(2,i);%把把新新入入选选最最小小生生成成树树的的边边的的白白色色端点变成当前红点端点变成当前红点t=find(c=b(2,i);c(t)=;%把把该该点点从从
25、白白点点集集合中移出去合中移出去b(:,i)=;%把该边从候选边中删除把该边从候选边中删除 for j=1:length(c)d=a(v,b(2,j);if d0&a(i,j)1，(2)如如果果线线路路从从j到到k，则则uk=uj+1，且且避避免免来来回回重重复和圈，约束条件为复和圈，约束条件为:ujuk+xkj-(n-2)(1-xkj)+(n-3)xjk，1kn，2jn jk；最优连线最优连线(最小生成树最小生成树)转化为整数规划：转化为整数规划：例例3 假假设设某某电电力力公公司司计计划划在在七七个个村村庄庄之之间间架架设设电电线线，各各村村庄庄之之间间的的距距离离如如图图所所示示试试求求
26、出出使电线总长度最小的架线方案使电线总长度最小的架线方案2.LINGO程序程序编写编写LINGO程序如下：程序如下：MODEL:sets:city/1.7/:u;!定义定义7个城市个城市;link(city,city):dist,x;!距离矩阵和决策变量距离矩阵和决策变量;endsets n=size(city);data:!dist是距离矩阵是距离矩阵;dist=0 3 4 7 100 100 100 3 0 3 2 4 100 100 4 3 0 100 5 7 100 7 2 100 0 2 100 6 100 4 5 2 0 1 4 100 100 7 100 1 0 2100 100
27、 100 6 4 2 0;!这里可改为你要解决的问题的数据这里可改为你要解决的问题的数据;enddata min=sum(link:dist*x);!目标函数目标函数;U(1)=0;for(link:bin(x);!定义定义X为为01变量变量;FOR(city(K)|K#GT#1:sum(city(I)|I#ne#K:x(I,K)=1;for(city(J)|J#gt#1#and#J#ne#K:u(J)=u(K)+X(K,J)-(N-2)*(1-X(K,J)+(N-3)*X(J,K);););sum(city(J)|J#GT#1:x(1,J)=1;for(city(K)|K#gt#1:U(K)
28、=1;U(K)=N-1-(N-2)*X(1,K););end计算结果：目标函数值计算结果：目标函数值(最优连线的长度最优连线的长度)为为13，最优连线的构成如图所示最优连线的构成如图所示41235674 旅行商问题一、一、旅行商问题的基本概念旅行商问题的基本概念旅旅行行商商问问题题（又又称称货货郎郎担担问问题题，traveling salesman problem，简简称称TSP问问题题）是是典典型型的的组组合合优优化化问问题题，并并且且是是一一个个NP完完全全难难题题，其其提提法法为为：有有n个个城城市市，相相互互之之间间的的旅旅行行费费用用（或或距距离离）为为已已知知，有有一一个个旅旅行行
29、推推销销商商，从从某某个个基基点点城城市市出出发发，要要遍遍访访其其余余n-1个个城城市市至至少少一一次次，最最后后回回到到出出发发点点，试试找找出出总总费费用用最最小小（或或总总路路程程最最短短）的旅行路线。的旅行路线。称称能能够够到到每每个个城城市市至至少少一一次次的的回回路路为为旅旅行行商商回路，其中费用最少者为最优旅行商回路回路，其中费用最少者为最优旅行商回路.在在图图论论中中，经经过过所所有有顶顶点点恰恰好好一一次次的的圈圈（路路）称称为为哈哈密密顿顿圈圈（路路），简简称称H圈圈（H路路），存存在在H圈的图称为哈密顿图，简称圈的图称为哈密顿图，简称H图。图。旅旅行行商商问问题题是是指
30、指在在赋赋权权图图上上经经过过每每个个顶顶点点至至少少一一次次，且且总总长长度度（路路径径上上权权的的总总和和）达达到到最最小小的的闭闭通通路路。在在加加权权的的连连通通无无向向图图中中，权权最最小小的的H圈圈简简称称最最优优H圈圈；经经过过每每个个顶顶点点至至少少一一次次且且权权最最小小的的闭闭通通路路称称为为最最优优旅旅行行商商回回路路。注注意意：最最优优H圈圈与与最最优优旅旅行行商商回回路路两两者者是是有有区区别别的的，最最优优H圈圈只只允允许许经经过过每每个个顶顶点点恰恰好好一一次次，而而最最优优旅旅行行商商回回路路允许经过某些顶点一次以上。允许经过某些顶点一次以上。定定理理1 在在加
31、加权权图图G=（V，E）中中，若若对对任任意意顶顶点点x,y,z（zx,zy），都都满满足足w(x,y)w(x,z)+w(y,z)（三三角角形形的的两两边边之之和和大大于于等等于于第第三三边边，称称为为三三角角不不等等式式），则则该该图图的的最最优优哈哈密顿圈也是最优旅行商回路。密顿圈也是最优旅行商回路。对对于于连连通通的的非非完完全全赋赋权权图图G，先先求求出出任任意意两两点点之之间间的的最最短短路路，然然后后用用最最短短路路作作为为每每一一条条边边的的权权，构构造造一一个个以以V为为顶顶点点集集的的完完全全图图G=（V，E），容容易易证证明明，在在如如此此构构造造出出来来的的图图G中中，各
32、各边边的的权权自自然然满满足足三三角角不不等等式式，故故在在加加权权图图G中中寻寻求求最最优优旅旅行行商商回回路路的的问问题题就就可可以以转转化化为为在在图图G中中寻寻求求最最优哈密顿圈的问题。优哈密顿圈的问题。寻寻找找最最优优哈哈密密顿顿圈圈和和最最优优旅旅行行商商回回路路是是图图论论中中的的典典型型问问题题，而而且且是是一一个个NP完完全全难难题题。问问题题的的求求解解没没有有多多项项式式时时间间算算法法，除除了了穷穷举举法法，目目前前还还没没有有寻寻找找最最优优解解的的算算法法，随随着着顶顶点点数数的的增增加加，运运算算所所需需时时间间呈呈指指数数级级增增长长，当当顶顶点点数数较较大大时
33、时，求求出出最最优优解解所所需需时时间间可可能能是是难难以以忍忍受受的的。可可行行的的方方法法是是用用近近似似算算法法，力力争争在在较较短短时时间间寻寻找找接接近近最最优优解的近似最优解。解的近似最优解。旅旅行行商商问问题题得得到到了了许许多多学学者者的的关关注注和和长长期期研研究究，提提出出了了多多种种近近似似算算法法，例例如如分分支支定定界界法法、遗遗传传算算法法、模模拟拟退退火火法法、蚁蚁群群算算法法、神神经经网网络络方方法法、粒粒子子群群优优化化算算法法、重重绕绕最最小小生生成成树树法法、二二次次逐逐边边修修正法等。正法等。二、用二、用LINGOLINGO求解求解TSPTSP问题的方法
34、一问题的方法一1.把最优哈密顿圈问题转化为把最优哈密顿圈问题转化为0-1线性规划线性规划 将将任任意意两两点点之之间间的的最最短短路路作作为为两两点点之之间间边边的的权权构构造造完完全全图图G。引引入入0-1整整数数变变量量xij(且且ij)：若若xij=1则边则边i-j在回路中，而在回路中，而xij0则表示否。则表示否。目标函数目标函数首首先先必必须须满满足足约约束束条条件件：对对每每个个城城市市访访问问一一次次且且仅仅一一次次。从从城城市市i出出发发一一次次(到到其其它它城城市市去去),表示为表示为从某个城市到达从某个城市到达j一次且仅一次，表示为：一次且仅一次，表示为：以以上上建建立立的
35、的模模型型类类似似于于指指派派问问题题的的模模型型，对对TSP问题只是必要条件，并不充分。问题只是必要条件，并不充分。例例如如，用用图图示示路路线线连连接接六六个个城城市市，满满足足以以上上两两个个约约束束条条件件，但但这这样样的的路路线线出出现现了了两两个个子子回回路，两者之间不通，不构成整体巡回路线。路，两者之间不通，不构成整体巡回路线。为为此此需需要要考考虑虑增增加加充充分分的的约约束束条条件件以以避避免免产产生子巡回。生子巡回。下面介绍一种方法：下面介绍一种方法：增增加加变变量量u ui i,i,i=2,3,n=2,3,n，（它它的的大大小小可可以以取取正正整整数数：例例如如从从起起点
36、点出出发发所所达达到到的的城城市市u=2,u=2,依依此类推）。此类推）。312456附加约束条件：附加约束条件：ui-uj+nxijn-1,i=1,n，j=2,n，且且ij。下下面面证证明明：(1)任任何何含含子子巡巡回回的的路路线线都都必必然然不不满满足足该约该约束条件束条件（不管（不管ui如何取值）如何取值）；(2)全全部部不不含含子子巡巡回回的的整整体体巡巡回回路路线线都都可可以以满满足足该约该约束条件束条件（只要（只要ui取适当值）取适当值）。用用反反证证法法证证明明(1),假假设设存存在在子子巡巡回回，则则至至少少有有两两个个子子巡巡回回。那那么么（必必然然）至至少少有有一一个个子
37、子巡巡回回中中不不含起点城市含起点城市1，如上图中的，如上图中的4564，则必有，则必有 u4-u5+nn-1，u5-u6+nn-1，u6-u4+nn-1，把把这这三三个个不不等等式式加加起起来来得得到到nn-1，不不可可能能，故故假假设设不不能能成成立立。而而对对整整体体巡巡回回，因因为为附附加加约约束束中中j2,不包含起点城市不包含起点城市1，故不会发生矛盾。，故不会发生矛盾。对对于于整整体体巡巡回回路路线线，只只要要ui取取适适当当值值，都都可可以以满满足足该约该约束条件束条件：()对对于于总总巡巡回回上上的的边边，xij=1,ui可可取取访访问问城城市市i的的 顺顺 序序 数数，则则
38、必必 有有 ui-uj-1，约约 束束 条条 件件 ui-uj+nxijn-1变成：变成：-1+n n-1，必然成立。必然成立。()对对于于非非总总巡巡回回上上的的边边，因因为为xij=0，约约束束条条件件ui-uj+nxijn-1变成变成-1n-1，肯定成立。肯定成立。综综上上所所述述，该该约约束束条条件件只只限限止止子子巡巡回回，不不影影响响其其它它，于于是是TSP问问题题转转化化成成了了一一个个整整数数线线性性规规划划问问题题。求最优哈密顿圈可以表示为规划：求最优哈密顿圈可以表示为规划：2.LINGO程序程序!旅行售货员问题旅行售货员问题;model:sets:city/1.17/:u;
39、!定义定义17个城市个城市;link(city,city):dist,!距离矩阵距离矩阵;x;!决策变量决策变量;endsets n=size(city);data:!距离矩阵距离矩阵;C =0 16.3 11.9 10.1 28 12.9 6 20.6 28.4 22.2 20.8 35.7 22.1 30.2 23.7 27.8 3616.3 0 12.2 26.4 23.9 8.8 10.3 36.9 40.1 32.2 16.7 31.6 14.7 22.8 7.4 11.5 19.711.9 12.2 0 22 36.1 21 5.9 32.5 40.3 34.1 28.9 43.8
40、 26.9 35 19.6 17.6 25.810.1 26.4 22 0 20.4 23 16.1 10.5 18.3 12.1 15.2 28.1 32.2 38.4 33.8 37.9 46.128 23.9 36.1 20.4 0 15.1 34 24 16.2 8.3 7.2 7.7 24.3 18 31.3 35.4 32.912.9 8.8 21 23 15.1 0 18.9 33.5 31.3 23.4 7.9 22.8 9.2 17.3 16.2 20.3 28.56 10.3 5.9 16.1 34 18.9 0 26.6 34.4 28.2 26.8 41.7 25 33
41、.1 17.7 21.8 3020.6 36.9 32.5 10.5 24 33.5 26.6 0 7.8 15.7 25.7 31.7 42.7 42 44.3 48.4 56.628.4 40.1 40.3 18.3 16.2 31.3 34.4 7.8 0 7.9 23.4 23.9 40.5 34.2 47.5 51.6 49.122.2 32.2 34.1 12.1 8.3 23.4 28.2 15.7 7.9 0 15.5 16 32.6 26.3 39.6 43.7 41.220.8 16.7 28.9 15.2 7.2 7.9 26.8 25.7 23.4 15.5 0 14.
42、9 17.1 25.2 24.1 28.2 36.435.7 31.6 43.8 28.1 7.7 22.8 41.7 31.7 23.9 16 14.9 0 18.4 10.3 25.7 33.4 25.222.1 14.7 26.9 32.2 24.3 9.2 25 42.7 40.5 32.6 17.1 18.4 0 8.1 7.3 26.2 2330.2 22.8 35 38.4 18 17.3 33.1 42 34.2 26.3 25.2 10.3 8.1 0 15.4 23.1 14.923.7 7.4 19.6 33.8 31.3 16.2 17.7 44.3 47.5 39.6
43、 24.1 25.7 7.3 15.4 0 18.9 20.327.8 11.5 17.6 37.9 35.4 20.3 21.8 48.4 51.6 43.7 28.2 33.4 26.2 23.1 18.9 0 8.236 19.7 25.8 46.1 32.9 28.5 30 56.6 49.1 41.2 36.4 25.2 23 14.9 20.3 8.2 0;!这里可改为你要解决的问题的数据这里可改为你要解决的问题的数据;enddata!目标函数目标函数;min=sum(link:dist*x);FOR(city(K):!进入城市进入城市K;sum(city(I)|I#ne#K:x(
44、I,K)=1;!离开城市离开城市K;sum(city(J)|J#ne#K:x(K,J)=1;);!保证不出现子圈保证不出现子圈;for(city(I)|I#gt#1:for(city(J)|J#gt#1#and#I#ne#J:u(I)-u(J)+n*x(I,J)=n-1););!限限制制u的的范范围围以以加加速速模模型型的的求求解解，保保证证所所加加限限制并不排除制并不排除掉掉TSP问题的最优解问题的最优解;for(city(I):u(I)=n-1);for(link:bin(x);!定义定义X为为01变量变量;end计算结果：计算结果：目标函数值：目标函数值：159.3路线：路线：1 17
45、73 3161617171414131315152 26 6111112125 510109 98 84 41 1因因为为以以上上规规划划是是线线性性规规划划，所所以以求求解解不不费费时时，当当顶顶点点数数为为2030个个时时，一一般般几几分分钟钟就就可可以以得得到最优解。到最优解。利利用用LINGO软软件件的的强强大大优优化化能能力力，不不必必研研究究旅旅行行商商问问题题的的算算法法，通通过过编编写写不不太太复复杂杂的的LINGO程程序序，能能够够较较快快地地解解决决实实际际问问题题，达达到到事半功倍的效果。事半功倍的效果。三、用三、用LINGOLINGO求解求解TSPTSP问题的方法二问题
46、的方法二1.对城市排序，找出最优排序对城市排序，找出最优排序在在现现实实中中的的城城市市交交通通图图中中，有有些些城城市市之之间间有有直直接接道道路路，有有些些则则没没有有，如如果果两两点点之之间间没没有有直直接接的的通通路路，则则两两点点之之间间的的距距离离取取最最短短路路（经经过过其其它它点点），即即用用任任意意两两点点之之间间的的最最短短路路Cij作作为为图图的的距距离离矩矩阵阵，构构成成一一个个完完全全图图G，其其任任意意一一对对顶顶点点都都有有一一条条边边相相连连。图图G的的最最优优旅旅行行商商回回路路等等价价于于图图G的的最最优优哈哈密密顿顿圈圈，此此时时形形式式上上的的环环形巡回
47、路线实际上个别点有可能不止经过一次。形巡回路线实际上个别点有可能不止经过一次。设设某某个个城城市市为为旅旅行行的的出出发发地地和和终终点点（相相当当于于总总部部所所在在地地），旅旅行行者者从从该该城城市市出出发发到到其其它它n个个城城市市各各一一次次且且仅仅一一次次，最最后后回回到到出出发发地地。我我们们把把行行进进路路线线分分成成n步步，每每一一步步到到一一个个城城市市（第第n+1步步返返回回出出发发地地），于于是是一一条条旅旅行行路路线线就就相相当当于于n个个城城市市的的一一种种排排列列，n个个城城市市共共有有n!种种排排列列方方式式。排排序序不不同同则则总总里里程程（或或费费用用）可可能
48、能不不同同，总总里里程程（或或总总费费用用）最最小小的的排排序序就就是是我我们们要要寻寻找的最优路线。找的最优路线。引引入入0-1型型决决策策变变量量Xkj，下下标标k表表示示旅旅行行的的步步数数，下下标标j表表示示到到达达哪哪一一个个城城市市，Xkj=1表表示示旅旅行行者者第第k个个目目的的地地（到到达达点点）是是城城市市j，Xkj=0则则表表示示否否。用用lj表表示示总总部部到到各各城城市市的的距距离离，用用Cij表表示示城市城市i与城市与城市j之间的最短路。之间的最短路。从出发地到第从出发地到第1个点的路程为个点的路程为从最后一个点返回出发地的里程为从最后一个点返回出发地的里程为 假假设
49、设在在第第k步步到到达达城城市市i，在在第第k+1步步达达到到城城市市j，即，即Xki=Xk+1,j=1，则走过的里程为：，则走过的里程为：CijXkiXk+1,j从第从第1点到第点到第n点走过的总里程为点走过的总里程为目标函数为目标函数为约束条件有以下约束条件有以下2条：条：(1)每一步到达一个城市，即每一步到达一个城市，即(2)每一个城市必须到一次且只需一次，即每一个城市必须到一次且只需一次，即综综上上所所述述，可可以以把把最最优优哈哈密密顿顿圈圈问问题题转转化化成成如下非线性如下非线性0-1 规划规划以上规划中允许包含其它约束条件。以上规划中允许包含其它约束条件。用用LINGO可以求解该
50、规划，举例如下。可以求解该规划，举例如下。某某县县邮邮局局和和10个个乡乡镇镇支支局局组组成成该该县县的的邮邮政政运运输输网网络络，已已知知县县局局到到各各支支局局的的距距离离和和支支局局之之间间的的距距离离矩矩阵阵（数数据据在在程程序序中中）。用用一一辆辆邮邮车车完完成成邮邮件件运运输输任任务务，邮邮车车从从县县局局出出发发到到各各支支局局去去一一次次且且只只需需一一次次，最最后后回回到到县县局局，求求总总路路程程最最短的行驶路线。短的行驶路线。解解：本本题题是是“旅旅行行商商”问问题题。可可以以用用上上面面介介绍的方法求解。绍的方法求解。编写编写LINGO程序如下：程序如下：MODEL:S