用分支限界法求TSP ■TSP是求排列的问题,不是仅找一条路径而已 因而需要对分支限界法的一般算法作些修改: (1)待扩展的结点如果在本路径上已经出现,则 不再扩展,但若是在其他路径上出现过,则仍 需要扩展。 (2)新结点,无论其优劣,既不影响其它路径上 的结点,也不受其它路径上的结点的影响。 (3)依据上界函数决定结点是否可以剪去。 2021/221 计算机算法设计与分析 92021/2/21 计算机算法设计与分析 9 用分支限界法求TSP ◼ TSP是求排列的问题，不是仅找一条路径而已。 因而需要对分支限界法的一般算法作些修改： ◼ (1)待扩展的结点如果在本路径上已经出现，则 不再扩展，但若是在其他路径上出现过，则仍 需要扩展。 ◼ (2)新结点，无论其优劣，既不影响其它路径上 的结点，也不受其它路径上的结点的影响。 ◼ (3)依据上界函数决定结点是否可以剪去