DLX(舞蹈链)
DLX(dancing links)是一种优化的X算法,用于求解精确覆盖问题。
精确覆盖问题,及用一些由1-n组成的集合,从中选择一些集合,使得1-n每个整数正好出现过一次。
对于这种问题,最为朴素的算法就是X算法。虽然名字看起来比较奇怪,但是就是裸的暴力dfs,因此没什么好说的。
而DLX就是对于X算法的优化。当然,因为仅仅是优化,因此复杂度是O(能过)。
对于每一个集合,如果我们选择了它,那么我们就可以删除掉所有包含它包含的数的集合,因为显然这些集合都不能取了。因此,我们从1开始遍历到n,如果这一列还没有取,那么我们就选择一个覆盖了该列的集合,删除其他集合,并且删除掉这个集合的所覆盖的所有列。到最后如果所有列都被删除掉了,那么这就是一个可行解,否则就进行回溯,而DLX算法就是优化了删除列的效率。
算法流程:
我们首先将所有集合转化为01的形式,表示是否覆盖了第i列,然后我们只将1视为节点并在每一列上方建立一个虚拟节点,同时在虚拟节点的最左侧再添加一个虚拟节点0,将每个节点指向其上下左右的节点(最左指向最右,最右指向最左,最上指向最下,最下指向最上),这样,我们在删除时就只需要修改双向链表的指向了。最后,我们只需要判断虚拟节点0的右侧是否还有节点即可。
DLX算法整体是十分简单清晰的,就是将节点转换成为了链表,加速了删除和恢复的速度。此外还有一个优化:每次删除列时优先删除被覆盖的集合数最少的列,这个优化就十分显然了。
具体的实现就上代码吧(参考例题:【模板】舞蹈链(DLX)):
精确覆盖问题,及用一些由1-n组成的集合,从中选择一些集合,使得1-n每个整数正好出现过一次。
对于这种问题,最为朴素的算法就是X算法。虽然名字看起来比较奇怪,但是就是裸的暴力dfs,因此没什么好说的。
而DLX就是对于X算法的优化。当然,因为仅仅是优化,因此复杂度是O(能过)。
对于每一个集合,如果我们选择了它,那么我们就可以删除掉所有包含它包含的数的集合,因为显然这些集合都不能取了。因此,我们从1开始遍历到n,如果这一列还没有取,那么我们就选择一个覆盖了该列的集合,删除其他集合,并且删除掉这个集合的所覆盖的所有列。到最后如果所有列都被删除掉了,那么这就是一个可行解,否则就进行回溯,而DLX算法就是优化了删除列的效率。
算法流程:
我们首先将所有集合转化为01的形式,表示是否覆盖了第i列,然后我们只将1视为节点并在每一列上方建立一个虚拟节点,同时在虚拟节点的最左侧再添加一个虚拟节点0,将每个节点指向其上下左右的节点(最左指向最右,最右指向最左,最上指向最下,最下指向最上),这样,我们在删除时就只需要修改双向链表的指向了。最后,我们只需要判断虚拟节点0的右侧是否还有节点即可。
DLX算法整体是十分简单清晰的,就是将节点转换成为了链表,加速了删除和恢复的速度。此外还有一个优化:每次删除列时优先删除被覆盖的集合数最少的列,这个优化就十分显然了。
具体的实现就上代码吧(参考例题:【模板】舞蹈链(DLX)):
#include <iostream>
#include <cstdio>
using namespace std;
int n, m, cnt, sum, ans[505], num[505], s[505][505];
struct node
{
int l;
int r;
int u;
int d;
int row;
int col;
} a[250005];
void init()
{
for (int i = 0; i <= m; ++i)
{
a[i].l = i - 1;
a[i].r = i + 1;
a[i].u = i;
a[i].d = i;
}
a[0].l = m;
a[m].r = 0;
cnt = m + 1;
return;
}
void add(int k)
{
int first = cnt;
for (int i = 1; i <= m; ++i)
if (s[k][i])
{
a[cnt].l = cnt - 1;
a[cnt].r = cnt + 1;
a[cnt].u = a[i].u;
a[cnt].d = i;
a[a[cnt].u].d = cnt;
a[i].u = cnt;
a[cnt].row = k;
a[cnt].col = i;
++num[i];
++cnt;
}
a[cnt - 1].r = first;
a[first].l = cnt - 1;
return;
}
void remove(int k)
{
a[a[k].l].r = a[k].r;
a[a[k].r].l = a[k].l;
for (int i = a[k].d; i != k; i = a[i].d)
for (int j = a[i].r; j != i; j = a[j].r)
{
a[a[j].u].d = a[j].d;
a[a[j].d].u = a[j].u;
--num[a[j].col];
}
return;
}
void restore(int k)
{
for (int i = a[k].u; i != k; i = a[i].u)
for (int j = a[i].l; j != i; j = a[j].l)
{
a[a[j].d].u = j;
a[a[j].u].d = j;
++num[a[j].col];
}
a[a[k].l].r = k;
a[a[k].r].l = k;
return;
}
bool dfs(int k)
{
if (a[0].r == 0)
{
sum = k;
return true;
}
int mi = a[0].r;
for (int i = a[0].r; i != 0; i = a[i].r)
if (num[i] < num[mi])
mi = i;
remove(mi);
for (int i = a[mi].d; i != mi; i = a[i].d)
{
ans[k + 1] = a[i].row;
for (int j = a[i].r; j != i; j = a[j].r)
remove(a[j].col);
if (dfs(k + 1))
return true;
for (int j = a[i].l; j != i; j = a[j].l)
restore(a[j].col);
}
restore(mi);
return false;
}
int main()
{
scanf("%d%d", &n, &m);
init();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
scanf("%d", &s[i][j]);
for (int i = 1; i <= n; ++i)
add(i);
if (dfs(0))
for (int i = 1; i <= sum; ++i)
printf("%d ", ans[i]);
else
puts("No Solution!");
return 0;
}
评论
发表评论