注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

长风明志的博客

不要也不能做下一个谁,应该且可以做第一个自己

 
 
 

日志

 
 

【POJ 2404】Jogging Trails(状态压缩动态规划算法)  

2013-03-29 22:03:24|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 1920Accepted: 761

Description

Gord is training for a marathon. Behind his house is a park with a large network of jogging trails connecting water stations. Gord wants to find the shortest jogging route that travels along every trail at least once.

Input

Input consists of several test cases. The first line of input for each case contains two positive integers: n <= 15, the number of water stations, and m < 1000, the number of trails. For each trail, there is one subsequent line of input containing three positive integers: the first two, between 1 and n, indicating the water stations at the end points of the trail; the third indicates the length of the trail, in cubits. There may be more than one trail between any two stations; each different trail is given only once in the input; each trail can be travelled in either direction. It is possible to reach any trail from any other trail by visiting a sequence of water stations connected by trails. Gord's route may start at any water station, and must end at the same station. A single line containing 0 follows the last test case.

Output

For each case, there should be one line of output giving the length of Gord's jogging route.

Sample Input

4 5
1 2 3
2 3 4
3 4 5
1 4 10
1 3 12
0

Sample Output

41
这题还是有点难度的,跟中国邮递员问题很像。
题意:Gord在为一场马拉松做准备,他家后面有一个公园,公园里有许多路径,这些路径连接了水上景点(n<=15)。Gord训练的时候想走遍所有的路径至少一次(从任意一个节点出发),问她所需要走的最短路程是多长。
中国邮递员问题邮递员从邮局出发送信,要求对辖区内每条街,都至少通过一次,再回邮局,而且其间要选择一条最短路线。 
从图论的角度来看,要求这个图首先应该是连通的,每个点的度数都必须是偶数,这样才能走出去后走回来。为此对所有度数为奇数的节点应该加边使其变成偶数度数的节点。我们可以找出所有奇度顶点,然后找出这些奇度顶点的最小带权匹配(使用

Kuhn-Munkres算法),当然我们也可以使用动态规划的方法,来计算出怎样的加边方案使所加的边的权值之和最小(此时我们需要计算出各个度数为奇数的节点之间的最短距离,如果这两个节点之间要加边(不一定是直接连接这两个节点),就可以加最短距离的边,这不影响其他度数为偶数的节点的奇偶性),可以把状态(度数为奇数的节点的位置信息)压缩成二进制的形式,这样便于动态规划中的分阶段处理和递归调用,如假设4个节点都为度数为奇数的节点,则状态信息为:1111,在该阶段处理一对节点后,把它变为1100在下一阶段递归调用),如此非常方便。

关于状态压缩动态规划算法:
引入 
首先来说说“状态压缩动态规划”这个名称,顾名思义,状态压缩动态规划这个算法包括两个特点,第一是“状态压缩”,第二是“动态规划”。 

状态压缩: 

从状态压缩的特点来看,这个算法适用的题目符合以下的条件: 
1.解法需要保存一定的状态数据(表示一种状态的一个数据值),每个状态数据通常情况下是可以通过2进制来表示的。这就要求状态数据的每个单元只有两种状态,比如说棋盘上的格子,放棋子或者不放,或者是硬币的正反两面。这样用0或者1来表示状态数据的每个单元,而整个状态数据就是一个一串0和1组成的二进制数。 
2.解法需要将状态数据实现为一个基本数据类型,比如int,long等等,即所谓的状态压缩。状态压缩的目的一方面是缩小了数据存储的空间,另一方面是在状态对比和状态整体处理时能够提高效率。这样就要求状态数据中的单元个数不能太大,比如用int来表示一个状态的时候,状态的单元个数不能超过32(32位的机器)。 

这里举一个可以状态压缩的例子,比如poj上的第1753题Flip Game(见poj1753解题报告),虽然这道题目不是用动态规划做,但是可以用状态压缩,4×4的格子,每个格子的状态为黑或者白,这样就可以用一个16位的二进制数来表示,在实现的时候可以用一个int类型来表示这个二进制数。在状态和状态对比和转换的时候可以用位操作来完成。 

位操作实现技巧: 
如果要获得第i位的数据,判断((data&(0X<<i))==0),若真,为0,假,为1; 
如果要设置第i位为1,data=(data|(0X1<<i)); 
如果要设置第i位为0,data=(data&(~(0X1<<i))); 
如果要将第i位取反,data=(data^(0X1<<i); 
如果要取出一个数的最后一个1(lowbit):(data&(-data)) 

动态规划: 
如果说状态压缩是数据结构的话,那么动态规划应该是算法了。题目通过动态规划来解通常有两个动机,第一是利用递归的重叠子问题,进行记忆话求解,即递归法的优化。第二是把问题看作多阶段决策的过程来求解问题。在状态压缩动态规划中我们讨论的是第二种动机。 

多阶段决策过程求解问题的动态规划最重要的是划分阶段和找到状态转移方程。对于划分阶段,是根据不同阶段之间的独立性来划分,通常会用状态数组的第一个下标来记录这个阶段的标记(比如01背包问题中的状态数组第一个下标为物品的个数,棋盘放棋子问题中的状态数组的第一个下标为棋盘的行数等等)。另一个重要的便是状态转移方程,状态转移方程是递推时得到一个状态数据的重要根据。通常情况下状态数组的除了第一个下标以外都是表示状态数据的,而状态数组的值是和所求结果紧密结合的。在后面的几个例题中会重点说明状态转移方程。 

当状态压缩和动态规划结合的时候便形成了一类问题的一种算法,即状态压缩动态规划的算法。这种算法最常见在棋盘问题上或者网格问题上,因为这一类问题的状态数据的单元较少,可以通过状态压缩来对当前棋盘或者网格的状态进行处理。 

例题解析 
例:在n*n(n≤20)的方格棋盘上放置n 个车,某些格子不能放,求使它们不能互相攻击的方案总数。 
分析: 
首先看到这道题目,我们可能会想到8皇后问题,用深度优先搜索。但是这里放这道题目是用来说明此题可以状态压缩动态规划,而且状态压缩动态规划相比于深度优先搜索可以应对更多的变化情况和拥有更高的效率。 

用状态压缩动态规划算法 
1.划分阶段,本题比较简单,以行来划分阶段,即一行一行的放车。 
2.找状态转移方程,因为前i行的状态是根据前i-1行的状态来确定的,所以,在状态数组中要记录多行状态。故设计状态数组为f[i][x],i表示这是前i行的状态,x在这里是就是一个压缩的状态,记录一个二进制数从而来表示前i行的状态,f的值记录形成前i行的x状态有多少种方案。状态转移方程是f[i][a]=SUM{f[i-1][b]},下面讨论a状态与b状态的关系。先举个例子,如果a状态为01011,表明前i行中的第0,1,3列都放置了一个车(从右往左看)。于是b的状态就可能是01010,01001,00011三种状态,于是f[3][01011]=f[2][01010]+f[2][01001]+f[2][00011]。再看普遍的情况,a-b的值的二进制表示中只有一个1。而且要保证a状态,b状态不能和非可用的格子冲突。综上,状态转移方程为: 
f[i][a]=SUM{f[i-1][b]} (a-b的值的二进制表示中只有一个1; a,b不与题目中的约束条件冲突) 
这样通过递推可以得到f[n][1…1]的方案数即为最后的方案总数。 

算法总结: 
1.断定这道题目可以用数据压缩动态规划来做。重点是看它的特点,是否符合状态压缩动态规划的条件。 
2.划分阶段。像棋盘和网格问题大多数是一行一行的进行操作,故以行来划分阶段,当然也有其他的阶段划分方法,具体问题具体分析。 
3.找状态转移方程 
3.1设计状态数组。通常数组的第一个参数为阶段的标志,其他几个参数为记录状态用(如果第i行的状态可以通过第i-1行的状态来确定,则需要一个参数,即第i行的状态;如果像炮兵阵地那题一样,第i行的状态需要根据第i-1行和第i-2行来确定,则需要两个参数,分别为第i行的状态和第i-1行的状态,具体见附录)。数组的值与结果挂钩,通常有以下几种情况:a.题目要求一共有多少的方案,这时数组的值为当前状态的方案数。(比如poj2411以及例题)b.题目要求最佳方案,这是数组的值为最佳方案的值。(比如poj1185炮兵阵地)。 
3.2列出状态转移方程,对应与上面的a,b两种情况,a情况时,状态转移方程为f[i][a]=sum{f[i-1][b]}; b情况时,状态转移方程为f[i][a]=max{f[i][b]}+sth. 
3.3找出状态转移方程中a,b之间的关系。即为状态转移方程添加约束条件。 
4.在很多情况下需要对每一个阶段的可能值进行dfs来找出所有的可能值存储起来,以便在对每一个阶段处理的时候能够很快的运用以提高效率。

源代码:

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
#define MAX 16
#define INFINITE 999999999
int dijkstra(int n,int start,int end);    //求两点之间的最短路径
void Floyd(int n);           //弗洛伊德求各个节点之间的最短路径
int dfs(int st,int n);       //递归求解状态st的距离花费distanceCost值
int distanceCost[1<<15];      //每一个状态的距离花费(如4个点时的某状态0101则表示计算第1个和第3个度数为奇数的节点之间的最短路径)
int adj[MAX][MAX];            //无向图的邻接矩阵
int deg[MAX];
int main()
{
int n,m;
int a,b,c;
int sum;             //最短路径和
int status;            //压缩状态:某一个二进制位为1则表示以该位置为ID的节点的度数为奇数(如:0101则表示第1个和第3个节点的度数为奇数)
    
while(cin>>n&&n&&cin>>m)
{
sum=0;
status=0;
memset(deg,0,sizeof(deg));
for(int i=1;i<=n;i++)         //初始化邻接矩阵为无穷大
{
for (int j=1;j<=n;j++)
{
adj[i][j]=INFINITE;
}
}
while(m--)
{
cin>>a>>b>>c;
if(adj[a][b]>c)    //此处必须做个判断,若输入的边权值比预设的无穷大Infinite还大的话,则默认为infinite值。
{
 adj[a][b]=c;
 adj[b][a]=c;
}
deg[a]++;
deg[b]++;
sum+=c;     //累加路径值
}
for(int i=1;i<=n;i++)
{
            if(deg[i]%2)
{
status|=(1<<(i-1));
}
}
/*
for(int i=1;i<=n;i++)
{
int degree=0;
for(int j=1;j<=n;j++)
{
if(adj[i][j]!=INFINITE)
{
degree++;
}
}
if(degree%2)        //发现一个度数为奇数的节点
{
status|=(1<<(i-1));       //生成状态
}
}
*/

Floyd(n);
memset(distanceCost,-1,sizeof(distanceCost));    //初始化数组所有值为-1
sum+=dfs(status,n);      //最后的路径花销=原图的所有边的权值+新增加的边的权值
cout<<sum<<endl;
}
return 0;
}
/*
dijkstra最短路径算法(计算节点start到节点end之间的最短路径)
返回值:返回该最短路径的距离
一次次调用太费时间,没有使用,改用弗洛伊德算法计算好个节点之间的最短距离
*/
int dijkstra(int n,int start,int end)
{
    int dis[MAX],pre[MAX],visited[MAX];
memset(visited,0,sizeof(visited));
for(int i=1;i<=n;i++)    //初始化数组
{
        dis[i]=adj[start][i];
pre[i]=-1;
}
    visited[start]=1;
for(int i=1;i<=n;i++)
{
if(visited[i]!=1&&adj[start][i]!=INFINITE)
{
pre[i]=start;
}
}
int mark;
for(int j=1;j<=n-1;j++)
{
int temp=INFINITE;
for(int i=1;i<=n;i++)
{
if(visited[i]!=1&&dis[i]<temp)
{
temp=dis[i];
mark=i;
}
}
if(mark==end)   //找到start到目标节点end的最短路径了则提前退出循环
{
break;
}
visited[mark]=1;
for(int i=1;i<=n;i++)
{
if(visited[i]!=1&&(dis[mark]+adj[mark][i])<dis[i])
{
dis[i]=dis[mark]+adj[mark][i];
pre[i]=mark;
}
}
}
return dis[end];
}
/*
动态规划,递归调用解决加边距离总和最短的方案。
*/
int dfs(int st,int n)
{
if(st==0)  //状态变为00000000000....表示处理完了
{
return 0;
}
if(distanceCost[st]>0) //表示之前已经计算出了该子状态的距离花费distanceCost值了,直接取出即可(动态规划中,需要保存子问题的解)
{
return distanceCost[st];
}
distanceCost[st]=INFINITE;
for(int i=1;i<=n;i++)   //找出当前状态st的最小距离花费distanceCost的分配方案(即如何选择两两度数为奇数的节点为一对)
{
{
if(st&(1<<(i-1)))    //度数为奇数的一个节点
{
for(int j=1;j<=n;j++)
{
if(i!=j&&(st&(1<<(j-1))))   //度数为奇数的另一个不同节点
{
//int temp=dfs(st^(1<<(i-1))^(1<<(j-1)),n)+dijkstra(n,i,j);   //花费时间太多
int temp=dfs(st^(1<<(i-1))^(1<<(j-1)),n)+adj[i][j];     //递归调用,将状态中这个阶段处理过的两个节点对应位置上的位取反设为0
if(distanceCost[st]>temp)   //找到当前状态st的更小distanceCost值,更新它   
distanceCost[st]=temp;
}
}
}
}
}
return distanceCost[st];

}
void Floyd(int n)
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
if(adj[i][k]!=INFINITE)
for(int j=1;j<=n;j++)
if(adj[k][j]!=INFINITE)
adj[i][j]=(adj[i][j]<(adj[i][k]+adj[k][j])? adj[i][j]:(adj[i][k]+adj[k][j]));
}

  评论这张
 
阅读(881)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018