给定n个城市集合C=cC从一个城市到另外一个城市的距离di为正整数求一条最短且每个城市恰好经过一次的巡回路线。 15分解向量o=1iiiz··i-显式约束巡回路线从1开始;iizin-1为23n的一个排列搜索空间排列树结点itizin已得到步路线界函数当前得到的最短全程巡回路线长度初始值为00现有货郎问题的一个实例如右图所示顶点代表城市边上的权代表城市间的距离要求1使用回溯法或者分支限界法求解TS

1. 设计限界函数：

• 最小花费限界函数：对于任意一个将要扩展的节点，计算当前节点到起始节点的距离和已经经过的节点到起始节点的最小距离之和，如果该和大于当前已经找到的最短路径长度，则剪枝。
• 最小剩余距离限界函数：对于任意一个将要扩展的节点，计算当前节点到起始节点的距离和未经过的节点到起始节点的最小距离之和，如果该和大于当前已经找到的最短路径长度，则剪枝。
• 最小花费加最小剩余距离限界函数：对于任意一个将要扩展的节点，计算当前节点到起始节点的距离和已经经过的节点到起始节点的最小距离之和，再加上未经过的节点到起始节点的最小距离之和，如果该和大于当前已经找到的最短路径长度，则剪枝。

2. 状态空间树如下所示：

          1
       /  |  \
      2   3   4
    / | \ | \ | \
   3  4  2  5  6

节点处的限界函数值如下所示：

• 节点1：限界函数值为0，当前界值在节点1处更新。
• 节点2：限界函数值为5，当前界值在节点2处更新。
• 节点3：限界函数值为6，当前界值在节点3处更新。
• 节点4：限界函数值为8，当前界值在节点4处更新。
• 节点5：限界函数值为8，当前界值在节点5处更新。
• 节点6：限界函数值为8，当前界值在节点6处更新。

3. 执行了剪枝操作的结点处，及执行剪枝的依据：

• 节点5执行了剪枝操作，因为节点5的限界函数值为8，大于当前已经找到的最短路径长度6。
• 节点6执行了剪枝操作，因为节点6的限界函数值为8，大于当前已经找到的最短路径长度6。

4. 该问题实例的最优解为1->2->3->4->1，总路径长度为6