示例3:旅行商问题 20 FIFO分支定界 E节点活节点表 (B BCDE EFG E FGHIJK F路径12341,59 2LG路径12431,66 ①的的@⑨团路径13241,25 路径1342,不展开 J路径14231,25 路径1432,不展开 2021/2/6
示例3：旅行商问题 • FIFO分支定界 E-节点 活节点表 B C D E F G C D E E F G H I J K F 路径12341，59 G 路径12431，66 H 路径13241，25 I J K 路径1342，不展开 路径14231，25 路径1432，不展开 2021/2/6 11
再解示例3:最小耗费法Q 4 10 使用最小堆存储活节点 20 E节点活节点表 E E DJKC DHJ KIC H路径13241, 定界函数如果一个 2 点的定界值不比当事 优行围小,则将 删除而不被感开 2021/2/6
再解示例3：最小耗费法 • 使用最小堆存储活节点 E-节点 活节点表 B E D C E D J K C D H J K I C H 路径13241，25 【定界函数】如果一个 节点的定界值不比当前 最优旅行更小，则将被 删除而不被展开！ 2021/2/6 12
最小耗费分支定界小结 定界函数确定最小耗费的下限;如果一个节点的定界值 不比当前最优旅行更小,则将被删除而不被展开 节点取出策略:使节点按照它们耗费的定界函数值的非 降序从最小堆中取出 2021/2/6
最小耗费-分支定界小结 • 定界函数确定最小耗费的下限；如果一个节点的定界值 不比当前最优旅行更小，则将被删除而不被展开 • 节点取出策略：使节点按照它们耗费的定界函数值的非 降序从最小堆中取出 2021/2/6 13
分支定界法小结 设计定界函数的原则:利用最少的时间,在内存允许范 围内去解决问题 好的定界函数:一个能够有效地减少计算时间,并因此 使产生的节点数目也减少 通过产生具有最少节点的树来解决问题并不是根本的目 标 2021/2/6
分支定界法-小结 • 设计定界函数的原则：利用最少的时间，在内存允许范 围内去解决问题 • 好的定界函数：一个能够有效地减少计算时间，并因此 使产生的节点数目也减少 • 通过产生具有最少节点的树来解决问题并不是根本的目 标 2021/2/6 14