动态规划特训：旅行商问题（回溯法或记忆搜索法）

发布时间：2024-11-12 05:26

解题思路：可以设定一个集合s表示还未访问的城市，i表示现在所在的城市，状态转移至任一还未访问的城市，转移方程为：dp[i][s]=min(dis[i][j]+dp[j][s^1<<j]);而回溯法比较直观，这里直接给出代码。

题目大意：有n个城市，两两之间均有道路直接相连。给出所有道路的长度（矩阵形式）。求一条经过每个城市一次且仅一次，最后回到起点的路线，使得经过的道路总长度最短。N<=15,城市编号为1-n。

输入:

0 3 6 7

5 0 2 3

6 4 0 2

3 7 5 0

0 8 5 6

6 0 8 5

7 9 0 5

9 7 8 0

输出:

记忆搜索法：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define inf 1<<30

int dp[21][1<<21],n,dis[21][21];

int f(int nowp,int s)

{

if(s==1) //这里不是0！集合所有数都去掉后为1！！因为集合编号从1开始，而非从0

{

if(nowp==1) //回到1为需要的终点

return 0;

else return inf; //否则返回无穷被丢弃

}

for(int i=1;i<=n;i++)

{

if(s&