`
yzmduncan
  • 浏览: 325992 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

DLX——Dancing Links

阅读更多

    Dancing Links是Knuth教授在近几年来写的一篇文章,是一类搜索问题的通用优化。它主要利用双向十字链表来存储稀疏矩阵,来达到搜索中的优化。在搜索问题中,矩阵会随着递归的加深会变得越来越稀疏,这种情况下用dancelinks来存储矩阵,往往会达到很好的效果。

    核心代码:

    对于熟悉双向链表的人,一定不会陌生:

L[R[x]] = L[x]

R[L[x]] = R[x]

    这两句话时将x从链表中删除。

    但很少有人知道下面两句:

L[R[x]] = x

R[L[x]] = x

    这两句会将已经删除的节点x重新添加回双向链表中。是不是非常神奇。我们在链表中删除,只是进行一个标记,并不真正进行清空内存的操作。可能这不是好的编程习惯,你可能会认为内存泄露,但在这里,我们就是要这种效果。

    给一个0、1矩阵,现在要选择一些(最少)行,使得每列有且仅有一个1,即精确覆盖

    或者,选择一些(最少)行,使得每列至少有一个1,即重复覆盖

    这两个问题都是NP问题,可以用搜索解决,DLX可以大大加快搜索速度。

    精确覆盖:

    首先选择当前要覆盖的列(含1最少的列),将该列和能够覆盖到该列的行全部去掉,再枚举添加的方法。枚举某一行r,假设它是解集中的一个,那么该行所能覆盖到的所有列都不必再搜,所以删除该行覆盖到的所有列,又由于去掉的列相当于有解,所以能够覆盖到这些列的行也不用再搜,删之。

    重复覆盖:

    首先选择当前要覆盖的列(同上),将该列删除,枚举覆盖到该列的所有行:对于某一行r,假设它是解集中的一个,那么该行所能覆盖到的列都不必再搜,所以删除该行覆盖到的所有列。注意此时不用删去覆盖到这些列的行,因为一列中允许有多个1。这里有一个A*的优化:估价函数h意义为从当前状态最好情况下需要添加几条边才能覆盖。

 

例:HDU3111 Sudoku

 

/*
DLX解决9*9的数独问题,转化为729*324的精确覆盖问题
行:
一共9 * 9 * 9 == 729行。一共9 * 9小格,每一格有9种可能性(1 - 9),每一种可能都对应着一行。
列:
一共(9 + 9 + 9) * 9 + 81 == 324 种前面三个9分别代表着9行9列和9小块,乘以9的意思是9种可能(1 - 9),因为每种可能只可以选择一个。
81代表着81个小格,限制着每一个小格只放一个数字。
读入数据后,如果为'.',则建9行,即有1-9种可能,否则建一行,表示某小格只能放确定的某个数字。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x7fffffff;
const int NN = 350;
const int MM = 750;
int n,m;    //列,行
int cntc[NN];
int L[NN*MM],R[NN*MM],U[NN*MM],D[NN*MM];
int C[NN*MM];
int head;
int mx[MM][NN];
int O[MM],idx;
int ans[10][10];

//删除列及其相应的行
void remove(int c)
{
    int i,j;
    L[R[c]] = L[c];
    R[L[c]] = R[c];
    for(i = D[c]; i != c; i = D[i])
    {
        for(j = R[i]; j != i; j = R[j])
        {
            U[D[j]] = U[j];
            D[U[j]] = D[j];
            cntc[C[j]]--;
        }
    }
}

//恢复列及其相应的行
void resume(int c)
{
    int i,j;
    R[L[c]] = c;
    L[R[c]] = c;
    for(i = D[c]; i != c; i = D[i])
    {
        for(j = R[i]; j != i; j = R[j])
        {
            U[D[j]] = j;
            D[U[j]] = j;
            cntc[C[j]]++;
        }
    }
}

bool dfs()
{
    int i,j,c;
    if(R[head] == head)
        return true;
    int min = INF;
    for(i = R[head]; i != head; i = R[i])
    {
        if(cntc[i] < min)
        {
            min = cntc[i];
            c = i;
        }
    }
    remove(c);
    for(i = D[c]; i != c; i = D[i])
    {
        //i是某点的序号,将该点所在行的行号保存
        O[idx++] = (i-1)/n;
        for(j = R[i]; j != i; j = R[j])
            remove(C[j]);
        if(dfs())
            return true;
        for(j = L[i]; j != i; j = L[j])
            resume(C[j]);
        idx--;
    }
    resume(c);
    return false;
}

bool build()
{
    int i,j,now,pre,first;
    idx = head = 0;
    for(i = 0; i < n; i++)
    {
        R[i] = i+1;
        L[i+1] = i;
    }
    R[n] = 0;
    L[0] = n;
    //列双向链表
    for(j = 1; j <= n; j++)
    {
        pre = j;
        cntc[j] = 0;
        for(i = 1; i <= m; i++)
        {
            if(mx[i][j])
            {
                cntc[j]++;
                now = i*n+j;
                C[now] = j;
                D[pre] = now;
                U[now] = pre;
                pre = now;
            }
        }
        U[j] = pre;
        D[pre] = j;
        if(cntc[j] == 0)
            return false;
    }
    //行双向链表
    for(i = 1; i <= m; i++)
    {
        pre = first = -1;
        for(j = 1; j <= n; j++)
        {
            if(mx[i][j])
            {
                now = i*n+j;
                if(pre == -1)
                    first = now;
                else
                {
                    R[pre] = now;
                    L[now] = pre;
                }
                pre = now;
            }
        }
        if(first != -1)
        {
            R[pre] = first;
            L[first] = pre;
        }
    }
    return true;
}

int T;

void print()
{
    int i,j;
    int x,y,k;
    for(i = 0; i < idx; i++)
    {
        int r = O[i];
        k = r%9;
        if(k==0) k = 9;
        int num = (r - k)/9 + 1;
        y = num%9;
        if(y == 0) y = 9;
        x = (num-y)/9 + 1;
        ans[x][y] = k;
    }
    if(idx == 0)
        printf("impossible\n");
    else
    {
        for(i = 1; i <= 9; i++)
        {
            for(j = 1; j <= 9; j++)
                printf("%d",ans[i][j]);
            printf("\n");
        }
    }
    if(T!=0)
        printf("---\n");
}

int main()
{
    int i,j,k;
    int cases;
    char cao[12];
    char s[12][12];
    scanf("%d",&cases);
    T = cases;
    while(T--)
    {
        if(T < cases-1)
            scanf("%s",cao);
        for(i = 1; i <= 9; i++)
            scanf("%s",&s[i][1]);
        memset(mx,0,sizeof(mx));
        for(i = 1; i <= 9; i++)
        {
            for(j = 1; j <= 9; j++)
             {
                int t = (i-1)*9 + j;
                if(s[i][j] == '?')
                {
                    for(k = 1; k <= 9; k++)
                    {
                        mx[9*(t-1)+k][t] = 1;               //81grid 每个小格只能放一个数字
                        mx[9*(t-1)+k][81+(i-1)*9+k] = 1;    //9row 每行数字k只能出现一次
                        mx[9*(t-1)+k][162+(j-1)*9+k] = 1;   //9col  每列数字k只能出现一次
                        mx[9*(t-1)+k][243+((i-1)/3*3+(j+2)/3-1)*9+k] = 1;   //subgrid 每个3*3格子数字k只能出现一次
                    }
                }
                else
                {
                    k = s[i][j] - '0';
                    mx[9*(t-1)+k][t] = 1;               //81grid
                    mx[9*(t-1)+k][81+(i-1)*9+k] = 1;    //9row
                    mx[9*(t-1)+k][162+(j-1)*9+k] = 1;   //9col
                    mx[9*(t-1)+k][243+((i-1)/3*3+(j+2)/3-1)*9+k] = 1;   //subgrid
                }
            }
        }
        n = 324;
        m = 729;
        build();
        dfs();
        print();
    }
    return 0;
}

 

 

例:ZOJ3209 Treasure Map

 

 

/*
题意:在坐标系中,有一个大矩形(长宽不超过30)和一些坐标大小都固定的小矩形(500个),问有没有一种方案使得找出最少的小矩形来覆盖大
矩形。注意,小矩形之间不能重叠。
分析:
    完全覆盖,不能重叠,不禁想到了dance links的精确覆盖问题。将小矩形(500)做行,大矩形的每个小格子(30*30个)做列。
    意思很明显了。。。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x7ffffff;
const int NN = 30*30+10;   //900列
const int MM = 500+10;     //500行
int n,m;    //列和行
int L[NN*MM],R[NN*MM],U[NN*MM],D[NN*MM];
int C[NN*MM];
int head;
int cntc[NN];
int mx[MM][NN];
int x,y;
int result;

void change(int p, int x1, int y1, int x2, int y2)  //矩形能够覆盖到的格子,行覆盖到的列
{
    int i,j;
    for(j = y1+1; j <= y2; j++)
    {
        for(i = x1+1; i <= x2; i++)
        {
            mx[p][(j-1)*x+i] = 1;
        }
    }
}

void remove(int c)
{
    int i,j;
    L[R[c]] = L[c];
    R[L[c]] = R[c];
    for(i = D[c]; i != c; i = D[i])
    {
        for(j = R[i]; j != i; j = R[j])
        {
            U[D[j]] = U[j];
            D[U[j]] = D[j];
            cntc[C[j]]--;
        }
    }
}

void resume(int c)
{
    int i,j;
    R[L[c]] = c;
    L[R[c]] = c;
    for(i = D[c]; i != c; i = D[i])
    {
        for(j = R[i]; j != i; j = R[j])
        {
            U[D[j]] = j;
            D[U[j]] = j;
            cntc[C[j]]++;
        }
    }
}

void dfs(int k)
{
    int i,j,c;
    if(R[head] == head)
    {
        if(result > k)
            result = k;
        return;
    }
    if(k >= result)
        return;
    int min = INF;
    for(i = R[head]; i != head; i = R[i])
    {
        if(cntc[i] < min)
        {
            min = cntc[i];
            c = i;
        }
    }
    remove(c);
    for(i = D[c]; i != c; i = D[i])
    {
        for(j = R[i]; j != i; j = R[j])
            remove(C[j]);
        dfs(k+1);
        for(j = L[i]; j != i; j = L[j])
            resume(C[j]);
    }
    resume(c);
    return;
}

bool build()
{
    int i,j;
    int now,pre,first;
    head = 0;
    memset(cntc,0,sizeof(cntc));
    for(i = 0; i < n; i++)
    {
        R[i] = i+1;
        L[i+1] = i;
    }
    R[n] = 0;
    L[0] = n;
    //列链表
    for(j = 1; j <= n; j++)
    {
        pre = j;
        for(i = 1; i <= m; i++)
        {
            if(mx[i][j])
            {
                now = i*n+j;
                cntc[j]++;
                C[now] = j;
                D[pre] = now;
                U[now] = pre;
                pre = now;
            }
        }
        D[pre] = j;
        U[j] = pre;
        if(cntc[j] == 0)
            return false;
    }
    //行链表
    for(i = 1; i <= m; i++)
    {
        pre = first = -1;
        for(j = 1; j <= n; j++)
        {
            if(mx[i][j])
            {
                now = i*n+j;
                if(pre == -1)
                    first = now;
                else
                {
                    R[pre] = now;
                    L[now] = pre;
                }
                pre = now;
            }
        }
        if(first != -1)
        {
            R[pre] = first;
            L[first] = pre;
        }
    }
    return true;
}

int main()
{
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    int i;
    int t;
    int p;
    int x1,y1,x2,y2;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d %d",&x,&y,&p);
        m = p;      //行
        n = x*y;    //列
        result = INF;
        memset(mx,0,sizeof(mx));
        for(i = 1; i <= p; i++)
        {
            scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
            change(i,x1,y1,x2,y2);
        }
        if(build())
        {
            dfs(0);
            if(result != INF)
                printf("%d\n",result);
            else
                printf("-1\n");
        }
        else
            printf("-1\n");
    }
    return 0;
}

 

例:HDU2295 Radar

 

/*
最小支配集问题:
二分枚举最小距离,判断可行性。可行性即重复覆盖模型,DLX解之。
A*的启发函数:
对当前矩阵来说,选择一个未被控制的列,很明显该列最少需要1个行来控制,所以ans++。
该列被控制后,把它所对应的行,全部设为已经选择,并把这些行对应的列也设为被控制。继续选择未被控制的列,直到没有这样的列。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int INF = 0x7fffffff;
const int MAX = 55;
const double EPS = 1e-8;
int n,m,k;
double city[MAX][2];
double radar[MAX][2];
double dis[MAX][MAX];       //dis[i][j]表示雷达i到cityj的距离

int L[MAX*MAX],R[MAX*MAX],U[MAX*MAX],D[MAX*MAX];
int C[MAX*MAX];
int cntc[MAX];
int head;

int mx[MAX][MAX];
bool vis[MAX];

//删除元素c所在的列
void remove(int c)
{
    int i;
    for(i = D[c]; i != c; i = D[i])
    {
        R[L[i]] = R[i];
        L[R[i]] = L[i];
    }
}

//恢复元素c所在的列
void resume(int c)
{
    int i;
    for(i = D[c]; i != c; i = D[i])
    {
        R[L[i]] = i;
        L[R[i]] = i;
    }
}

int h()
{
    int i,j,c;
    memset(vis,0,sizeof(vis));
    int ans = 0;
    for(c = R[head]; c != head; c = R[c])
    {
        if(!vis[c])
        {
            ans++;
            for(i = D[c]; i != c; i = D[i])
                for(j = R[i]; j != i; j = R[j])
                    vis[C[j]] = true;
        }
    }
    return ans;
}

bool dfs(int dep)
{
    int i,j;
    if(R[head] == head)
        return true;
    if(dep + h() > k)       //A_Star剪枝
        return false;
    int Min=INF,c;
    for(i = R[head]; i != head; i = R[i])
    {
        if(cntc[i] < Min)
        {
            Min = cntc[i];
            c = i;
        }
    }
    for(i = D[c]; i != c; i = D[i])
    {
        remove(i);
        for(j = R[i]; j != i; j = R[j])
        {
            remove(j);
            cntc[C[j]]--;
        }
        if(dfs(dep+1))
            return true;
        for(j = L[i]; j != i; j = L[j])
        {
            resume(j);
            cntc[C[j]]++;
        }
        resume(i);
    }
    return false;
}

bool build(double mid)
{
    int i,j;
    memset(cntc,0,sizeof(cntc));
    memset(mx,0,sizeof(mx));
    for(i = 1; i <= m; i++)
    {
        for(j = 1; j <= n; j++)
        {
            if(dis[i][j] - mid < EPS)
                mx[i][j] = 1;
        }
    }
    head = 0;
    for(i = 0; i < n; i++)
    {
        R[i] = i+1;
        L[i+1] = i;
    }
    R[n] = 0;
    L[0] = n;
    int first,pre,now;
    //列链表
    for(j = 1; j <= n; j++)
    {
        pre = j;
        for(i = 1; i <= m; i++)
        {
            if(mx[i][j])
            {
                cntc[j]++;
                now = i*n+j;
                C[now] = j;
                U[now] = pre;
                D[pre] = now;
                pre = now;
            }
        }
        D[pre] = j;
        U[j] = pre;
        if(cntc[j] == 0)
            return false;
    }
    for(i = 1; i <= m; i++)
    {
        pre = first = -1;
        for(j = 1; j <= n; j++)
        {
            if(mx[i][j])
            {
                now = i*n+j;
                if(pre == -1)
                    first = now;
                else
                {
                    R[pre] = now;
                    L[now] = pre;
                }
                pre = now;
            }
        }
        if(first != -1)
        {
            R[pre] = first;
            L[first] = pre;
        }
    }
    return true;
}

bool OK(double mid)
{
    if(build(mid))
        return dfs(0);
    else
        return false;
}

double solve()
{
    double low = 0;
    double high = 1500;
    double ans = -1;
    while(low+EPS<high)
    {
        double mid = (low+high)/2.0;
        if(OK(mid))
        {
            ans = mid;
            high = mid;
        }
        else
            low = mid;
    }
    return ans;
}

double Dis(int i, int j)
{
    return sqrt((double)(radar[i][0]-city[j][0])*(radar[i][0]-city[j][0])+(radar[i][1]-city[j][1])*(radar[i][1]-city[j][1]));
}

void Init()
{
    int i,j;
    for(i = 1; i <= m; i++)
        for(j = 1; j <= n; j++)
            dis[i][j] = Dis(i,j);
}

int main()
{
    int i;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d %d",&n,&m,&k);
        for(i = 1; i <= n; i++)
            scanf("%lf %lf",&city[i][0],&city[i][1]);
        for(i = 1; i <= m; i++)
            scanf("%lf %lf",&radar[i][0],&radar[i][1]);
        Init();
        printf("%.6lf\n",solve());
    }
    return 0;
}

 

 other: poj3074 hdu3663 2828

 

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics