算法笔记——回溯法解决旅行员售货与圆排列问题

1、旅行员售货问题

问题描述

该售货员负责前往多个城市进行商品推销。各城市间的路程（即旅费）已知后，则该售货员需要寻找从驻地出发、遍历每个城市的单次路径并最终返回驻地的最短回路。以确保总行程最短。

** 问题分析**

将旅行售货员问题视为一棵排列树的可能性，并将其解空间视为对应的一棵排列树。在初始化阶段x=[1: n]时，则相应的解空间由x[1:n]的所有可能置换构成。这种回溯法类似于遍历所有可能置换的过程。

在递归算法Backtrack运行至i取到n值时的情形下（即当前扩展节点位于排列树的叶节点层的上一层位置），算法首先会检查图G中是否存在连接顶点x[n-1]与x[n]的一条边以及连接x[n]与顶点1的一条边。如果上述两条边均存在，则确定了一条完整的回路路径。接下来，在确认该回路的有效性后（即判断其费用bestc是否为当前最优），还需进一步评估这条回路费用与已知最优解对应费用之间的关系：如果新回路费用更低，则必须更新当前最优值bestc以及对应的最优解bestx参数设置为新的更低值。

假设给定整数i满足条件i < n，则当前生成节点位于排列树中的第(i−1)层