8
25
2012
0

时间和空间的矛盾:The Clocks

Consider nine clocks arranged in a 3x3 array thusly:

|-------|    |-------|    |-------|    
|       |    |       |    |   |   |    
|---O   |    |---O   |    |   O   |          
|       |    |       |    |       |           
|-------|    |-------|    |-------|    
    A            B            C

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O   |    |   O   |
|   |   |    |   |   |    |   |   |
|-------|    |-------|    |-------|
    D            E            F

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O---|    |   O   |
|   |   |    |       |    |   |   |
|-------|    |-------|    |-------|
    G            H            I

The goal is to find a minimal sequence of moves to return all the dials to 12 o'clock. Nine different ways to turn the dials on the clocks are supplied via a table below; each way is called a move. Select for each move a number 1 through 9 which will cause the dials of the affected clocks (see next table) to be turned 90 degrees clockwise.

Move Affected clocks
1 ABDE
2 ABC
3 BCEF
4 ADG
5 BDEFH
6 CFI
7 DEGH
8 GHI
9 EFHI

Example

Each number represents a time accoring to following table:

9 9 12       9 12 12       9 12 12        12 12 12      12 12 12 
6 6 6  5 ->  9  9  9  8->  9  9  9  4 ->  12  9  9  9-> 12 12 12 
6 3 6        6  6  6       9  9  9        12  9  9      12 12 12 

[But this might or might not be the `correct' answer; see below.]

PROGRAM NAME: clocks

INPUT FORMAT

Lines 1-3: Three lines of three space-separated numbers; each number represents the start time of one clock, 3, 6, 9, or 12. The ordering of the numbers corresponds to the first example above.

SAMPLE INPUT (file clocks.in)

9 9 12
6 6 6
6 3 6

OUTPUT FORMAT

A single line that contains a space separated list of the shortest sequence of moves (designated by numbers) which returns all the clocks to 12:00. If there is more than one solution, print the one which gives the lowest number when the moves are concatenated (e.g., 5 2 4 6 < 9 3 1 1).

SAMPLE OUTPUT (file clocks.out)

4 5 8 9

这个问题要求用最少的步骤把所有的表盘都调整到12点,所能使用的操作集合是给定的。首先我们也许会担心这九种操作是否总能给出一个解决方案,答案是肯定的,因为对于任意表盘,都有一个操作序列能使表针不多不少顺时针转动90度同时其他表盘最终回到原状态(通过应用我们的算法可以预计算出这些操作序列,实际上这些序列的计算只是原问题的特例)。如此以来,通过累积这些序列的操作,我们肯定能得到一个问题的解(这正是USACO题解中给出的一种方法)。

然后我们注意到所有操作最多可以做3次(如果一种操作做4次,等价于没有做任何操作),而且操作顺序对结果没有影响(因为操作的效果是累加的)。这样以来所有可能的操作序列有4^9=262144个,这个数量级完全可以暴力破解(USACO对程序的限制是:运行时间<1s,内存<14M,栈<1M)。

如此一来通过DFS枚举所有情况是完全可行的。但是由于这个问题实质上属于求“最短路径”(这里路径就是操作序列),我选择了BFS以保证得到的第一个解就是最优解(DFS因为是深度优先,不遵循路径长度的顺序进行搜索,第一个解一般不是最优解,所以需要遍历所有情况,这消耗了不必要的时间),当然这需要对搜索的顺序做一定的安排:按非递减顺序遍历,每种操作最多三次。

BFS看似是个不错的选择,但是最多262144个搜索节点数让人头疼,为此我MLE(Memory Limit Exceeded)了一次。之后我想到了使用循环队列【1】


【1】循环队列开多大?找到搜索树中节点数之和最多的相邻两层,如果这个节点数之和是n,那么循环队列开到n+1应该就可以了。假设队列长度为n+1但是搜索过程中队尾循环回来覆盖了队头,这说明队头节点和队尾节点之间有n个节点,这与相邻两层节点数之和最多为n相矛盾(注意到BFS时队头节点永远在队尾节点的上一层)。

但是对于这道题,我的搜索树形状很奇特,这给估算n值带来了很大麻烦,在尝试之后我取了n=50000并且AC。这显然是BFS在解决这个问题时最大的坏处。

作为一个对空间的优化,实际上可以使用位运算,这样可以用一个整数的比特位表示所有表盘的状态,这让它既省空间又省时间。但我没有尝试。


我的程序代码:

/*
ID: *******
LANG: C
TASK: clocks
*/
#include<stdio.h>
FILE *fin,*fout;
typedef struct{
	int clo[9];//表盘状态
	int beg;//第一个要尝试的操作的编号
	int count[9];//每种操作的次数
	int memo[27];//操作序列
	int pMemo;
}CL;//搜索树节点的定义
CL queue[50001];
int tailQue=-1;
int headQue=-1;
int move[9][9]={
	{3,3,0,3,3,0,0,0,0},
	{3,3,3,0,0,0,0,0,0},
	{0,3,3,0,3,3,0,0,0},
	{3,0,0,3,0,0,3,0,0},
	{0,3,0,3,3,3,0,3,0},
	{0,0,3,0,0,3,0,0,3},
	{0,0,0,3,3,0,3,3,0},
	{0,0,0,0,0,0,3,3,3},
	{0,0,0,0,3,3,0,3,3}
};

int testOutput(int po){
	int isAnswer=1;
	int i;
	for(i=0;i<9;i++){
		if(queue[po].clo[i]!=12){
			isAnswer=0;
			break;
		}
	}
	if(isAnswer==1&&queue[po].pMemo>=0){
		fout=fopen("clocks.out","w");
		fprintf(fout,"%d",queue[po].memo[0]+1);
		for(i=1;i<=queue[po].pMemo;i++){
			fprintf(fout," %d",queue[po].memo[i]+1);
		}
		fprintf(fout,"\n");
	}
	return isAnswer;
}

int main(){
	fin=fopen("clocks.in","r");
	int i;
	headQue=0;
	tailQue=1;
	for(i=0;i<9;i++){
		fscanf(fin,"%d",&queue[headQue].clo[i]);
		queue[headQue].count[i]=0;
	}
	queue[headQue].pMemo=-1;
	queue[headQue].beg=0;
	while(headQue!=tailQue){//开始BFS
		if(testOutput(headQue)==1)break;
		for(i=queue[headQue].beg;i<9;i++){
			if(queue[headQue].count[i]>=3)continue;
			int j;
			for(j=0;j<9;j++){
				queue[tailQue].clo[j]=queue[headQue].clo[j]+move[i][j];
				if(queue[tailQue].clo[j]>12)
					queue[tailQue].clo[j]-=12;
				queue[tailQue].count[j]=queue[headQue].count[j];
			}
			for(j=0;j<=queue[headQue].pMemo;j++)
				queue[tailQue].memo[j]=queue[headQue].memo[j];
			queue[tailQue].count[i]++;
			queue[tailQue].pMemo=queue[headQue].pMemo+1;
			queue[tailQue].memo[queue[tailQue].pMemo]=i;
			queue[tailQue].beg=i;
			//printf("tail:%d\n",tailQue);
			tailQue++;
			if(tailQue>50000)tailQue=0;
		}
		headQue++;
		if(headQue>50000)headQue=0;
	}
	return 0;
}

USACO题解的第一种方法是DFS:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <ctype.h>

#define INF 60000	/* bigger than longest possible path */

char *movestr[] = { "abde", "abc", "bcef", "adg", "bdefh", "cfi", "degh",
                    "ghi", "efhi" };

int movedist[9][9];
int clock[9];

int bestmove[9];
int nbestmove;

/* translate move strings into array "movedist" of which clocks change on each move */
void
mkmove(void)
{
    int i;
    char *p;

    for(i=0; i<9; i++)
	for(p=movestr[i]; *p; p++)
	    movedist[i][*p-'a'] = 3;
}

/* apply some number of each move from k to 9 */
/* move contains the number of times each move is applied */
void
solve(int *move, int k)
{
    int i, j, n, rep;

    if(k == 9) {
	for(j=0; j<9; j++)
	    if(clock[j]%12 != 0)
		return;

	/* we have a successful sequence of moves */
	n = 0;
	for(j=0; j<9; j++)
	    n += move[j];

	if(nbestmove == 0 || n < nbestmove) {
	    nbestmove = n;
	    for(j=0; j<9; j++)
		bestmove[j] = move[j];
	}
	return;
    }

    /*
     * the for loop counts down so we
     * generate smaller numbers first by
     * trying more of small numbered
     * moves before we try less of them.
     */
    for(rep=3; rep>=0; rep--) {
	/* apply move k rep times */
	for(i=0; i<rep; i++)
	    for(j=0; j<9; j++)
		clock[j] += movedist[k][j];
	move[k] = rep;

	solve(move, k+1);

	/* undo move */
	for(i=0; i<rep; i++)
	    for(j=0; j<9; j++)
		clock[j] -= movedist[k][j];
    }
}

void
main(void)
{
    FILE *fin, *fout;
    int i, j, move[9];
    char *sep;

    fin = fopen("clocks.in", "r");
    fout = fopen("clocks.out", "w");
    assert(fin != NULL && fout != NULL);

    mkmove();

    for(i=0; i<9; i++)
	fscanf(fin, "%d", &clock[i]);

    solve(move, 0);

    sep = "";
    for(i=0; i<9; i++) {
	for(j=0; j<bestmove[i]; j++) {
	    fprintf(fout, "%s%d", sep, i+1);
	    sep = " ";
	}
    }
    fprintf(fout, "\n");

    exit(0);
}

第二种方法很独特,正如文章开头提到的“对于任意表盘,都有一个操作序列能使表针不多不少顺时针转动90度同时其他表盘最终回到原状态”。这是USACO的原文:


You can precalculate a matrix a as following:

a[i][0],a[i][1],....,a[i][8] is the number of moves '1','2','3',...'9' necessarly to move ONLY clock i (where 0 < i <= 8 - there are 9 clocks: 0=A, 1=B, ... 8=I) 90 degrees clockwise. So, you have the matrix:

int a[9][9]= { {3,3,3,3,3,2,3,2,0},
               {2,3,2,3,2,3,1,0,1},
               {3,3,3,2,3,3,0,2,3},
               {2,3,1,3,2,0,2,3,1},
               {2,3,2,3,1,3,2,3,2},
               {1,3,2,0,2,3,1,3,2},
               {3,2,0,3,3,2,3,3,3},
               {1,0,1,3,2,3,2,3,2},
               {0,2,3,2,3,3,3,3,3} };

That means: to move ONLY the clock 0 (clock A) 90 degrees clockwise you have to do {3,3,3,3,3,2,3,2,0}, 3 moves of type 1, three moves of type 2, ..., 2 moves of type 8, 0 moves of type 9, etc.

To move ONLY the clock 8 (clock I), you have to do the moves {0,2,3,2,3,3,3,3,3}: 0 moves of type 1, 2 moves of type 2... 3 moves of type 9....

That's it! You count in a vector v[9] how many moves of each type you have to do, and the results will be modulo 4 (%4 - 5 moves of any type have the same effect 1 move has).


代码:

#include <stdio.h>

int a[9][9]= { {3,3,3,3,3,2,3,2,0},
               {2,3,2,3,2,3,1,0,1},
               {3,3,3,2,3,3,0,2,3},
               {2,3,1,3,2,0,2,3,1},
               {2,3,2,3,1,3,2,3,2},
               {1,3,2,0,2,3,1,3,2},
               {3,2,0,3,3,2,3,3,3},
               {1,0,1,3,2,3,2,3,2},
               {0,2,3,2,3,3,3,3,3} };
int v[9];

int main() {
    int i,j,k;
    freopen("clocks.in","r",stdin);
    for (i=0; i<9; i++) {
        scanf("%d",&k);
        for(j=0; j<9; j++)
             v[j]=(v[j]+(4-k/3)*a[i][j])%4;
    }
    fclose(stdin);

    k=0;
    freopen("clocks.out","w",stdout);
    for (i=0; i<9; i++)
        for (j=0; j<v[i]; j++)
            if (!k) { printf("%d",i+1); k=1; }
            else    printf(" %d",i+1);
    printf("\n");
    fclose(stdout);
    return 0;
}

方法就是预先计算出所有这些序列,然后针对具体问题简单地叠加这些操作序列,如果一种操作超过了4次,将操作次数模4取余。这种方法可以在O(1)时间内解决问题。问题是这种方法能够总是得到最优解吗?

我认为这种方法成立的一个重要前提是 9种基本操作中任意一种不能由其余操作的组合来等效!

这样一来,操作2(ABC)等于a[0]+a[1]+a[2](a[i]表示一个向量),也就是说(a[0]+a[1]+a[2])mod 4 == {0,1,0,0,0,0,0,0,0} (参照原文中的int a[9][9]),也就是说a矩阵中各种操作的叠加不仅和操作2等效,而且实际上就是操作2。相反,如果这个重要前提不成立,例如操作2可以由操作1和操作3叠加得到,那么a[0]+a[1]+a[2]有可能等于{1,0,1,0,0,0,0,0,0} 这样由此算法得到的解不一定是最优解(一个操作变成了两个操作,操作步骤增加了)。

如果这个前提成立,那么这个算法肯定是安全的,当然这只是一个充分条件,至于其必要性我没能证明。不过从另一角度考虑,一个“九维”的表盘组,表盘之间没有相关性,如果操作2可以由操作1和3叠加的话,实际上我们只有8种操作方式,这显然是不够的,对于一些情况它甚至不能成功的将所有表盘调到12点!

那么这个安全性如何被保证呢?当这个前提成立时,我们的搜索算法和这个常数时间算法是等价的。因为9种操作的每一种都和a矩阵中的某操作序列唯一等价。当你被告知a矩阵向量的某种组合可以组合出最优解,而且把重复4次的向量消去后你只有唯一一种组合方式,那么这个组合不是最优解又能是什么呢?

PS. 本文所有推理都是意淫,事实上本人没有什么数学造诣以至于不能给出形式化的证明。

Category: USACO | Tags: usaco | Read Count: 969

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com