旅行商问题 | 回溯：N排列（最小剪枝）

秒速五厘米 2023-03-13 05:59 2阅读 0赞

> **旅行推销员问题**（**TSP**）：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。
> 
> 它是[组合优化][Link 1]中的一个[NP][]难问题~

--------------------

###  一、思路 ###

回溯算法就是梳理好、有顺序、合理地进行全遍历。很明显，TSP 经过不同城市各一次，选择每个城市的经过顺序对于回路的总路程是有影响的。所以 TSP 问题的解空间是全体排列，那么我们需要遍历所有点的排列情况。

对于需要遍历 n 个点的排序情况，我们需要选择 n - 1 次，为此我们可以建立一棵很形象的 **排列决策树**：在树的第 i 层即是对第 i

个位置的选择，其应该有 (n - i + 1) 种选择范围。比如下面是对数字 123 的所有排列遍历的决策树：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70][]

--------------------

### 二、伪代码实现 ###

假设初始所有的数字无序地存储在 x 数组中。决策树中第 i 层即是对第 i 位的选择，在遍历到第 i 层时， 1~ i - 1 位的数字已经确定（存在 x 数组中），故我们第 i 层的选取只能在 x\[ i \] ~ x\[n\] 中。

这里其实带了**最小问题的剪枝操作**：只有当前的值小于已经记录的最小情况时，我们才继续下一层搜索。

backtrack(int t) {  //搜索树的第t层：确定第 t 位的选择
        if(t > n) {
            //遍历的终点
            return;
        }
        for i = t : n
            change x[i] and x[t]  //选则第 i个数为 第 t 位
            if 满足限制条件和界限条件
                backtrack(t + 1)  //继续选择下一位
            change x[i] and x[t]  //换回来哦
    }

[Link 1]: https://baike.baidu.com/item/%E7%BB%84%E5%90%88%E4%BC%98%E5%8C%96/3314860
[NP]: https://baike.baidu.com/item/NP/7470332
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: /images/20230312/e02af2322ff04e9784430fdf50475688.png