7-14 旅行商问题（旅行商问题公式）

7-14 旅行商问题

旅行商问题公式

旅行商问题（Traveling Salesman Problem，TSP）是一个经典的组合优化问题。目标是寻找一条经过所有城市且每个城市只经过一次的醉短路径，醉后返回出发点。

设有n个城市，编号为1, 2, ..., n。设城市之间的距离矩阵为D，其中D[i][j]表示从城市i到城市j的距离。设x[i][j]为0或1，当且仅当从城市i到城市j的路径被选择时，x[i][j]为1。TSP的目标函数可以表示为：

min ∑_{i=1}^{n} ∑_{j=1}^{n} D[i][j] * x[i][j]

约束条件如下：

1. 每个城市必须有且仅有一个进入和一个离开的路径，即对于每个i，∑_{j=1, j≠i}^{n} x[i][j] = 1，且∑_{j=1, j≠i}^{n} x[j][i] = 1。

2. 不能从同一个城市出发两次，即对于每个i，∑_{j=1}^{n} x[i][j] = 1。

3. 城市之间的路径必须是连续的，即对于每个i，∑_{j=1}^{n} x[i][j] = 1。

旅行商问题的求解方法有很多，包括暴力搜索、动态规划、遗传算法、模拟退火等。