• N皇后问题是很经典的一个问题[CSP中大家已经失去兴趣的一个问题],本菜感概下,所以把相关自己写过的程序都总结下,加深下理解这类问题的解法.

1.朴素的回溯法:朴素的定义是单纯的BT+单层FC解法;这里引用了<算法艺术>的实现,我用used1,used2,used3分别作为行,主对角线,副对角线的可行值!->映射为0->2*(n-1),主对角线为n-1+(y-x),而副对角线为y+x.思路很简单,代码如下:

int used1[MAX], used2[MAX], used3[MAX];
//MACRO,又来宏,引用jon的实现
#define setT(bit, i) (bit[(i)>>5]|=(1<<((i)&0x1f)))
#define resetT(bit, i) (bit[(i)>>5]&=~(1<<((i)&0x1f)))
#define testT(bit, i) (bit[(i)>>5]&(1<<((i)&0x1f)))

void itersearch(int n){//Note:纯的迭代框架
    for(int i=0; i>-1;){
        for(;queen[i]<n;queen[i]++){//y-x+n, and y+x
            //test(used1, queen[i])
            if(!testT(used1, queen[i])&&!testT(used2, queen[i]-i+(n-1))&&!testT(used3, queen[i]+i)){
                //set
                setT(used1, queen[i]),setT(used2, queen[i]-i+(n-1)),setT(used3, queen[i]+i);
                if(i==n-1){
                    total++;
                    //reset,我这里开始写的时候忘记了,FT,卡了1分钟,忽然醒悟
                    resetT(used1, queen[i]),resetT(used2, queen[i]-i+(n-1)),resetT(used3, queen[i]+i);
                }
                else{
                    i++;
                    queen[i]=-1;
                }
            }
        }
        //queen[i]==n
        i–;
        //reset
        resetT(used1, queen[i]),resetT(used2, queen[i]-i+(n-1)),resetT(used3, queen[i]+i);

        queen[i]++;
    }
}

void search (int dep, const int n){
    int i;
    if(dep==n) tot++;
    else{
        for(i=0; i<n; i++){
            if(!testT(used1, i)&&!testT(used2, i-dep+(n-1))&&!testT(used3, dep+i)){
                setT(used1, i),setT(used2, i-dep+(n-1)),setT(used3, dep+i);
                search(dep+1, n);
                resetT(used1, i),resetT(used2, i-dep+(n-1)),resetT(used3, dep+i);
            }
        }
    }//else
}

2.关于朴素算法的思考,你看我那么辛苦的用三个数组来禁位,确实很麻烦.好参考Matrix67的代码,改成c++如下,其实思路是一样的,代码我加了注释[我觉得这个代码可以称的上编程之美,造化巧妙].不敢隐大牛的地址如下:http://www.matrix67.com/blog/archives/266/comment-page-1,至于上面引用的dd大牛的Gray码解女友群问题,哈哈,没那个本事,人专注和专一点好!不过感兴趣的话,你可以写个程序来管理下,反正不难10行搞定!

void BQueen(int row, int ld, int rd, const int n, const int upper, int& sum){
    if(row==upper) sum++;
    else{
         int pos=(upper&(~(row|ld|rd)));//clr bits,所有的占用位求反,可得当前可用的位
         while(pos>0){//left bits yeah!
            int p=(pos&(-pos));//-a=~(a+1), the most right side bit,最右边的1,没啥说的,实在不懂看BOP
            pos=pos-p;
            BQueen(row+p,(ld+p)<<1,(rd+p)>>1, n, upper, sum);//<<1,>>1这个很有趣,把对角线映射到下一行上,一个左移,一个右移[左边第一位的对角线限制为0,因此若第一位置位那么实际上是无影响的,OK,没其他说的了!右边同理]
        }
    }
}

3.但朴素的算法能否修正呢,先用MRV来做一个,用下一位值域的非递减序列!这里随便写个,示意而已[如果在BQueen上修改的话,可以加上1位统计代码如下]。计算有多少个1,二分法计算每个unsigned int数

int forIntOne(unsigned int s){//当然可以优化,但这种代码最能表现原始企图,因此不改了,代码还是看得懂得好
        int v=(s&0x55555555)+((s>>1)&0x55555555);
        v=(s&0x33333333)+((s>>2)&0x33333333);
        v=(s&0x0f0f0f0f)+((s>>4)&0x0f0f0f0f);
        v=(s&0x00ff00ff)+((s>>8)&0x00ff00ff);
        v=(s&0x0000ffff)+((s>16)&0x0000ffff);
        return v;
    }

//MRV实现如下

void search (int dep, const int n){
    int i;
    if(dep==n) tot++;
    else{
        LNode cand[n];//Herusic Method
        int index=0;
        for(int i=0; i<n; i++){
            if(!used[i][0]&&!used[i-dep+n-1][1]&&!used[i+dep][2]){
                //valid for current selection
                used[i][0]=used[i-dep+n-1][1]=used[i+dep][2]=1;
                //counting next possibility
                int key=0;
                for(int i=0; i<n; i++) key+=(~(used[i][0]&used[i][1]&used[i][2]));//一个禁位计算
                int j=index;
                for(;j-1>=0&&key>cand[j-1].key; j–) cand[j]=cand[j-1];
                cand[j].key=key,cand[j].i=i;
                index++;
                used[i][0]=used[i-dep+n-1][1]=used[i+dep][2]=0;
            }
        }
        for(int i=0; i<index; i++){//don’t need to maintain status
            int curi=cand[i].i;
            if(!used[curi][0]&&!used[curi-dep+n-1][1]&&!used[curi+dep][2]){
                used[curi][0]=used[curi-dep+n-1][1]=used[curi+dep][2]=1;
                search(dep+1, n);
                used[curi][0]=used[curi-dep+n-1][1]=used[curi+dep][2]=0;
            }
        }
    }//else
}

但这种算法在运行时确差强人意,为什么?因为每次迭代都要排序,系统在这上面折腾的时间太多,但假如兴趣的话,在NQueen版本上的修改,通常不会让你失望的,当然N在适当大的时候[我们假设N->4,完全没必要排序,而较大的解,我可以用修正算法来做,所以算法嘛,要因地制宜]

3.当然我们可以用修正构造的方式来解Queen问题,下面的代码是CSDN上的,但他是修正一个解的代码,稍微动下脑筋,其实可以将修正代码和iterative的版本结合在一起对于一个到最后无解的近似解[或者说满足小于修正因子的解],单独运行修正程序,我想估计这就是lrj神牛说的吧!猜测,仅猜测!

//repair naive version
void repairApproach(int n);//size of n
bool repair(int* q, int n, int& maxconf);
int getConfNum(int* q, int n, int i);

//implementation
void repairApproach(int n){
    int* q=new int[n];
    int maxconf=n;//supposed max number
    srand((unsigned)0);
    while(maxconf!=0){//haven’t eliminate the maxconf
        for(int i=0; i<n; i++) q[i]=rand()%n;
        bool required=true;
        while(required=repair(q, n, maxconf));
    }
    delete[] q;
}

bool repair(int* q, int n, int& maxconf){
    maxconf=-1;
    bool required=false;
    for(int i=0; i<n; i++){
        int orgVal=q[i], minVal=q[i], minconf=n;
        for(int j=0; j<n; j++){//trial for each value
            q[i]=j;
            int confnum=getConfNum(q, n, i);
            if(confnum<minconf){
                minconf=confnum, minVal=j;
            }
        }
        q[i]=minVal;
        if(orgVal!=minVal) required=true;//not equal, change currently
        if(minconf>maxconf) maxconf=minconf;//maxconf is the max of all minmal num
    }
    return required;
}

//get number of columns that conflct with column i
int getConfNum(int *q, int n, int i ){
 int num = 0;
 for(int j=0; j<n; j++){
  if (j==i)continue;
  if (q[j]==q[i]) num++;
  else if (q[j]-q[i]==j-i) num++;
  else if (q[j]-q[i]==i-j) num++;
 }
 return num;
}

4.最后的最后,当然要说最强的方法啦,不过很难证明,参见《challenging.mathematical.problems.with.elementary.solutions》。主要方法如下:

一、当n mod 6 != 2 或 n mod 6 != 3时,有一个解为:

2,4,6,8,…,n,1,3,5,7,…,n-1       (n为偶数)

2,4,6,8,…,n-1,1,3,5,7,…,n       (n为奇数)

(上面序列第i个数为ai,表示在第i行ai列放一个皇后;… 省略的序列中,相邻两数以2递增。下同)

二、当n mod 6 == 2 或 n mod 6 == 3时,

(当n为偶数,k=n/2;当n为奇数,k=(n-1)/2)

k,k+2,k+4,…,n,2,4,…,k-2,k+3,k+5,…,n-1,1,3,5,…,k+1         (k为偶数,n为偶数)

k,k+2,k+4,…,n-1,2,4,…,k-2,k+3,k+5,…,n-2,1,3,5,…,k+1,n       (k为偶数,n为奇数)

k,k+2,k+4,…,n-1,1,3,5,…,k-2,k+3,…,n,2,4,…,k+1               (k为奇数,n为偶数)

k,k+2,k+4,…,n-2,1,3,5,…,k-2,k+3,…,n-1,2,4,…,k+1,n           (k为奇数,n为奇数)

引用袁牛的话“我没得那个智商,研究这个数学”,懒得管了,抄了段代码了事!对于不感兴趣的事,直接闪过!

void math(int n){
    int i;
    if (n%6!=2&&n%6!=3){
   for (i=2;i<=n;i+=2) printf("%d ",i);
   for (i=1;i<n-1;i+=2) printf("%d ",i);
   printf("%d\n",i);
  }
  else if ((n/2)&1){
   for (i=n/2;i<n;i+=2) printf("%d ",i);
   for (i=1;i<(n/2)-1;i+=2) printf("%d ",i);
   for (i=n/2+3;i<=n;i+=2) printf("%d ",i);
   for (i=2;i<n/2;i+=2) printf("%d ",i);
   printf("%d\n",i);
  }
  else{
   for (i=n/2;i<=n;i+=2) printf("%d ",i);
   for (i=2;i<(n/2)-1;i+=2) printf("%d ",i);
   for (i=n/2+3;i<n;i+=2) printf("%d ",i);
   for (i=1;i<n/2;i+=2) printf("%d ",i);
   printf("%d\n",i);
  }
}

可以看出CSP问题的套路还是相当清晰,而且理论思路也很清晰,了解到这个程度,可以了,以后有需要再认真研究吧!

  • 好,搜索的结语:开始我不明白lrj为什么说搜索是最难的,现在我明白了,搜索难是难在它的外延直接与人工智能接壤,而且对于确定的算法模型而言,非确定的人为因素很多,一个好的启发函数和好的框架,可以比一个一般或者坏的框架性能和思路都优越很多很多[典型的坏框架就是本菜的代码,俄!写的巨庞大无比,写到后面沾了点牛尾巴气,还算写得能看得过去了!当然思路的学习才是最大的提高]

那我学到了什么呢?

  • 简单的搜索框架:DFS,BFS[应该是熟练程度吧,例题:最优程序],以及双向广度搜索[例题:Color Hash];优点是什么,缺点是什么!
  • 重要的启发搜索问题:A*和IDA*框架[例题:编辑书稿,埃及分数],A*的空间要求太高,因此IDA*用迭代的方式来缓解空间危机。博大精深的启发函数
  • 博弈问题算法:Min-Max,Neg-Max框架,以及Alpah-Beta剪枝的框架问题[可以用动规解的,例题:三角形大战],这两种是基于DFS的搜索算法;而基于BFS的搜索算法呢,SSS*和AB-SSS*算法[AB-SSS*的框架实际上是一种DFS下的迭代框架,和IDA*差不多]
  • 两类问题:路径寻找问题[例题:外公的难题],以及限制满足问题[例题:N皇后问题]
  • 两种思想

1。剪枝思想:最优,极大极小的极端剪枝;基于数学模型的剪枝;基于动态规划的问题转化[状态压缩的模型搞的我之痛苦,不过现在看起来也不过是动规的一种变化而已,难在用数学优化!][例题:1M多,水题居多]

2。参数搜索思想:极大极小的一种变化而已。[例题:抄写书稿,可与动规相互转化]

先结一下,以后再有空再说搜索吧,下一个部分了,同时再回头复习下动规呀,分治这些东西了,练习下自己的白纸编程!

PS:看到dd大牛的一首诗歌,很有感概,大牛果真是大牛,情诗都写得气势不凡,小菜佩服!左手程序右手诗

Advertisements