lecture10

NP 完全性的证明SAT限制法局部替换法构件设计法恰好覆盖3SAT 最大可满足性构件设计法构件设计法构件设计法子集和VC 有向HC 限制法局部替换法HC独立集双机调度0-1背包局部替换法局部替换法团背装箱限制法局部替换法MAX SAT最大可满足性MAX-SAT(MAX-SAT): 任给关于变元x,x2,…,x n的简单最大可满足性(MAX SAT):1析取式C,C2,…,C m 及正整数K, 问存在关于变元x1,x2,…,x n1,C2,…,C m中至少有K 个为真吗?的赋值使得CK1设判定问题Π=<D,Y>, Π′=<D′,Y′>, 如果D′⊆D, Y′=D′∩Y, 则Π′是Π的特殊情况, 称作Π的子问题.: 如果已知Π的某个子问题Π是NP难的, 则Π也是限制法:′NP难的⎯⎯只需把Π′的实例I 看作Π特殊情况的实例.定理MAX-SAT是NP完全的.证MAX-SAT∈NP. 要证SAT≤MAX-SAT. 任给SAT的实例pI, 对应的MAX-SAT的实例f(I): 其他不变，仅需令K=m.I MAX SAT)其他不变仅需令3SAT3元合取范式: 每一个简单析取式恰好有3个文字的合取范式.每个简单析取式恰好有三元可满足性(3SAT): 任给一个3元合取范式F, 问F是可满足的吗?定理3SAT NP.是完全的’证显然3SAT∈NP.要证SAT ≤p3SAT. 任给个合取范式F, 要构造对应的3元合SAT3SAT.任给一个合取范式,取范式F ′=f(F), 使得F是可满足的当且仅当F′是可满足的.设F C1∧C2∧…∧C m, 对应的F F1∧F2∧…∧F m, F j是对=,′=′∧′′,′的合取范式, 并且应CjC j是可满足的当且仅当F j是可满足的.′F j′的构造规则(1) C j = z1. 引入两个新变元y j1, y j2, 令(1)F j′= (z1∨y j1∨y j2)∧(z1∨¬y j1∨y j2)∧(z1∨y j1∨¬y j2)∧(z1∨¬y j1∨¬y j2)(2)引入个新变元(2) C j = z1∨z2. 引入一个新变元y j, 令F j′= (z1∨z2∨y j)∧(z1∨z2∨¬y j)(3) C j = z1∨z2∨z3. 令F j′=C j.(3)(4) C j = z1∨z2∨…∨z k, k≥4. 引入k-3个新变元y j1, y j2,…,y j(k-3), 令F j′= (z1∨z2∨y j1)∧(¬y j1∨z3∨y j2)∧(¬y j2∨z4∨y j3)∧…∧(¬y j(k-4)∨z k-2∨y j(k-3))∧(¬y j(k-3)∨z k-1∨z k)实例:C j = z1∨z2∨…∨z5jF j′= (z1∨z2∨y j1)∧(¬y j1∨z3∨y j2)∧(¬y j2∨z4∨z5))1)1证明t(C)=1 ⇔t(F j′)=1j, 则存在i使得t(z i)=1设赋值)1t 满足Cj)=0 (1≤s≤k-3)当i=1 或2 时, 令t(yjs)=1 (1≤s≤k-3)当i= k-1 或k 时, 令t(yjs)=1 (1≤s≤i-2), t(y js)=0 (i-1≤s≤k-3)当3≤i≤k-2时, 令t(yjs′)=1.则有t(Fj反之, 设t(F′)=1.j)=0, 则t(z1∨z2)=1若t(yj1)=1, 则t(z k-1∨z k)=1若t(y)=1j(k-3)否则, 必有s(1≤s≤k-4) 使得t(y)=1且t(y j(s+1))=0,js)=1. 总之, 都有t(C j)=1.)1)1从而t(zs+2变换时间F 4j ′中简单析取式的个数不超过C j 中文字个数的4 倍, 每个简单析取式有3个文字, 因此可以在|F | 的多项式时间内构造出F ′.证明方法局部替换法证明方法：局部替换法要证Π1 ≤p Π2. 当Π2 是Π1 的子问题或两者的结构相似时, 往把实每个结构替换实往可以把Π1 的实例的每一个子结构替换成对应的Π2 实例的子结构.例如把SAT 的每个析取式C j ，替换成一组析取式F j ′6顶点覆盖团与独立集顶点覆盖、团与独立集引理对任意无向图G=<V,E>和子集V′⊆V, 下述命题等价: (1) V′是G 的顶点覆盖,集(2) V-V′是G 的独立集,(3) V-V′是补图G c = <V,E c> 的团.顶点覆盖(VC): 任给一个无向图G = <V,E>和非负整数K≤|V|,G K问G 有顶点数不超过K 的顶点覆盖吗?团: 任给一个无向图G = <V,E>和非负整数J ≤|V |, 问G 有顶点数不小于J 的团吗?J独立集: 任给一个无向图G = <V,E>和非负整数J ≤|V |, 问G 有顶点数不小于J 的独立集吗?J顶点覆盖定理顶点覆盖是NP 完全的.证:VC 的非确定型多项式时间算法: 任意猜想一个子集V ′式⊆V , |V ′|≤K , 检查V ′是否是一个顶点覆盖.3SAT ≤VC. x x …x n 3要证p 任给变元1,2,,n 的元合取范式F = C 1∧C 2∧…∧C m ,j =,i i .其中C j z j 1∨z j 2∨z j 3, z jk 是某个x i 或¬x i .如下构造VC 的实例f (F ): G = <V ,E > 和K =n +2m , 其中=,V V 1∪V 2, E =E 1∪E 2∪E 3,{}变换实例U = {x 1, x 2, x 3, x 4}, C =(x 1∨¬x 3∨¬x 4)∧(¬x 1∨x 2∨¬x 4)K = 4 + 2×2 = 8x 1x 1x 2x 2x 3x 3x 4x 4[x 2,2][x 3,1][x 4,2][x 1,2][x 1,1][x 4,1]10说明定理独立集和团是NP完全的.构件设计法顶点覆盖问题的NP完全性证明中设计了2种“构件”变元构件：真值赋值功能简单析取式构件：满足性检验功能,式用这些构件及构件之间的连接构成G, 通过这种方式达到用VC的实例表达3SAT的实例的目的哈密顿回路与货郎问题有向哈密顿回路: 任给有向图D , 问:D 中有哈密顿回路吗?定理有向HC 是NP 完全的.证要证3SAT ≤p 有向HC. 任给变元x 1,x 2,…,x n 的3元合取范式F =C ∧C ∧…∧C , C =∨∨, x i ¬x i .12m ,其中j z j 1z j 2z j 3,每个z jk 是某个i 或i 采用构件设计法构造有向图D . 表示变元x i 的构件是一条由串水平的顶点组成的链相邻的两个顶点之间有对方一串水平的顶点组成的链L i , 相邻的两个顶点之间有一对方向相反的有向边. 只有两种可能的方式通过L i 上的所有顶点⎯⎯从左到右或者从右到左通过L i 上的所有顶点, 这恰好对应x i 的值为1或者为0. 表示简单析取式C j 的构件是一个顶点c j .添加s 0,s 1,…,x n , 并通过它们把L 1,L 2,…,L n 连接起来.变元构件与析取式构件连络边链1L i 有3m +1的顶点, 依次为d i 0, a i 1, b i 1,d i 1,a i 2, b i 2,d i 2, …,a im , b im , d im . 对每一个C j =z j 1∨z j 2∨z j 3,(1)如果>>z jk =x i , 则添加<a ij ,c j > 和<c j ,b ij >; (2)如果z jk =¬x i , 则添加<c j ,a ij > 和<b ij ,c j >.实例C 2= x 1∨¬x 3∨¬x 4 对应的连接变换实例:x, x2, x3, F=(x1∨¬x2)∧(x2∨¬x3)1t(x1)=1, t(x2)=1, t(x3)=0)1)1)0s0C1C2s3证明F 证明：F 可满足⇒D 存在HC 设构造条从t 是F 的成真赋值. 要根据t 构造一条从s 0到s n, 最后回到s 0的哈密顿回路.(1) 依次对i =1,2,…,n 进行, 若t (x i )=1, 则从s i -1到d i 0, 从左到右经过L i 的所有顶点到达d im , 再到s i ; 若t (x i )=0, 则从s i -1到d im , 从右到左经过L i 的所有顶点到达d i 0, 再到s i . 最后, 从s n 回到s 0.(2) 将所有c j 插入这条回路. 设C j =z j 1∨z j 2∨z j 3, 由于t (C j )=1, 必有k (1≤k ≤3)使得t (z jk )=1. 若z jk =x i , 则通路从左到右经过L i , 且有有向边<a ij ,c j >和<c j ,b ij >. 于是, 可以把c j 插在a ij 与b ij 之间; 若z jk =¬x i , 则通路从右到左经过L i , 且有有向边<b ij ,c j >和<c j ,a ij >. 于是, 可以把c j 插在b ij 与a ij 之间. 这就得到D 中的一条哈密顿回路.证明F证明：D存在HC⇒F 可满足反之, 设D有哈密顿回路P, 不妨设P从s0到sn再到s结束. 正常的回路从左到右或从右到左通过每一条Li, 每个c j 插在某个a ij和bij 或者bij和aij之间. 若P从左到右通过Li, 令t(x i)=1; 若P从右到左通过Li, 令t(x i)=0. 不难证明必有t(C j)=1.要证P一定是正常的. 假设不然, P一定从某条链Ls 的顶点u到cj后没回到L而是到链L s≠t). u=a, 由于b只与a c及d相s t()若sj,sj sj,j sj邻, P已经过asj 和cj, b sj只剩下一个相邻的顶点, 故P不可能通b. u=b, P a. P过sj若sj,同理可证不可能通过sj都与是哈密顿回路矛盾, 所以P一定是正常的.构造D可以在多项式时间内完成.HC与TSP定理HC是NP完全的.HC. 任给一个有向图D=<V,E>, 要构造无证要证有向HC ≤p向图G=<V′,E′>使D有哈密顿回路当且仅当G有哈密顿回路.把D的每一个顶点v替换成3个顶点v in, v mid和v out, 用边连接v in 和v mid, v mid和v out. D的每条有向边<u,v>在G中换成(u out,v in).即V′={v in, v mid, v out| v∈V },E′={(u out,v in) | <u,v>∈E}∪{(v in,v mid),(v mid,v out) | v∈V }.定理TSP是NP完全的.恰好覆盖恰好覆盖:,a2,…,a n}，A的子集的集合W={S1,S2,…,S m}, 有穷集A={a1问: 存在子集U⊆W使得U中的子集都是不相交的且它们的并集中集交集等于A? 称W这样的子集U是A的恰好覆盖.例如, 设A={1,2,3,4,5}, S={1,2}, S2={1,3,4}, S3={2,4}, S4={2,5},1则{S2,S4}是A的恰好覆盖. 若把S4改为S4{3,5}, 则不存在A的.={3,5},恰好覆盖.定理恰好覆盖是NP完全的.构件设计∧∧证任给变元x 1,x 2,…,x n 的合取范式F =C 1∧C 2∧…∧C m , 其中A ={{|1t 1j m }jjs j j j z z z C ∨∨∨= 21A = { x 1,x 2,…,x n , C 1,C 2,…,C m }∪{ p jt | 1≤t ≤s j , 1 ≤j ≤m },其中p jt 代表C j 中的文字z jt . W 包含下述子集:变元构件恰好覆盖对每个：恰好覆盖对每个i ，T T i 与T F i 恰好取其1T T i ={x i }∪{p jt | z jt = ¬x i , 1≤t ≤s j , 1≤j ≤m }, 1≤i ≤n ,T F i ={x i }∪{ p jt | z jt = x i , 1≤t ≤s j , 1≤j ≤m }, 1≤i ≤n ,析取式构件：恰好覆盖对每个j ，C jt 中恰好取其1j C jt ={C j ,p jt }, 1≤t ≤s j , 1≤j ≤m .填充物{p jt }, 1≤t ≤s j , 1≤j ≤m.实例1F=(x1∨¬x2)∧(¬x1∨x2∨x3)∧(x1∨¬x2∨x3)∧(x1∨¬x3)A={x1,x2,x3,C1,C2,C3,C4, p11,p12,p21,p22, p23,p31,p32,p33,p41,p42}, W包含下述子集:{p11},{p12},{p21},{p22},{p23},{p31},{p32},{p33},{p41},{p42},T1T={ x1,p21}, T1F={ x1,p11, p31, p41},{{}T2T ={ x2,p12, p32}, T2F ={ x2,p22},T{F{}T3T ={ x3,p42}, T3F ={ x3,p23,p33},C11={C1, p11}, C12={C1, p12},C21={C2, p21}, C22={C2, p22}, C23={C2, p23}, {}{}{}C31={C3, p31}, C32={C3, p32}, C33={C3, p33},C41={C4, p41}, C42={C4, p42}{}{23恰好覆盖满设证明：U 是恰好覆盖⇔F 可满足U ⊆W 是A 的恰好覆盖, ∀i , 若T T i ∈U , 则令t (x i )=1;若T F i ∈U , 则令t (x i )=0. ∀j , 必有一个C jt ={C j ,p jt }∈U . z jt =x i 或¬x i .(1))1(1) 若T T i ∈U , 则p jt ∉T T i , 从而z jt =x i . 有t (x i )=1, 故t 满足C j .(2) 若T F i ∈U , 则p jt ∉T F i , 从而z jt =¬x i . 有t (x i )=0, 故t 也满足C j . F t 是F 的成真赋值.反之,t .,)=1,T ;)=0,, 设t 是F 的成真赋值. ∀i , 若t (x i )1, 则U 包含T i ; 若t (x i )0, 则U 包含T F i . ∀j , 由于t 满足C j , C j 必有一个文字z jt 使得t (z jt )=1, .,.,从而U 中现有的子集不包含p jt . 于是, 可以把C jt 加入U . 至此, U 覆盖了所有的x i 和C j , 以及部分p jt . 最后, 把尚未被覆盖的p jt 构成的单元子集{p jt }加入U , 即可得到A 的恰好覆盖.24变换时间由于F 中的文字数不超过mn, 故|A| ≤n + m + mnW 中的子集数不超过2n + 2mn每个子集的大小不超过n+1.而且构造很简单, 显然可以在多项式时间内完成.子集和,背包,装箱与双机调度子集和: 给定正整数集合X ={x 1,x 2,…,x n }及正整数N , 问存在X 的子集T , 使得T 中的元素之和等于N 吗? 装箱: 给定n 件物品, 物品j 的重量为正整数w j , 1≤j ≤n , 以及箱K . B , 子数规定每只箱子装入物品的总重量不超过正整数,问能用K 只箱子装入所有的物品吗?双机调度: 有2台机器和n 项作业J 1,J 2,…,J n , 这2台机器完全相同, 每一项作业可以在任一台机器上进行, 没有先后顺序, 1作业J i 的处理时间为t i , 1≤i ≤n , 截止时间为D , 所有t i 和D 都是正整数, 问能把n 项作业分配给这2台机器, 在截止时间D 内完成所有的作业吗?子问题关系子集和是0-1背包的子问题= v i且B = K.限制0-1背包的实例中所有wi双机调度是装箱问题的子问题物品看作作业, 物品的重量是作业的处理时间, 截止时间是每只箱子允许的最大重量.限制箱子数K=2只需证明子集和与双机调度问题的NP完全性构件设计定理子集和是NP完全的.,a2,…,a n}和W={S1,S2,…,S m},证恰好覆盖：有穷集A={a1子集和：非负整数集合X={x,x2,…,x n}及非负整数N.1和N都可表成kn位的二进制数, 这kn位分成n 段, 每每个xj(m+1)⎤. N的每一段的第一位(最右的一位)为1, 段k位, k=⎡log2其余的为0. x对应于子集S. 当a i∈S时, 从左到右x的第i段j j j j的第一位为1, 其余的为0.变换实例n=4, m=3, A={a1,a2,a3,a4}, S1={a1,a2}, S2={a1,a3,a4}, S3={a2}, N=01010101, x1=01010000, x2=01000101, x3=00010000.=01010101=01010000=01000101=00010000存在集和W含A的恰好覆盖⇔存在子集和=N| S j∈U}. 由于A中的每个元U⊆W是A的恰好覆盖, 令T={x设|}中的每一个元j中恰好出现一次, 故对于二进制数的每一段, 素在U的所有Sj中恰好有一个的这一段为00…01, 从而T 中所有在T的所有x01Tj元素之和等于N.反过来, 设X的子集T 中元素之和等于N, 令U={S| x j∈T}. T 中j(m+1)⎤位, 最大值为2k-1 ≥m, 至多有m个数, 每一段有k=⎡log2故T 中的数相加时不会出现段之间的进位. 对于每一段, 在T的所有x中恰好有一个的这一段为00…01, 这意味着每一个a ji 中恰好出现一次, 即U是A的恰好覆盖.在U的所有Sj构造X和N显然可以在多项式时间内完成,010-1背包与伪多项式时间算法定理0-1背包是NP完全的.注意: 0-1背包问题优化形式的动态规划算法, 其时间复杂度意算法度为O(nB), 其中n是物品的个数, B是重量限制. 这不是多项式时间算法, 而是指数时间算法.伪多项式时间算法: 算法的时间复杂度以|I|和max(I)的某个二元多项式p(|I|, max(I))为上界, 其中max(I)是实例I中数的最大绝对值.双机调度与装箱定理 双机调度是 机调度是NP完全的. 证 要证子集和≤p双机调度. 任给子集和实例:非负整数集X={x1, x2,…, xn}及非负整数N, 对应的双机调度实例有n+2项作业J1, J2,…, Jn+2, 处理时间为 x1, x2,…, xn, a, b, 截止时间为D. 要求存在 X 的子集T 使得当 且仅当 N+a = M-N+b=D. 于是, a = -2N+b. 取 b=M +2N, a=2 2M , D=2 2M+N, 其中 M= x1+x2+…+ xn.变换实例子集和实例 X={ 5, 2, 7, 4, 3 }, N=6 子集 T={ 2,4 2 4 }, } 2+4=6 M=21, a=2M=42, b=M+2N=33, D=2M+N=48 双机调度实例 J ={ { J1, J2, J3, J4, J5, J6, J7 } t ={ 5, 2, 7, 4, 3, 42, 33 } D=48 可行调度 J2+J4+J6: 2+4+42=48；J1+J3+J5+J7: 5+7+3+33=4832NPC证明小结证明问题是NP完全的 (1) 证明该问题属于NP. (2) 选好一个已知 选好 个已知NP完全问题变换到该问题, 给出变换规则. (3) 证明肯定实例当且仅当变换到肯定实例. (4) 证明变换时间是多项式的——变换规模是多项式规模. 常用的证明方法 限制法 局部替换法 构件设计法NP完全性理论的应用‡用NP完全性理论进行子问题分析 完全性 论进行子问题分析„ „子问题的计算复杂性 子问题的NP完全性证明 搜索问题 Turing归约 NP-hard, NP-easy‡NP难度„ „ „34子问题的计算复杂性NPC?P 努力扩大已知区域，缩小未知区域 当P≠NP时，存在不属于NPC也不属于P的问题35有先行约束的多处理机调度问题‡优化问题: 给定任务集 T, m 台机器,∀t∈T, l(t)∈Z+, T上的偏序‫ط‬. 若σ:T→{ 0, 0 1 1, … , D }满足下述条件,则称 T 为可行调度. (1) ∀t∈T, σ(t)+l(t)≤D (2) ∀i, 0 ≤ i≤ D, | { t∈T : σ(t) ≤ i < σ(t)+l(t) }| ≤ m (3) ∀t, t’∈T, t ‫ ط‬t’⇔ σ(t)+l(t) ≤ σ(t’) 求使得 D 最小的可行调度. 条件说明： 任务在截止时间前完成 同时工作的台数不超过 m 有偏序约束的任务必须按照约束先行36‡实例任务集如图 m=2, 求使得 D 最小的可行调度.t611 1 1t522t4t3t2t1t6 t5 t4 t6 t5 t3t4t2 ∅ t2 t3 ∅ t1t1 D=6 6D=537对应的判定问题实例：任务集 实例 任务集T, m台机器,∀t∈T, l(t)∈Z+,T上的偏序‫ط‬, 截止时间 D∈Z+. 问 是否存在小于等于 D 的可行调度？ 问：是否存在小于等于 的 行调度 子问题通过限制参数(机器数、工作时间、偏序)构成 参数 偏序 m大小 l 大小 ∅ l 为常数 限 制 树 任意 m 任意 l 任意38m ≤1, 2, … , 某个常数调度问题的子问题结构从上到下：偏序任意、树形偏序、无偏序约束 从左到右：处理器台数限制逐步放大 从前到后：各任务等长工作时间、任意工作时间l 任意 ≺ l=1任意 为树≺≺ =∅m=1m≤2m≤3m≤Mm任意39某些子问题属于Pm =1, 1 l 任意, 任意 偏序任意算法： 1 计算所有任务的工作时间之和 Time 1. i 2. if Time ≤ D,存在可行调度. 3 按照偏序从高层依次取任务，进行安排即可 3. 按照偏序从高层依次取任务 进行安排即可.m 任意, l 为常数, 偏序为空算法： 1. Time ←⎡|T|/m⎤ l 2. if Time ≤ D,存在可行调度. 3. 将任务按顺序依次分配到 m 台机器上.40某些子问题属于Pm任意，l 为常数，偏序为树关键路径算法：1.按照偏序关系，从树叶依次拿任务，每次至多下移m 个结点.2.将分配次数与D比较,如果不超过D, 回答Yes.分配次数至少为树高,可以证明时间为多项式时间.m=2, 偏序任意, l 为常数算法：H.N.Gabow,An almost linear algorithmfor two processors scheduling, J.Assoc.Comput.Math,29, 1982, 766-780.41术语简介极大多项式可解（加绿圈）的子问题π：（加绿圈）π是多项式时间可解的,并且不存在其他多项式’’的子问题可解的子问题π,使得π是π的子问题.极小NP完全的子问题π（加篮圈）π是NP完全的，并且不存在其他NP完全的子问题π’使得π’是π的子问题.极小未解决的子问题π：（加红圈）π的子问题都属于P, 但不知π是否属于P，也不知P是否属于NPC.极大未解决的子问题π: (加粉圈)π的父问题都是NP完全的，但不知π是否属于P，也不知P是否属于NPC.42NP完全子问题的证明许多子问题的NP完全性证明采用局部替换法.以图论为例，平面性限制，顶点度数限制等形成子问题.以顶点度数D 为例，子问题分析如下：问题P NPCVC D≤2D≥3HC23顶点三着色34反馈顶点集23团给定D任意43Turing 归约多项式时间的Turing 归约：设π, π是搜索或优化问题，A 是利用解π2的假想子程序s 12 2 解π1的算法，且只要s 是多项式时间的，A 也是多项式时间2.的，则称算法A 是从π1到π2 的多项式时间的Turing 归约. 这是也称π1 Turing 归约到π2，记作π1∝T π2.判定问题是搜索问题特例，多项式变换等价于Turing 归约. 对于判定问题π，若I 属于Y π, 则S π[I ]={ Yes }, 若I 属于D −Y , 则S I ]={ No }.44ππ,π[]{}图灵归约的性质传递性π1∝T π2，π2∝T π3⇒π1∝T π3多项式变换是Turing 归约的特例.设π多项式变换到π, 如下设计解π1的算法A ：12, 1 1. 对于π1的任何实例I ，先将I 变换成π2实例I’,22I’2. 利用解π2 的假想子程序s 对I 识别.3. 如果I’是肯定实例，则I 也是肯定实例；4是否定实例则I 4. 如果I’是否定实例，则I 也是否定实例.易见只要s 是多项式时间的，则A 也是多项式时间的. 45因此π1∝T π2.T iTuring归约的应用证明许多NPC 问题所对应的优化或构造问题为NP-hard. 证明某些非NP 类的判定问题是NP-hard说明:将解对应优化问题或构造问题的算法作为解判定问题算法的子程序，得到解判定问题的算法，从而构造了从判定问题到对应优化问题或构造问题的Turing归约.证明某些NPhard问题是NP等价的46NP等价证明：货郎问题等价证明货郎问题例1 货郎问题（TSO）是NP等价的.证：易证TSO是NP-hard. 下面证明TSO 是NP-easy.引入中间问题：货郎问题的延伸问题（TSE）TSE实有市集实例：有穷城市的集合C= { c, c2, … , c m}1, c j∈C, d(c i, c j)∈Z+,距离∀ci长度限制B∈Z+,部分旅行路线ϑ= < c, … ,cπ(k) >π(1)问：ϑ是否可以延伸成全长不超过B的全程旅行问< cπ(1), … , cπ(k), cπ(k+1), … , cπ(m)>?易证TSE属于NP.NP47TSO 到TSE 的图灵归约设s (C ,d ,ϑ,B )是解TSE 的子程序，其中C 为城市集，d 为距离函数，ϑ为部分旅行，B 为长度限制.下面构造解TSO 的算法.思路：用二分法确定最短路旅行长度B *旅行长度界于m →m ×d , d = max{ d (c i , c j )}每次取中点值验证是否存在能延伸到此长度的旅行根据最小长度值B *确定旅行路线开始依次检查><>从c 1开始，依次检查<c 1,c 2>,<c 1,c 3>…是否能延伸到B *长度的旅行，选择第一个可延伸的顶点c i . .48按照上面方法确定后面的其他顶点.算法MinLength设S的子程序其中s(C,d,ϑ,B)是解TSE 的子程序，其中C为城市集，d为距离函数，ϑ为部分旅行，B为长度限制.算法Minlength（二分法确定最短旅行长度B*）令min,max{(i,j)i,j}1. B←m, B←m⋅max{ d c c): c, c∈C2. 若B max−B min=1, 则B*←B max, 结束3.i3. B←[(B min+B max)/2]4. s(C,d,<c1>,B)5. 若回答Yes”, B max←B, 否则B min←B5若回答”Yes”6．转2.49算法图示B min =m B max =md B=(B min +B max )/2Yes B min =m B max =B i =B =md No B min B B max md 50B min B*=B max return。