归本程上太军 实例分析一0-1背包问题 SHANDONG UNIVERSITY OF TECHNOLOGY 华器会空空合安会器会的会路 n=3,c=30,Ww=[16,15,15],p=[45,25,25] ●队列式分支限界法： [A]B,C=>B,C [B,C]D,E=>E [C,E]F,G=>F,G [E,F,G]J,K=>K(45)[1,0,0] c [E,G]L,M=>L(50)[0,1,1]M(25) 0 0 [G]N,0=>N(25),O(0) G 不搜索以不可行结，点为根的子树 ● 优先队列式分支限界法： [A]B,C=>B(45),C(0) [B,C]D,E=>E(45) [E,C]J,K=>K(45)[1,0,0] [C]F,G=>F(25),G(0) [E,G]L,M=>L(50),[0,1,1]M(25) [G]N,O=>N(25),O(0) 202马醒尊枝函数加速搜索 16
2025 年 4 月 3 日 16 实例分析－ 0 - 1背包问题 n=3, c=30, w=[16,15,15], p=[45,25,25] ⚫ 队列式分支限界法： [A] B, C => B, C [B, C] D, E => E [C, E] F, G => F, G [E, F, G] J, K => K(45) [1,0,0] [F, G] L, M =>L(50) [0, 1, 1] M(25) [G] N, 0 =>N(25), O(0) 不搜索以不可行结点为根的子树 ⚫ 优先队列式分支限界法： [A] B, C => B(45), C(0) [B, C] D, E => E(45) [E, C] J, K => K(45) [1, 0, 0] [C] F, G => F(25), G(0) [F, G] L, M => L(50), [0, 1, 1] M(25) [G] N, O => N(25), O(0) ⚫ 可用剪枝函数加速搜索
山东程子太军 1.5实例一T$P问题 SHANDONG UNIVERSITY OF TECHNOLOOY 会是33✉ 30 问题描述：某售货员 6 要到若干城市去推销 4 3 商品，一直各城市之 20 间的路程，他要选定 一条从驻地出发，经 过每个城市一遍，最 2 B 后回到住地的路线， E 使总的路程最短。 2 2 3 4 2025年4月3日 17
2025年4月3日 17 1.5 实例－TSP问题 1 2 3 4 20 6 30 5 4 10 A B C D E F G H I J K L M N O P Q 1 2 3 4 3 4 4 3 4 2 3 2 2 4 2 3 问题描述：某售货员 要到若干城市去推销 商品，一直各城市之 间的路程，他要选定 一条从驻地出发，经 过每个城市一遍，最 后回到住地的路线， 使总的路程最短
归东程子末军 分支限界法解旅行售货员问题 SHANDONG UNIVERSITY OF TECINOLOGY FFO队列： 活结点队列： } B 2 U C D 3 4 2 A 2 3 30 2 5 F G H 6 10 4 3 A 3 4 59 66 25 66 25 59 20 M
分支限界法解旅行售货员问题 1 2 3 4 30 20 6 10 5 4 FIFO队列： 活结点队列： { } B C D E F G H I J K L M N O P Q 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 59 66 25 66 25 59 {F,G,H,I,J,K } {E,F,G,H,I } {C,D,E } {D,E,F,G} {G,H,I,J,K } {H,I,J,K } {I,J,K } {J,K } {K } { }
G 山东程子太军 分支限界法解旅行售货 问题 最小费用优先队列： 活结点队列： } B 2 3 C 30 D 6 E 3 2 4 2 3 30 2 35 40 11 26 14 24 5 G H 6 10 3 3 2 4 59 66 25 66 25 59 20 N
分支限界法解旅行售货员问题 1 2 3 4 30 20 6 10 5 4 最小费用优先队列： 活结点队列： { } B C D E F G H I J K L M N O P Q 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 30 6 4 35 40 11 26 14 24 59 66 25 66 25 59 {E,D,C } {D,J,K,C } {H,J,K,I,C } {J,K,I,C } {K,I,C } {F,G } {I,C } {G }C { }
归东程子末军 实例分析一TSP问题 SHANDONG UNIVERSITY OF TECINOLOGY ● 队列式分支限界法： [B]C,D,E 30 [C,D,E]F,G [D,E,F,G]H,I 6 10 [E,F,G,H,I]J,K 4 3 4 [E,G,H,1,J,KL(59)[1,2,3,4,1] 20 [G,H,I,J,KM(66) [但I,J,KN(25)[1,3,2,4,1] A [L,J,K灯1-3-4(26) [u,K灯P(25) 2 B [K☒Q(59) D ● 优先队列式分支限界法： [B]C,D,E=>C(30),D(6),E(4) 3 4 2 4 2 [E,D,C]J,K=>J(14),K(24) F H ① K [D,J,K,C]H,I=>H(11),I(26) 4 3 2 3 2 [世，J,K,I,C]N=>N(25)[1,3,2,4,1] [,K,1,C]P=>P(25) ① M W P [K,1,C]Q=>Q(59) 山，C]l,C被限界掉 2025年4月3日 20
2025年4月3日 20 实例分析－TSP问题 ⚫ 队列式分支限界法： [B] C, D, E [C, D, E] F, G [D, E, F, G] H, I [E, F, G, H, I] J, K [F, G, H, I, J, K] L(59) [1,2,3,4,1] [G, H, I, J, K] M(66) [H, I, J, K] N(25) [1, 3, 2, 4,1] [I, J, K] 1-3-4(26) [J, K] P(25) [K] Q(59) ⚫ 优先队列式分支限界法： [B] C, D, E => C(30), D(6), E(4) [E, D, C] J, K => J(14), K(24) [D, J, K, C] H, I => H(11), I(26) [H, J, K, I, C] N => N(25) [1, 3, 2, 4,1] [J, K, I, C] P => P(25) [K, I, C] Q => Q(59) [I, C] I, C 被限界掉 1 2 3 4 20 6 30 5 4 10 A B C D E F G H I J K L M N O P Q 1 2 3 4 3 4 4 3 4 2 3 2 2 4 2 3