dancing link

Knuth对 算法 的描述就是一种享受～
    从算法解决什么问题 （Exact Cover ）（精确覆盖），到算法的实现(DancingLink ),相当的自然，而且对算法的描述，非常自然，很想得通～赞赞！

  看完_{就知道，关键是如何实现一个那样的矩阵表示，想想C语言的矩阵表示，如果拷贝实在太费时，怎么办呢？dancing Links , 用链表实现～赞～}

 

 

Knuth's Algorithm X

Donald Knuth 's Algorithm X  is a recursive , nondeterministic , depth-first , backtracking  algorithm  that finds all solutions to the exact cover problem represented by a matrix A  consisting of 0s and 1s. The goal is to select a subset of the rows so that the digit 1 appears in each column exactly once.

1. If the matrix A  is empty, the problem is solved; terminate successfully.
2. Otherwise choose a column  c  ( deterministically ). 这里是确定性的，找到含有1最少的那个column  why -Lin Yang 3/30/10 11:07 AM  
   • 原因是：If column c is entirely zero, there are no subalgorithms and the process terminates unsuccessfully  -所以找到含有1最少的那个column，可以尽快结束算法。
   • Golomb and Baumert [16] suggested choosing a subproblem that leads to the fewest branches
   • 这是启发式
     
     
3. Choose a row r  such that A _{r , c}  = 1 (nondeterministically ).
4. Include row r  in the partial solution.
5. For each column j  such that A _{r , j}  = 1,for each row i  such that A _{i , j}  = 1,delete row i  from matrix A ;delete column j  from matrix A .
6. Repeat this algorithm recursively on the reduced matrix A .

 

-from wikipedia

 

 

 

这个图很经典～

 

/**
 * pku 3740 -dancing link
 * 完全按照knuth论文的语意实现。
 * 算法很复杂，但是初始化数据结构更复杂。。
 */

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

#define ROW 20
#define COL 305
#define INF 9999999

// 必须是按照与删除顺序相反的顺序恢复，才对

int rr, cc;
//both used for data node obj & column obj
struct NODE {
	int L, R, U, D;
	int C; //points	to the column object 
	int S; //column_header use
	char N;//column_header use
};

struct NODE nodes[ROW * (COL + 1)]; //nodes[0...cc]作为column_header //nodes[999作为header]  nodes[1000 - ...]存放node 

int head_id = 999;//没被占用
struct NODE &head = nodes[head_id];//用nodes[-1]表示
int nodes_id;

int choose_column() {
	int s = INF;
	int c = head.R;
	for (int j = head.R; j != head_id; j = nodes[j].R)
		if (nodes[j].S < s) {
			c = j;
			s = nodes[j].S;
		}
	return c;
}

void cover(int c) {
//	printf("cover(%d)", c);
	nodes[nodes[c].R].L = nodes[c].L;
	nodes[nodes[c].L].R = nodes[c].R;
	for (int r = nodes[c].D; r != c; r = nodes[r].D) {
//		printf("r:%d\n", r);
		for (int j = nodes[r].R; j != r; j = nodes[j].R) {
//			printf("j:%d\t", j);//here
			nodes[nodes[j].D].U = nodes[j].U;
			nodes[nodes[j].U].D = nodes[j].D;
			nodes[nodes[j].C].S--;
		}
	}
}

void uncover(int c) {
	for (int i = nodes[c].U; i != c; i = nodes[i].U)
		for (int j = nodes[i].L; j != i; j = nodes[j].L) {
			nodes[nodes[j].C].S++;
			nodes[nodes[j].U].D = j;
			nodes[nodes[j].D].U = j;
		}
	nodes[nodes[c].L].R = c;
	nodes[nodes[c].R].L = c;
}

int search(int k) {
//	printf("search(%d)\n", k);
	if (head.R == head_id)
		return 1;
	int c = choose_column();
//	printf("choose_colume return: %d\n", c);
	cover(c);
	for (int r = nodes[c].D; r != c; r = nodes[r].D) {
//		printf("r:%d\n", r);
		for (int j = nodes[r].R; j != r; j = nodes[j].R) {
//			printf("j:%d\t", j);
			cover(nodes[j].C);
		}
		if (search(k + 1))
			return 1;//modified
		for (int j = nodes[r].L; j != r; j = nodes[j].L) {
			uncover(nodes[j].C);
		}
	}
	uncover(c);
	return 0;
}

int mat[ROW][COL];
int map[ROW][COL];

void link_row(int r) {
//	printf("link_row(%d)",r);
	int c1 = 0;
	for (c1 = 0; c1 < cc; c1++)
		if (mat[r][c1])
			break;
	if (c1 == cc)
		return;
	int id1 = map[r][c1];
	nodes[id1].L = nodes[id1].R = id1;// init link list

	for (int c = 0; c < cc; c++)
		if (mat[r][c] && c != c1) {
			int id2 = map[r][c];
			nodes[id2].R = nodes[id1].R;
			nodes[id2].L = id1;
			nodes[nodes[id1].R].L = id2;
			nodes[id1].R = id2;
		}
}
void link_col(int c) {
//	printf("link_col(%d)",c);
	//init nodes[c]
	nodes[c].U=nodes[c].D = nodes[c].C  =c;
	nodes[c].S =0;
	//insert column_header
	nodes[c].R = head.R;
	nodes[c].L = head_id;
	nodes[head.R].L = c;
	head.R = c;
	int id = -1;
	//set column nodes
	for (int r = 0; r < rr; r++) {
		if (!mat[r][c])
			continue;
		id = map[r][c];
		nodes[id].C = c;
		nodes[c].S++; //update Sum
		//insert node 
		nodes[id].D = nodes[c].D;
		nodes[id].U = c;
		nodes[nodes[c].D].U = id;
		nodes[c].D = id;
	}
}
void init() {
	memset(nodes, 0, sizeof(nodes));
	head.L = head.R = head_id;
	nodes_id = head_id + 1;
	for (int r = 0; r < rr; r++)
		for (int c = 0; c < cc; c++)
			if (mat[r][c] == 1)
				map[r][c] = nodes_id++;
	for (int r = 0; r < rr; r++) {
		link_row(r);
	}
	for (int c = 0; c < cc; c++) {
		link_col(c);
	}
}

int main() {
	while (EOF != scanf("%d%d", &rr, &cc)) {
		for (int r = 0; r < rr; r++)
			for (int c = 0; c < cc; c++) {
				scanf("%d", &mat[r][c]);
			}
		fflush(stdout);
		init();
		if (search(0))
			printf("Yes, I found it\n");
		else
			printf("It is impossible\n");
	}
	return 0;
}

/*
 1 1
 1

 1 2
 1 1

 1 2
 0 0

 1 2 
 0 1
 */

/**
 3 3
 0 1 0
 0 0 1
 1 0 0
 4 4
 0 0 0 1
 1 0 0 0
 1 1 0 1
 0 1 0 0
 4 6
 0 0 0 1 1 1
 1 0 0 0 0 0
 1 1 0 1 0 0
 0 0 1 0 0 0


 4 6
 0 0 0 1 1 1
 1 0 0 0 0 0
 1 1 0 1 0 0
 0 1 1 0 0 0

 */

/**

 yes 
 no 
 no
 yes
 **/

 

Knuth这个复杂度分析，太精细了～

    Each update involves about 14 memory accesses when the S heuristic is used, and about

8 accesses when S is ignored. Thus the S heuristic multiplies the total number of memory

accesses by a factor of approximately (14 × 3,617,723)/(8 × 17,818,752) 36%

 

 

实现：

注意： cover和uncover一定要完全反序～（Notice that uncovering takes place in precisely the reverse order of the covering operation）

实现过程中，

最好不要使用这样的数据结构，

struct  point  {
     int  L;
     int  R;
     int  U;
     int  D;
     int  Sum;
     int  x, y;
} p[  1010  *  1010  ];

因为需要写：

nodes[nodes[c].R].L = nodes[c].L;

nodes[nodes[c].L].R = nodes[c].R;

来表示删除，而Knuth使用

L[R[c]]=L[c] 

R[L[c]]=R[c].表示删除

而不要用真正的指针 ，因为那样很难调试。。