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，大大减少了状态数。

慢慢迭代加深搜索；

代码：

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 
 5 using namespace std;
 6 
 7 struct Nod
 8 {
 9     int pos[8];
10 }temp;
11 int n,len[10];
12 char str[10][10];
13 char dna[]="ACGT";
14 
15 int dfs(Nod tnd,int sum,int depth)  //迭代加深搜索
16 {
17     int i,j,flag;
18     Nod nd;
19     if(sum>depth)   return 0;  //搜索深度超过depth时，表示深度depth太小，还得继续增加
20     for(i=0;i<n;i++)    if(len[i]-tnd.pos[i]+sum>depth) return 0;  //某一个串超过深度depth，len[i]是串本身的长度，tnd.pos[i]为迭代产生的长度，sum为迭代的深度
21     for(i=0;i<n;i++)    if(tnd.pos[i]<len[i])  break;  //如果某行没有迭代到本身串的长度就break，结合下面if（i==n）判断
22     if(i==n)    return 1;   //如果i==n，即对i（0，n-1） tnd.pos[i]>=len[i]，全部迭代完成
23     for(i=0;i<4;i++)
24     {
25         flag = 0; //标记是否匹配上
26         for(j=0;j<n;j++)
27         {
28             if(str[j][tnd.pos[j]]==dna[i]) //用A C G T去匹配
29             {
30                 flag = 1;
31                 nd.pos[j] = tnd.pos[j] + 1;  //匹配上了位置向后移动一位
32             }
33             else
34             {
35                 nd.pos[j] = tnd.pos[j];
36             }
37         }
38         if(flag&&dfs(nd,sum+1,depth))   return 1;  //匹配上了，就进行下一层匹配
39     }
40     return 0;
41 }
42 
43 int main()
44 {
45     int t;
46     scanf("%d",&t);
47     while(t--)
48     {
49         int i;
50         scanf("%d",&n);
51         for(i=0;i<n;i++)
52         {
53             scanf("%s",str[i]);
54             len[i] = strlen(str[i]);
55         }
56         for(i=0;;i++) if(dfs(temp,0,i)) break;  //i为迭代加深的值，找到则跳出
57         printf("%d
",i);
58     }
59     return 0;
60 }

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

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