HDU 1560 DNA sequence (IDA* 迭代加深 搜索)

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1560

BFS题解:http://www.cnblogs.com/crazyapple/p/3218107.html

构造一个串,使得它包含所有的给定DNA序列,并且要求长度最短。
采用dfs策略,对于每个串定义1个指针,当全部指针为串尾时判断构造的长度,由于状态空间过大,但是又存在冗余搜索,可以用迭代加深将状态减少。最长待构造长度 + 当前长度 < 迭代的最大深度则直接return,大大减少了状态数。

慢慢迭代加深搜索;

代码:

 #include<iostream>
#include<stdio.h>
#include<string.h> using namespace std; struct Nod
{
int pos[];
}temp;
int n,len[];
char str[][];
char dna[]="ACGT"; int dfs(Nod tnd,int sum,int depth) //迭代加深搜索
{
int i,j,flag;
Nod nd;
if(sum>depth) return ; //搜索深度超过depth时,表示深度depth太小,还得继续增加
for(i=;i<n;i++) if(len[i]-tnd.pos[i]+sum>depth) return ; //某一个串超过深度depth,len[i]是串本身的长度,tnd.pos[i]为迭代产生的长度,sum为迭代的深度
for(i=;i<n;i++) if(tnd.pos[i]<len[i]) break; //如果某行没有迭代到本身串的长度就break,结合下面if(i==n)判断
if(i==n) return ; //如果i==n,即对i(0,n-1) tnd.pos[i]>=len[i],全部迭代完成
for(i=;i<;i++)
{
flag = ; //标记是否匹配上
for(j=;j<n;j++)
{
if(str[j][tnd.pos[j]]==dna[i]) //用A C G T去匹配
{
flag = ;
nd.pos[j] = tnd.pos[j] + ; //匹配上了位置向后移动一位
}
else
{
nd.pos[j] = tnd.pos[j];
}
}
if(flag&&dfs(nd,sum+,depth)) return ; //匹配上了,就进行下一层匹配
}
return ;
} int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int i;
scanf("%d",&n);
for(i=;i<n;i++)
{
scanf("%s",str[i]);
len[i] = strlen(str[i]);
}
for(i=;;i++) if(dfs(temp,,i)) break; //i为迭代加深的值,找到则跳出
printf("%d\n",i);
}
return ;
}
上一篇:HDU 1560 DNA sequence (迭代加深搜索)


下一篇:Python3中使用PyMySQL连接Mysql