DLX(舞蹈链)

DLX(dancing links)是一种优化的X算法,用于求解精确覆盖问题。

精确覆盖问题,及用一些由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;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注