旅行商问题——状态压缩DP
问题简介
有n个城市,每个城市间均有道路,一个推销员要从某个城市出发,到其余的n-1个城市一次且仅且一次,然后回到再回到出发点。问销售员应如何经过这些城市是他所走的路线最短?
用图论的语言描述就是:给定一个权值为正数的赋权完全图,求各边权值和最小的哈密尔顿回路。
这个问题就是著名的旅行商问题(TSP,Traveling Salesman Problem),TSP问题是NP问题,没有已知的多项式时间的高效算法可以解决之一问题。问题在1930年首次被形式化,并且是在最优化中研究最深入的问题之一,许多优化方法都用它作为一个基准,例如动态规划,最邻近法,插入法,模拟退火算法,遗传算法,神经网络算法等。
经典应用实例
印制电路板转孔
在一块电路板上打成百上千个孔,转头在这些孔之间移动,要求移动的距离之和最小。把这个问题转化为TSP,孔相当于城市.孔到孔之问的移动时间就是距离,转头的移动距离之和就是一次巡回的距离
生产安排
假设要在同一组机器上制造n种不同的产品,生产是周期性进行的,即在每一个生产周期这n种产品都要被制造。要生产这些产品有两种开销,一种是制造第i种产品时所耗费的资金(1≤i≤n),称为生产成本,另一种是这些机器由制造第i种产品变到制造第j种产品时所耗费的开支cij称为转换成本。显然,生产成本与生产顺序无关。于是,我们希望找到一种制造这些产品的顺序,使得制造这n种产品的转换成本和为最小。由于生产是周期进行的,因此在开始下一周期生产时也要开支转换成本,它等于由最后一种产品变到制造第一种产品的转换成本。于是,可以把这个问题看成是一个具有n个结点,边成本为cij图的货郎担问题。
代码实现
给定一个n个顶点组成的带权有向图的距离矩阵d(i,j)(INF表示没有边)。要求从顶点0出发,经过每个顶点恰好一次后再回到顶点0.问所经过的边的总权重的最少值是多少?(2≤n≤15),(0≤d(i,j)≤1000).
分析:
虽然TSP是NP困难的,不过在程序设计竞赛中还是有可能出现这种范围较小的题目。
所有可能的路线共有(n-1)! 种,这是一个非常大的值,即使在本题n已经很小,仍无法试遍每一种情况。对于这个问题,我们可以用DP来解决。
假设现在已经访问过的顶点的集合(起点0当作还未访问过的顶点)为S,当前所在的顶点为v,用d[S][v]表示从顶点v出发访问剩余的所有顶点,最终回到顶点0的路径的权重之和最小的路径。
已经访问过的集合S如何表示?由于S是有基数最大为n的集合,所以可以用n为二进制来表示集合,把每一个元素的选取与否对应到一个二进制位中,从而状态压缩成一个整数,像这种针对集合的DP我们一般叫做状态压缩DP。
时间复杂度O(2nn2)(2n * n种状态,每种状态有n种选择)。
代码:
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std; const int INF = 0x3f3f3f3f;
const int maxn = ;
int n,m,G[maxn][maxn];
int d[ << maxn][maxn]; //记忆化搜索使用的数组 //已经访问过的节点集合为S,当前位置为v
//用d[S][v]从v出发访问剩余的所有顶点,最终回到顶点0的路径的权重总和的最小值
int dp(int S, int v)
{
int& ans = d[S][v];
if (ans >= ) return ans; //已经求出来了,直接返回
if (S == ( << n) - && v == ) return ans = ; //已经访问过所有节点并回到0号点
ans = INF;
for (int u = ; u < n; u++) if ((!((S >> u) & )) && G[v][u])
ans = min(ans, dp(S | ( << u), u) + G[v][u]);
return ans;
} void solve()
{
//memset(G, INF, sizeof(G));
memset(d, -, sizeof(d));
printf("%d\n", dp(, ));
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n,&m);
for (int i = ; i < m; i++)
{
int u, v,w;
scanf("%d%d%d", &u, &v,&w);
G[u][v] = w;
}
solve();
}
return ;
}
对于不是整数的情况,很多时候很难确定一个适合的递推顺序,因此使用记忆化搜索可以避免这个问题。不过在这个问题中,对于任意两个整数i,j,如果它们对应的集合满足S(i) ⊆ S(j),就有i ≤ j。所以这题还可以用循环求出答案。
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std; const int INF = 0x3f3f3f3f;
const int maxn = ;
int n, m, G[maxn][maxn];
int d[ << maxn][maxn]; //记忆化搜索使用的数组 void solve()
{
//用足够大的值初始化数组
for (int S = ; S < ( << n); S++)
fill(d[S], d[S] + n, INF);
d[( << n) - ][] = ; //根据递推式依次计算
for (int S = ( << n) - ; S >= ; S--)
for (int v = ; v < n; v++)
for (int u = ; u < n; u++)
if ((!(S >> u & )) && G[v][u])
d[S][v] = min(d[S][v], d[S | << u][u] + G[v][u]);
printf("%d\n", d[][]);
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
for (int i = ; i < m; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
G[u][v] = w;
}
solve();
}
return ;
}
参考链接:
https://baike.baidu.com/item/NP完全问题/4934286?fr=aladdin
https://baike.baidu.com/item/旅行商问题/7737042?fr=aladdin
https://baike.baidu.com/item/%E8%B4%A7%E9%83%8E%E6%8B%85%E9%97%AE%E9%A2%98
最新文章
- 2016HUAS_ACM暑假集训3F - Jungle Roads
- jQuery Filterizr 筛选过滤
- NFine的后台源码
- BZOJ3295 [Cqoi2011]动态逆序对
- Nazo解密游戏攻略
- java+hadoop+spark+hbase+scala+kafka+zookeeper配置环境变量记录备忘
- 使用Python,字标注及最大熵法进行中文分词
- 我的CSS 入门1
- MySQL慢查询日志汇总
- 【java提高】---queue集合
- Linq使用Group By
- Javascript中用来实现继承的几种方式
- SAP WM 有无保存WM Level历史库存的Table?
- BZOJ2288 生日礼物
- 论文阅读笔记三十九:Accurate Single Stage Detector Using Recurrent Rolling Convolution(RRC CVPR2017)
- Maven - 实例-6-聚合与继承
- Haskell语言学习笔记(82)Extensible effects
- IntelliJ IDEA windows与mac下常用快捷键
- 怎样让孩子爱上设计模式 —— 7.适配器模式(Adapter Pattern)
- sqoop 常见错误以及处理方式
热门文章
- struts2通用标签
- 《Eye In-Painting with Exemplar Generative Adversarial Networks》论文阅读笔记
- E20170404-gg
- C++笔试题库之编程、问答题 150~200道
- Codeforces Round #422 (Div. 2)D. My pretty girl Noora(递推+数论)
- java 发送get,post请求
- Unity陀螺仪
- 当打开一个.h或.cpp文件时, Solution Explorer就自动展开文件所在的目录
- bzoj 1060: [ZJOI2007]时态同步【树形dp】
- P1648 看守