题目概述
输入
输入数据包含多行。
第一行包含一个整数N(2 < N ≤ 16)，代表伟大航路上一共有N个岛屿（包含起点的罗格镇和终点的拉夫德鲁）。其中，起点的编号为1，终点的编号为N。
之后的N行每一行包含N个整数，其中，第i(1 ≤ i ≤ N)行的第j(1 ≤ j ≤ N)个整数代表从第i个岛屿出发到第j个岛屿需要的时间t(0 < t < 10000)。第i行第i个整数为0。
输出
输出为一个整数，代表路飞一行从起点遍历所有中间岛屿（不重复）之后到达终点所需要的最少的时间。
样例输入
5
0 18 13 98 8
89 0 45 78 43
22 38 0 96 12
68 19 29 0 52
95 83 21 24 0
样例输出
137
提示
对于样例输入：可能的路径及总时间为：
1,2,3,4,5: 18+45+96+52=211
1,2,4,3,5: 18+78+29+12=137
1,3,2,4,5: 13+38+78+52=181
1,3,4,2,5: 13+96+19+43=171
1,4,2,3,5: 98+19+45+12=174
1,4,3,2,5: 98+29+38+43=208
所以最短的时间花费为137
单纯的枚举在N=16时需要14!次运算，一定会超时。
DP算法分析
这道题感觉上像是DP，但是我总也想不出个具体的转移方程。
以下摘录网上别人的代码和想法。
内存2576kb，时间24ms。
- 受到限制的有集合中元素，和最后到达的地点，与之前的顺序无关，最后从1到n也与2到n-1的顺序无关
- 考虑状态压缩，先处理1到n-1结点，最后处理中间部分结点到n结点 d[S][i]=min(d[S][i],d[S-(1<< i)][j]+dist[j][i]);
#include<cstdio>
#include<climits>
#include<iostream>
using namespace std;
#define N 17
int d[1<<N][N],dist[N][N];
int n,i,j,S,ans;bool f;
int main(){
scanf("%d",&n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&dist[i][j]);
n-=2;
for(int i=0;i<n;i++) d[(1<<i)][i]=dist[0][i+1];
for(S=0;S<(1<<n);S++){
for(i=0;i<n;i++) if(S==(1<<i)) f=true;
if(f) {f=false;continue;
}
for(i=0;i<n;i++) d[S][i]=INT_MAX/2;
for(i=0;i<n;i++){
if(S&(1<<i)){
for(int j=0;j<n;j++){
if(i==j) continue;
if(S&(1<<j))
d[S][i]=min(d[S][i],d[S-(1<<i)][j]+dist[j+1][i+1]);
}
}
}
}
ans=INT_MAX,S=(1<<n)-1;
for(int i=0;i<n;i++) ans=min(ans,d[S][i]+dist[i+1][n+1]);
printf("%d",ans);
return 0;
}
DFS算法分析
实际上，在作业中老师把他归到搜索的题目，所以我就想到了用DFS。然而我的代码比较拙劣，TLE了。
又搜索相关剪枝策略，贴上别人的代码。关键的部分在于以下这个nposition数组记录了[1~po][选择方式]的最优解，可以减除大量无关解。
内存2088kb，时间76ms。
#include<cstdio>
#include<string.h>
#include<stdlib.h>
#include<math.h>
const int inf = 0x3f3f3f3f;
int step;
int minstep;
int a[16][16];
int book[15];
int postion[20];
int n;
int npostion[15][1<<15];
int po;
void dfs(int cur,int qc)
{
if(cur+2==n)
{
step+=a[qc][n-1];
if(step<minstep)
minstep=step;
step-=a[qc][n-1];
return;
}
for(int i=1; i<n-1; i++)
{
if(!book[i])// has been through
{
if(step>=minstep)
continue;
if((npostion[i][po+postion[i-1]]<=step+a[qc][i]))
continue; //重要剪枝语句，我把这一句写在for前面便导致超时了
po+=postion[i-1];
step+=a[qc][i];
npostion[i][po]=step;
book[i]=1;
dfs(cur+1,i);
po-=postion[i-1];
book[i]=0;
step-=a[qc][i];
}
}
}
int main()
{
for(int i=0; i<14; i++)
postion[i]=1<<i;
while (~scanf("%d",&n))
{
po=0;
step=0;
minstep=1e17;
memset(npostion,inf,sizeof(npostion));
memset(a,0,sizeof(a));
memset(book,0,sizeof(book));
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
scanf("%d",&a[i][j]);
dfs(0,0);
printf("%d\n",minstep);
}
return 0;
}
个人解法
在上面代码的指导下，我优化了一下自己的，终于通过了。
我加入了一个新的剪枝：当前的sum如果加上最小的可能（代码中实现为cut数组）超过了minimum的话则return（上边的代码是当前sum>=minimum则return），并且把step作为一个全局变量来用了。
内存1444kb，时间39ms。内存是DP的一半，时间是DP的两倍，还可以。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<bitset>
using namespace std;
#define INF 0x3f3f3f3f
int cost[20][20];
int brune[20][(1<<14)+5];
int cut[20]={0},pos[20]={0};
bitset<20>visit;
int minimum=INF;
int n,sum=0,step=1,state=0;
void f(int k){
if(sum+cut[n-step]>minimum)
return; //加上最小可能都超过最小值的话则返回
if(step==n-1){
minimum=min(sum+cost[k][n],minimum);
return;
}
for(int i=2;i<n;++i){
if(visit[i]==0){
if(sum+cost[k][i]>=brune[i][state+pos[i]])
continue; //注意是“>=”,最优解肯定是小于等于此的
brune[i][state+pos[i]]=sum+cost[k][i];
visit[i]=1;
sum+=cost[k][i];
++step;
state+=pos[i];
f(i);
--step;
state-=pos[i];
sum-=cost[k][i];
visit[i]=0;
}
}
}
int main(){
cin>>n;
int b[20];
memset(brune,INF,sizeof(brune));
memset(b,INF,sizeof(b));
for(int i=1;i<=n;++i){
pos[i]=(1<<i);
for(int j=1;j<=n;++j){
cin>>cost[i][j];
if(cost[i][j]!=0)
b[i]=min(b[i],cost[i][j]);
} }
sort(b+1,b+n+1);
for(int i=1;i<=n;++i){
cut[i]=b[i]+cut[i-1]; //还剩i个岛时至少还要再加上cut[i]的时间
}
visit[1]=1;
state=2;
f(1);
cout<<minimum;
}
总结
能尽早剪枝就剪除，留到下一步很可能就爆炸。
注意大于号和大于等于号的实际意义。
这一题大于等于就可以跳出，否则将超时。
早日掌握DP算法。
DFS的代码有点儿长，主要是全局变量挺多，有点冗余。
应该还有更精巧的DFS代码，有待发现。
网友评论