第12讲 旅行售货商问题和斯坦纳最小树问题

旅行售货商问题和斯坦纳最小树问题旅行售货商问题一个售货商想去几个城市推销商品，他希望从公司所在城市出发后，在其旅途中恰好路过他所要去的每个城市一次，最后返回出发地。假设他已知每对城市间的距离，问如何安排旅行路线，所走的路线总长度最短，这就是旅行售货商问题（TravellinSalesmanProblem,TSP）。也称货郎担问题。TSP问题是要求经过图中每个点一次，有一种问题是要求经过每条边一次，称为中国邮路问题。说明记售货商要访问的城市为1,2,…,n，城市i与j之间的距离为cij，每一条旅行路线称为一个旅游，它可用一个置换Φ表示。一个置换表示一个旅游当且仅当该置换不能分解称两个因子的乘积，称这种置换为圈置换。圈置换Φ=(1,3,5,4,2)表示从1出发如下一个旅游：13542说明而τ=(1,3,5)(2,4)就不能表示一个旅游，它表示13532表示TSP可以表示为,其中φ为不可分解的所有n阶圈置换，φ(i)表示访问城市i后紧接着访问的城市。)(min1)(ccniii否则之后紧接着访问城市售货商访问城市,0;,1jixij且不含子旅游或,,...,2,1,,10,...,2,1,1;,...2,1,1..min1111njixnjxnixtsxcijnjijnjijninjijij实际问题例子：现需在一台机器上加工n个零件，这些零件可按任意先后顺序在机器上加工，我们希望加工完成所有零件总时间尽可能少。由于加工工艺的要求，加工零件j时机器必须处于相应状态sj。设起始未加工任何零件时机器处于状态s0,且当所有零件加工完成后续恢复到s0状态。一直从状态si调整到状态sj需要时间cij，零件j本身加工时间为pj。为方便起见，引入一个虚零件，其加工时间为p0=0,要求状态为s0,则{0,1,2,…,n}的一个圈置换π就表示对所有零件的一个加工顺序，在此置换下，完成所有加工所需要的总时间为niiiniiiniiiiipcpc0)(0)(0)()()(实际问题例子：现有一卷有图案的墙纸，墙纸上的图案以一定的周期重复出现，不妨设周期为1，先要从这卷墙纸上切割下n片，设第i片纸需从图案的si初开始，fi处结束，中间含li个重复的图案，因此若从卷纸上先割下第i片后再去割第j片，浪费的量为，假设切割开始时，这卷墙纸起始位置为s0=0，且切割完成所需的n片纸后也必须再切一次使剩下的墙纸起始位置仍未s0=f0=0.为此引入一个虚片，它的起始位置和结束位置分别为s0,f0,则设计一个切割顺序使总浪费量最小的问题就转化为n+1个城市的旅行售货商问题。1,0iifs否则如果,1,ijiiijijfssffsc易解的旅行售货商问题1.为上三角阵；2.金字塔形旅游nnijcC)(指派问题可以看成松弛的TSP问题，我们在解决上三角阵的情况时主要使用指派问题的算法。C为上三角阵的情况引理：设C是上三角矩阵，Φ满足Φ(n)=1的最优指派，则为最有旅游总长度的下界。niiicc1)()(引理：设C是上三角阵，Φ满足Φ(n)=1的最优指派，则最优旅游τ的总长度等于,且τ可从Φ中构造出来。)(c算法1从C中删去第i列第n行，得到矩阵，然后求的最优指派。2如果最优指派中不含子旅游则结束；否则，取子旅游数目为s≥2,删掉最优指派中的反向弧(n,1)，以及每个子旅游中的反向弧；则得到一些路，其中一条必为由1到n的；设其它的路分别为j1到i1,j2到i2,…..,js-1到is-1,且j1j2…js-1,添加弧(n,j1)(i1,j2)(i2,j3)….(is-2,js-1),(is-1,1).算法结束)1()1(nn'C'C例子00000003000000118000009440000267300089168120052320710C300000118000094400026730089168120523207130000017018181818944000267300891681202518230271910000015018181818744000067300691681202318230271910}0{00015}0{181818187440}0{0}0{673006916812}0{231823}0{2719000000030}0{00001}18{000009440}0{00}2{6730008916812}0{0523}20{710C最优指派为565,22,1734123465734657112最近邻域算法NN1.任选一个城市i1,构造一个仅含此城市的部分旅游（i1）.2.设当前部分旅游为(i1,i2,…,ik),kn;若ik+1是不在当前部分旅游中的所有城市里离ik最近的城市，则将ik+1加入原部分旅游中，那么得到了新的部分旅游（i1,i2,…,ik+1）.3.如果当前部分旅游已含有所有城市，则停止，否则，转2.最小支撑树算法MST1.求网络的最小支撑树；2.从一个度为1的城市出发，沿每条边来回走一次，经过每个城市并，回到出发点。3.按“抄近路”原则，使得除起点外，每个城市仅经过一次。Christofides算法1.求出连接n个城市的最小支撑树T；2.找出T中度数为奇数的顶点，求出这些奇度点所组成的完全网络的最小权完美匹配M，将M加入T，得到一个包含所有顶点的图；3.利用抄近路原则得到一个旅游；斯坦纳最小树长度分别为8,和3243324332424定义给定欧氏平面上的点集P,如何设法添加新点集N,使关于P∪N的最小支撑树为连接P中的点的最短网络：斯坦纳最小树问题。P中的点成为正则点或者原点；N中的点成为斯坦纳点或者斯点。三角不等式：AB≤AC+CB正权网络中的斯坦纳最小树给定无向网络网络上每条边权值为正。在允许使用V-P中的点的情况下，如何连接P中的点成一个树，使总长度尽可能小。sPVnPVPEVG||||,||,),,,(P中的点称为正则点、原点，V-P中的点为斯坦纳的点、斯点。Lawler算法1.计算最短路。如果网络中每条边的边长不满足三角不等式，则计算所有顶点对之间的最短路及路长，用最短路长代替原来的边长，产生一个完全网络。2.求最小支撑树。对每个点集，构造出的最小支撑树。3.构造最小斯坦纳最小树。求出2中得到的所有树中的最小树，然后将该树中的每条边还原成最短路中的边，从而还原成原来网络中的一个树。2||,nNPVNNPMST算法1.对P中任何一对顶点，求出它的最短路；2.构造一个一个以P为顶点集的完全图Gs，定义每条边的长为相应顶点在G中的最短路长；3.求Gs的最小支撑树Tmin4.将Tmin中每条边还原成G中最短路的边，从而得到G中的一个连接P的一个斯坦纳树。作业P153:4;P165:7