没有合适的资源?快使用搜索试试~ 我知道了~
资源详情
资源评论
资源推荐
Dancing Links 在搜索中的应用
momodi
2008 年 7 月 8 日
目录
1 Abstract 2
1.1 Dancing Links是什么 . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Dancing Links的主要原理是什么 . . . . . . . . . . . . . . . . 2
1.3 这篇论文与knuth论文的不同 . . . . . . . . . . . . . . . . . . 2
2 双向链表 2
2.1 双向链表的存储结构 . . . . . . . . . . . . . . . . . . . . . . . 2
2.2 双向链表的应用 . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.3 双向链表的恢复 . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3 Exact Cover Problem 3
3.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.2 Solving an exact cover problem . . . . . . . . . . . . . . . . . 3
3.3 The Dance Steps . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.4 Hust Online Judge Problem 1017 . . . . . . . . . . . . . . . . 8
4 Sudoku to exact cover problem 8
4.1 What is Sudoku? . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.2 How to Solve Sudoku Puzzle? . . . . . . . . . . . . . . . . . . 9
4.3 Dancing Links在解决Sudoku这类问题上的优势 . . . . . . . . 10
4.4 转化模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.5 Pku Online Judge Problem 3076 3074 . . . . . . . . . . . . . 11
5 Exact cover problem 变种 11
5.1 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
5.2 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1
1 ABSTRACT 2
5.3 H function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.4 Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.5 Pku Online Judge Problem 1084 . . . . . . . . . . . . . . . . 13
1 Abstract
1.1 Dancing Links是什么
Dancing Links 是knuth 在近几年写的一篇论文,在我看来是一类搜索
问题的通用优化, 因此我把它写下来,希望能在竞赛中得到一定的应用。
1.2 Dancing Links的主要原理是什么
Dancing Links 主要是用双向十字链表来存储稀疏矩阵,来达到在搜索
中的优化。在搜索问题中,所需要存储的矩阵往往随着递归的加深会变得越
来越稀疏,这种情况用Dancing Links 来存储矩阵,往往可以取得非常好的
效果。
1.3 这篇论文与knuth论文的不同
本篇论文是对Dancing Links 在竞赛的应用的一个介绍,并列举了几个
竞赛中的例题。原文可以在此下载到:
http://www.ocf.berkeley.edu/ jchu/publicportal/sudoku/0011047.pdf
相对于本文,我更建议去读者去看knuth的原文,本文可以当作一个参
考。本文还介绍了Sukudo问题和一个Dancing Links的一个变种问题。
2 双向链表
2.1 双向链表的存储结构
双向链表的存储结构往往是有一个空的结点来表示头指针。然后每一
个结点有一个pre值域和一个next值域。如果是十字链表的话,结点中指针
的值域会变成四个。
2.2 双向链表的应用
众所周知,在单向链表中删除一个结点是非常麻烦,而且低效的。双向
链表有着优美的结构,可以方便的删除任意一个结点。有如下操作:
L[R[x]] = L[x], R[L[x]] = R[x]; (1)
3 EXACT COVER PROBLEM 3
相信有写过双向链表经验的人对这两句话一定不会陌生.
2.3 双向链表的恢复
在双向链表中删除一个结点只要用(1) 就可以了,然后来看下面这一段
代码:
L[R[x]] = x, R[L[x]] = x; (2)
这段代码会将已经删除掉的结点,重新添加回双向链表中。第一次看到这段
代码的你是不是会感觉非常奇妙?你有可能会说在链表中进行删除操作但
是不释放内存的话是不好的编程习惯,会造成内存溢出错误。但是在这里,
我们要的就是这样的效果。
我们在链表中删除,只是进行一个标记,并不进行真正的清空内存操
作。这样我们后来便可以用(2) 进行恢复操作了。
你也有可能会说这段代码会有什么用?下面就让我们来真正看看(2) 强
大的威力。(2)才是Dancing Links 的核心.
3 Exact Cover Problem
3.1 Description
上节所说的双向链表的恢复操作会在本节中有重要的作用。下面先让
我们来看一个问题(Exact Cover Problem)。
给定一个01矩阵, 现在要选择一些行,使得每一列有且仅有一个1. 例子
如下:
0 0 1 0 1 1 0
1 0 0 1 0 0 1
0 1 1 0 0 1 0
1 0 0 1 0 0 0
0 1 0 0 0 0 1
0 0 0 1 1 0 1
(3)
对于如上所示的矩阵(3),我们取行集合{1, 4, 5} 便可使每一列有且仅有一
个1。
3.2 Solving an exact cover problem
很明显,exact cover problem 是一个无法用多项式算法解决的问题,解
决方法只有搜索! 且看如下搜索代码:
剩余12页未读,继续阅读
A1119181796
- 粉丝: 0
- 资源: 5
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0