比如最近2008 sysu校赛预选的gene reprogram，2008广东省赛的fengshui，以及usaco的clocks(http://ace.delos.com/usacoprob2?a=RRbITFklHzA&S=clocks)
下面用gene reprogram做个例子，备忘一下。
-------------------------------------------------------------------------------
Problem
As a gene engineer of a gene engineering project, Enigma encountered a puzzle about gene recombination.It is well known that a gene can be considered as a sequence, consisting of four nucleotides, which are simply denoted by four letters, A, C, G, and T.
Enigma has gotten a gene, such as "ATCC" for example. And he wants to reorder this gene to a new one, "CTCA" for instance. He can use two kinds of operations: (1) exchange the first two letters, or (2) move the first letter to end of the gene. For example, "ATCC" can be changed to "TCCA" by operation two, and then "TCCA" can be changed to "CTCA" by operation one. Your task is to make a program to help Enigma to find out the minimum number of operations to reorder the gene.
Input
The input contains several test cases. The first line of a test case contains one integer N indicating the length of the gene (1<=N<=12). The second line contains a string indicating the initial gene. The third line contains another string which Enigma wants.For each kind of letter, the two strings have the same number of it.
Output
For each test case, output the minimum number of operations.Sample input
4
ATCC
CTCA
4
ATCG
GCTA
4
ATCG
TAGC
Sample output
2-------------------------------------------------------------------------------
4
6
代码：
#include <stdio.h>
#include <string.h>
int len;
int before[15];
int after[15];
char mark[1<<24]; // 用于hash的数组
const int QLEN = 200000; // 广搜队列长度
int bval,eval;
struct node
{// 广搜树节点
int value;
int level;
};
node q[QLEN];
int b,e; // queue and its head,tail
void inc(int & p)
{// 使用循环队列的方法来保存节点
if(++p == QLEN) p=0;
}
int zip(int * gene)
{// 状态压缩
int result = 0,base = 1,i,j;
for(i=len-1;i>=0;i--)
result |= gene[i]<<((len-i-1)*2);
return result;
}
int * unzip(int zipped,int * gene)
{// 解压缩
int i;
for(i=0;i<len;i++)
{
gene[i] = (zipped>>(len-i-1)*2)&3;
}
return gene;
}
int op1(int gene)
{// 对应题目的第一个操作
int first = (gene>>(len-1)*2)&3;
int second = (gene>>(len-2)*2)&3;
int mask = (1<<(len*2))-1; // for len=4, 11 11 11 11
int mask1 = ~(3<<(len-1)*2) & mask; // for len=4, 00 11 11 11
int mask2 = ~(3<<(len-2)*2) & mask; // for len=4, 11 00 11 11
gene &= mask1;
gene &= mask2;
gene |= first<<(len-2)*2;
gene |= second<<(len-1)*2;
return gene;
}
int op2(int gene)
{// 对应题目的第二个操作
int first = (gene>>(len-1)*2)&3;
int m = (1<<(len*2))-1; // for len=4, 11 11 11 11
int mask = ~(3<<(len-1)*2) & m; // for len=4, 00 11 11 11
gene = (gene&mask) <<2;
gene |= first;
return gene;
}
void getGene(int * gene)
{// 输入gene
char ch;
for(int i=0;i<len;i++)
{
scanf("%c",&ch);
switch(ch)
{
case 'A':gene[i] = 0;break;
case 'C':gene[i] = 1;break;
case 'G':gene[i] = 2;break;
case 'T':gene[i] = 3;break;
}
}
scanf("\n");
}
int search()
{// 进行搜索，返回结果所在的层数，就是所需要的最短步数
while( b!=e )
{
node n = q[b]; // de-queue
inc(b);
if( n.value == eval ) return n.level;
node temp;
temp.value = op1(n.value);
temp.level = n.level + 1;
if( temp.value == eval ) return temp.level;
if( mark[temp.value] != 1)
{// en-queue
q[e] = temp;
inc(e);
mark[temp.value] = 1;
}
temp.value = op2(n.value);
temp.level = n.level + 1;
if( temp.value == eval ) return temp.level;
if( mark[temp.value] != 1)
{// en-queue
q[e] = temp;
inc(e);
mark[temp.value] = 1;
}
}
return -1;
}
int main()
{
freopen("order.in","r",stdin);
while( scanf("%d\n",&len) != EOF)
{
memset(mark,0,sizeof(mark));
b=0;e=0;
getGene(before);
getGene(after);
bval = zip(before);
eval = zip(after);
node temp;
temp.value = bval;
temp.level = 0;
q[b] = temp; // 把初始状态压入队列
inc(e);
mark[bval] = 1;
int result = search();
printf("%d\n",result);
}
return 0;
}
-------------------------------------------------------------------------------
分析：
1.广搜
一般题目都是给出一个configuration，再给出几个操作op，要求使用这些op对初始状态进行变换，
直到状态变为目标状态为止，如果无法达到则输出-1.
一般有两种问法，比较简单的是问最少要多少步能达到；也可能会要求给出最短路径。
对于前者，无需保存整棵搜索树，只需要记录当前节点的层数即可，这时可以使用循环队列的方法来记录节点。
对于后者，则有必要保存整棵搜索树（所以此时状态压缩、空间分配很重要），才能进行有效回溯。不能使用循环队列，否则会覆盖回溯路径的父节点。
此时广搜队列的长度则能大则大了，不过用内存多少是给定的，就狠狠地用尽它吧！
2.状态压缩
一般题目都是给出一个向量或矩阵表示初始状态。则此时可以把每一个元素可能出现的状态记为base，
则整个状态可以看作一个base进制的数，第i个元素可以看作权为i的系数。
比如本题给出的元素状态有4种：A,C,G,T，我分别把它们记做0，1，2，3.
对于一个具有n位的串a，状态可以表示为一个int：
a[0]*4^0 + a[1]*4^1 + ... a[n-1]*4^(n-1)
因为n最大取12，则可能出现的最大数为4^13-1=64M,可能存在的状态有4^12=16M种。
比如串ACGT=0123,可以表示为0*64+1*16+2*4+3*1=27
一般化一点，可能出现的最大数为base^(n+1)-1，存在的状态有base^n种
此时往往可能出现的问题是：
由于base或n太大，使得一个int无法保存，或者使得剪枝操作无法进行（跟后面介绍的hash方法有关）
考虑到一个字节有8位，用以上的方法我们只利用了其中的2位，因此可以进一步使用位压缩方法进行压缩。
显然，可以使用00=0,01=1,10=2,11=3来表示这四种状态，使用移位的方法可以拼凑出需要的数字。
也许其中会写很多微操作的步骤，不过不用担心，做一个位操作比做一个乘除快多了。
比如本题，使用
int result = 0,base = 1,i,j;
for(i=len-1;i>=0;i--)
result |= gene[i]<<((len-i-1)*2);
从最低位开始每次左移两位来拼凑出最后的int表示。
这样则充分利用了每一个位，使得状态压缩得更精简。
3.剪枝
剪枝的主要原则是发掘操作的顺序、重复，以删除无用的树枝。
比如问题中，可以观察到进行两次操作一则得到原串，进行k=串长度次数的操作二可以得到原串，
另外经过多次的op1，op2操作，也是有可能得到相同的串的。
而USACO的clocks题目，操作之间是无序的，即op1(op2(state)) = op2(op1(state))
而且四个op
此时如果已经搜索过某个状态及其生成的树而无结果，则下次不必再搜索。
剪枝的实现一般是通过顺序搜索或者hash实现的。
对于前者，每次生成新的状态便在队列中搜索是否存在相同元素，如果存在则不必加入；
对于后者，每次新生成的状态在一个开关数组中查询，如果标记了说明已经生成过了，如果没有标记则可以进行搜索，并且标记之，
一般使用char 的数组来完成标记，其实这就是一种桶大小为1，而桶数量为状态数的hash。
对于以上介绍的压缩方法，刚好可以利用hash方法来进行标记，因此这两种技术往往是一起使用的。威力不是一般的强大。
本题16M的状态刚好可以使用一个足够大小的char数组保存，大小为16MB（一般允许使用32MB-64MB的内存）
-------------------------------------------------------------------------------
后记：刚刚开始接触这种题目时，觉得混杂了这么多的算法和技巧很复杂，其实写多了就是一个样
代码也不长，简单的100行左右就好了。因此也可以说是简单题目。
不过很多题目的数据强度都是恰好能让人用尽内存和时间后AC的，所以也不容轻视。
No comments:
Post a Comment