• 如果喜欢本站,您可以按CTRL+D收藏本站,方便下次访问。

  • 欢迎来自五湖四海的朋友,期待为您分享有价值的资源 :oops:

Dancing links算法

技术分享 第四度 7年前 (2013-09-09) 78次浏览 0个评论 扫描二维码

file

Dancing Links算法由Knuth设计并命名,用于解决精确覆盖问题。 这样的问题就是,给定一个01矩阵,要求挑出它的若干行,组成的子矩阵满足条件:每一列恰有一个1。 解决的办法是把矩阵的每一行每一列的非零元1用双十字链表结构链接起来,方便删除和回溯。然后依次尝试每一种可能的情形。 具体参见原文。

#include<iostream>
#include<stdlib.h>
#include <conio.h>
#include <time.h>
using namespace std;

const int N=60009;
const int M=70;

int data[N][M];
int S[N];
int R[N][M];
int L[N][M];
int U[N][M];
int D[N][M];

int col;
int row;
int res[N];

void cover(int c)
{
    int i,j;
    L[0][R[0][c]]=L[0][c];
    R[0][L[0][c]]=R[0][c];
    for(i=D[0][c];i!=0;i=D[i][c])
    {
        for(j=R[i][c];j!=c;j=R[i][j])
        {
            U[D[i][j]][j]=U[i][j];
            D[U[i][j]][j]=D[i][j];
            S[j]--;

        }
    }

}

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

}

void search(int n)
{
    int i,j,c,r;
    c=R[0][0];
    for(i=R[0][0];i!=0;i=R[0][i])
    {
        if(S[i]<S[c])
            c=i;
    }

    if(c==0)
    {
        for(i=0;i<n;i++)
            cout<<res[i]<<'t';
        cout<<endl;
        for(j=0;j<n;j++)
        {
            for(i=1;i<=col;i++)
                cout<<data[res[j]][i];
            cout<<endl;
        }

    }
    else
    {
        cover(c);
        for(r=D[0][c];r!=0;r=D[r][c])
        {
            for(j=R[r][c];j!=c;j=R[r][j])
            {
                cover(j);
            }
            res[n]=r;
            search(n+1);
            for(j=L[r][c];j!=c;j=L[r][j])
            {
                uncover(j);
            }
        }
        uncover(c);
    }
}
void init()
{
    int i,j;
    int tmp;
    srand((unsigned)time(NULL));
    for(i=1;i<=row;i++)
    {
        for(j=1;j<=col;j++)
        {

        //  data[i][j]=rand()%2;
            cin>>data[i][j];
            if(data[i][j]==1)
                S[j]++;
        }

    }
    for(i=0;i<=col;i++)
    {
        L[0][i]=(i+col)%(col+1);
        R[0][i]=(i+1)%(col+1);
    }
    for(i=1;i<=row;i++)
    {
        tmp=0;
        for(j=1;j<=col;j++)
        {
            if(data[i][j]==1)
            {
                R[i][tmp]=j;
                L[i][j]=tmp;
                tmp=j;
            }
        }
        R[i][tmp]=R[i][0];
        L[i][R[i][0]]=tmp;

    }
    for(i=1;i<=col;i++)
    {
        tmp=0;
        for(j=1;j<=row;j++)
        {
            if(data[j][i]==1)
            {
                U[j][i]=tmp;
                D[tmp][i]=j;
                tmp=j;
            }
        }
        D[tmp][i]=0;
        U[0][i]=tmp;
    }

}
int main()
{
    cin>>row>>col;
    init();
    search(0);
    return 0;
}
/*
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
*/

本网站采用BY-NC-SA 4.0协议进行授权 | 转载请注明原文链接:https://www.disidu.com/post/1308.html
如果觉得本文对您有帮助或者您心情好~可以微信打赏支持一下本站:↓↓↓
喜欢 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址