分享
 
 
 

[回溯法]从蛮力算法起步,谈八皇后问题的求解:

王朝other·作者佚名  2006-02-01
窄屏简体版  字體: |||超大  

[回溯法]从蛮力算法起步,谈八皇后问题的求解:

By EmilMatthew

05/9/15

八皇后是一个相当著名的算法问题:题目说是在8*8国际象棋棋盘上,要求在第一行放置一个皇后,且能做到在竖方向,斜方向都没有冲突。

这里首先谈一下解集合的选取方式,如果用一个二维数组来存放八皇后的位置,难免比较浪费,注意到八个皇后不可能位于同一行,所以只要存放各个皇后在竖方向的位置即可。所以存放解集仅需要一个长度为8的整型数组即可.

首先看到这个问题,最容易想到的想法就是穷举法,每次在当前行中的第一列起摆当前这个皇后的位置,发现有冲突时则终止当前的次的搜索,当发现当前的这个行的皇后与前面的皇后没有冲突时,则跳到下一行,继续从第一列起摆放皇后的位置.如果当前行的皇后已摆至最后一列了,则应跳到上一行.

由于行数已经不可能相同了,所以了不起也就是做一个8!的次运行次数的算法便可以得到最终解了.不过,很快,这种自然的一蹋糊涂的想法便要被打住了,如果不是8皇后呢,如果是20皇后呢?效率低不说,光是要修改源程序这一个不足点便可以将这种想法否决掉了.

优化的出路在哪里呢,其实,改进的工作也没有动啥”大手术”,主要是做到下面两件事情:

1) 一旦当前的集不满足条件时,便终止当前的搜索树的分枝,并回退到前一层继续搜索.

(其实,前面的蛮力法退出是满足的,就是这个回退做不了。)

2 如果当前的解满足部分解的条件时,则继续跳到下一行搜索,发现有全解时终止搜索.

(前面的蛮力法做这个也是没问题的)

关于搜索树的最基本的想法,可以参考我前面的一篇愚作---http://blog.csdn.net/emilmatthew/archive/2005/08/03/445132.aspx

所以,从蛮力法跳到相对“高级”的回溯法我们就提高了一步----能回退到上一层.

而这个动作,可以通过递归和非递归两种方式来实现,递归的会相对好理解些,另一种非递归的也不难理解的.

而一旦使用回溯法,则程序的柔韧性得到了极大的提高,可以求解N皇后问题.

在展示最后的实现版本之前,先来看几个输助的函数,判定是否有冲突和是否局部完成位置的函数。

由于我们的结果数组存放的仅仅是列中的位置,而行中的位置肯定是相异的,所以,只需要判定斜方向是否有冲突和竖直方向是否有冲突就可以了:

//判定当前结点在斜方向和另一个结点是否有冲突:

int checkXiePos(int r1,int r2,int c1,int c2)

{

return !(fabs(r1-r2)==fabs(c1-c2));

}

//判定当前结点和所有已搜索的竖直方向上的结点是否有冲突.

int checkVPos(int* arr,int len)

{

int flag=1;

int i,j;

assertF(arr!=NULL,"in checkVPos,arr is null\n");

for(i=0;i<len-1;i++)

for(j=i+1;j<len;j++)

if(arr[i]==arr[j])

{

flag=0;

break;

}

return flag;

}

//总的判定当前结点和已搜索结点之前是否有冲突的函数:

int partFinished(int* arr,int len)

{

int flag=1;

int i,j;

assertF(arr!=NULL,"in partFinished,arr is null\n");

flag=flag&&checkVPos(arr,len);

for(i=0;i<len-1;i++)

for(j=i+1;j<len;j++)

{

flag=flag&&checkXiePos(i,j,arr[i],arr[j]);

if(!flag)goto out;

}

out:

return flag;

}

//判定是完成了一个N皇后的排列,用的还是partFinished,但在算法的表达上更为贴切.

int fullFinished(int* arr,int len)

{

assertF(arr!=NULL,"in fullFinished,arr is null\n");

eturn partFinished(arr,len);

}

好了,有了这些底层的函数作为铺垫,那么再来实现我们上层的算法那就要清楚和明朗多了.

1) 首先看一下递归版本的实现: (相当的简洁和好懂)

//NqueensProblems Solution Recursive1 Search and Print out all the answers.

void NQueensProblem2(int* arr,int depth,int size,int* count,FILE* outputFile)

{ /*default:a[1..n]=0 , 0 , size, 1, outputFile*/

//nowSize,finished rows. [1..n]

//size,total problem size. [n]

int i=0;

assertF(outputFile!=NULL,"in NQueensProblems2 outputFile is null\n");

assertF(count!=NULL,"in NQueensProblems2 count is null\n");

if(!partFinished(arr,depth+1))return;

//如果当前的结点和前面的结点有冲突,则终断当前搜索的子分支.

else if(fullFinished(arr,size)&&depth+1==size)/*如果全部完成了,则同样终断当前搜支,并打印出当前的结集.*/

{

fprintf(outputFile,"Answer of%dQueens Problem No.%d:\r\n",size,*count);

(*count)++;//结果数目加1

}

else //partFinished ,部分解

{

depth++; //branch to a deeper levels,展开搜索树到下一个深度搜索

for(i=0;i<size;i++)

{

arr[depth]=i+1;//搜索下一个深度的所有结点

//because it is a depth first search ,it will not affect another search branch.

NQueensProblem2(arr,depth,size,count,outputFile);

}

}

}

这个递归的版本有一个不足之处在于,第一层树的展开工作要手工来做:

即:

for(i=0;i<problemSize;i++)

{

ansCol[0]=i+1;//first level branch. node the col pos is between [1..n]

NQueensProblem2(ansCol,0,problemSize,count,outputFile2);

}

2有了递归版本作铺垫,再来看这个非递归版本也不会有太大的困难了:

//Nqueens Problem Solution1 Unrecursive,could get the full or only one answer set.

void NQueensProblem1(int size,int mode)

{

//attention ,the output position use 1...n.

int* arr;

int i=0,k=0;

int count=0;

FILE* outputFile;

outputFile=createFile('w',"NQueensAns.txt");

arr=(int*)malloc(sizeof(int)*size);

for(i=0;i<size;i++)

arr[i]=0;

k=0;

count=1;

while(k>=0)//k: stands for the branch tree's levels,which start from 0 to size-1

{

while(arr[k]<=size-1)//arr[0..size-1]: stands for the v position of the queens.from(1 to size).

{

arr[k]++;//search the parallel level's next possible position.

if(fullFinished(arr,k+1)&&(k+1==size))//full answer check.

{

fprintf(outputFile,"Answer of%dQueens Problem No.%d:\r\n",size,count);

outputListArrInt(arr,0,size,outputFile);

outputQueensAns(arr,size,outputFile);

count++;

if(!mode)/*no need all resolved.根据参数调节是否要输出全部解集,如果/。要,则从这里跳出.*/

goto out;

}

else if(partFinished(arr,k+1))//if only part finished. Branching to a deeper level.

{

k++;//move to a deeper level---branching new search child tree.

}

}

/*If current search has no solution ,roll back to the up level*/

arr[k]=0;//set current node to unUsed.

k--;//roll back to the pre level.

}

out:

free(arr);

}

3这里给出第三个版本,同样是一个递归的版本,这个版本只能打到第一组解,但是比较好的地方在于可以不用在外部调用层把第一层的情况给展开:

void NQueensProblem3(int* arr,int depth,int size,int* count,FILE* outputFile)

{ //arrValue=1..n 0 .. size-1

assertF(outputFile!=NULL,"in NQueensProblems2 outputFile is null\n");

assertF(count!=NULL,"in NQueensProblems2 count is null\n");

if(depth>=size-1&&partFinished(arr,depth+1))

{

fprintf(outputFile,"Answer of%dQueens Problem No.%d:\r\n",size,*count);

outputListArrInt(arr,0,size,outputFile);

outputQueensAns(arr,size,outputFile);

(*count)++;

}

else if(!partFinished(arr,depth+1)||arr[depth]>size)//have chong tu

{

if(arr[depth]>=size)//roll back to the pre level

{

arr[depth]=1;

depth--;

arr[depth]++;

NQueensProblem3(arr,depth,size,count,outputFile);

}

else{ //search for the parallel row's next possible position

arr[depth]++;

NQueensProblem3(arr,depth,size,count,outputFile);

}

}

else //part answer is ok ,branch to a deeper level for search.

{

depth++;

arr[depth]=1;//here,at first you use 0 as start pos,wrong!

NQueensProblem3(arr,depth,size,count,outputFile);

}

}

插一句:关于第三个版本的调试.

现在看看上面这个递归版本也是相当清楚的,但我调试时却调了半天。下面把我调试记录文件中最后的比较重要的几步贴出来,和大家共同分享程序设计过程中所遇到的点点滴滴。可能有些乱的话.

debug1

else //part answer is ok ,branch to a deeper level for search.

{

//printf("%d-",arr[1]);

//push_Seq(myStack,arr[depth]);//storage current level's col pos

depth++;

arr[depth]=1;//here,at first you use 0 as start pos,wrong!

fprintf(outputFile,"brahch to deeper to %dlevel\r\n",depth);

fprintf(outputFile,"pre level node val:%d\r\n",arr[depth-1]);

outputListArrInt(arr,(int)0,(int)size,outputFile);

NQueensProblem3(arr,depth,size,count,outputFile);

}

brahch to deeper to 1level

pre level node val:1

1 1 1 1

brahch to deeper to 2level

pre level node val:3

1 3 1 1

brahch to deeper to 3level

pre level node val:5

1 3 5 1

从这个错误中,可以看出,由于没有对partResolve的上限加以限定,导致部分解没有上限~~~

debug2

试图将成功的条件上移,但是对上面的BUG是无效的.

if(depth>=size-1&&partFinished(arr,depth+1))

{

fprintf(outputFile,"Answer of%dQueens Problem No.%d:\r\n",size,*count);

outputListArrInt(arr,0,size,outputFile);

outputQueensAns(arr,size,outputFile);

(*count)++;

}

将部分不成功解中,回到上层的判定条件改成>=size

if(arr[depth]>=size)//roll back to the pre level

brahch to deeper to 3level

pre level node val:2

1 4 2 1

roll back to 2level

roll back to 1level

brahch to deeper to 2level

pre level node val:4

1 4 1 1

brahch to deeper to 3level

pre level node val:2

1 4 2 1

roll back to 2level

roll back to 1level

brahch to deeper to 2level

pre level node val:4

1 4 1 1

在第一个主分叉中的最后一棵子树中出现的死循环,原因在于当本层与先前没有冲突但已到最后一个位置时,会新生成一棵子树,然后,子树不成功,退上来,再生成,再退...

3解决方案,在不成功处加一个判定:

!partFinished(arr,depth+1)||arr[depth]>size)

if(arr[depth]>=size)//roll back to the pre level

{

arr[depth]=1;

depth--;

fprintf(outputFile,"roll back to %dlevel\r\n",depth);

arr[depth]++;//加了这一句~~~,好~~

//本来写的是if(arr[depth]<size)arr[depth]++;

//虽然看到了有多余位置的BUG,但是没挑准地方.

NQueensProblem3(arr,depth,size,count,outputFile);

}

BUG找到了,第三个版本的递归Version也实现了,呵呵~~~

算法效率的简单测试.

size=10,not all answer

version:1 time:0.0000s

version:3 time:0.0000s

Answer of10Queens Problem No.1:

1 3 6 8 10 5 9 2 4 7

(o代表皇后,*代表空余位)

o * * * * * * * * *

* * o * * * * * * *

* * * * * o * * * *

* * * * * * * o * *

* * * * * * * * * o

* * * * o * * * * *

* * * * * * * * o *

* o * * * * * * * *

* * * o * * * * * *

* * * * * * o * * *

================================================

size=15,not all answer

version:1 time:0.0930s

version:3 失效了,估计程序有错误.

size=10, all answer.(包括打出程序的结果)

version:1 time:0.89100s

version:2 time:0.53100s

当size变得更大时,程序的运行就有些长了,size=20时,第一个版本的竟然在南海诸求一组解时用了32秒,而第二个版本在一分钟内已经算不出来了~~~~

所以,求解更大规模的皇后问题,这样的程序和算法还是扛不住~~~,继续学习~~~~

源码下载,欢迎提出批评意见:

http://free5.e-168.cn/hhucskx/download/EightQueens.rar

如果直接点击无效的话,请把上面这个地址直接粘贴到IE地址栏中下载.

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有