【人工智能】首选爬山法+随机交换法实现N皇后问题求解（C语言）

1.原理

爬山法（Hill Climbing）是一种局部搜索算法。局部搜索算法不关心求解目标的路径，只要求找到符合要求的解，通常对最优化问题十分有用。爬山法使用启发式函数（或代价评估函数）确定“标高”，找到目标的解就是要找到最高峰，即全局最大值。但是我们知道山外有山，山外还有一望无际的平原。爬山法存在局部最大值、山脊、高原等问题。爬山法经常被卡在某个局部最大值（或最小代价处），其成功率低到只有14%.解决此办法的通常思路是：使用随机爬山法（随机选择一个优于当前状态的状态）、首选爬山法（首先选择第一个优于当前状态的状态、对于上千后继比较管用）、随机重启爬山法（Random restart hill climbing,先随机生成一个初始状态，若不行再随机生成一个初始状态，直到找到目标）

N皇后问题的版本有：

（1）求解的个数

（2）求所有解（摆放方法）

（3）求一个解

其求解方法有：回溯法、递归法、深度优先搜索法等。甚至还有直接O(n)求解的算法,如https://blog.csdn.net/lyy289065406/article/details/78955101

本文以爬山法为例求解问题（3），权当一个例子。

2.数据结构

（1）皇后位置的表示

皇后有N个，需摆放在N*N的棋盘上，一种比较好的方法是用一个大小为N的数组来存放其位置。如：int s[N],第i行（或第一列）皇后存放的位置是s[i]

（2）冲突皇后的表示

一共有三条线：列冲突（生成初始状态时，每行一个、行不冲突）、主副对角线冲突（共2*N-1个），用三个数组表示：col[N]、pdiag[N]、cdiag[N]

#include 
#include 
#include 
#include #define SIZE 8
#define swap(a,b) {int t = a; a = b; b = t;}int s[SIZE]={0};
//int row[1000]={0};//row[i]表示第i行有几个皇后
int row[SIZE]={0};
int col[SIZE]={0};//col[i]表示第i列有几个皇后 
//pdiag[i]表示第i根主对角线（principal diagonal）皇后个数（从左上到右下的线） 
int pdiag[SIZE*2-1]={0};
//pdiag[i]表示第i根副对角线（counter diagonal）皇后个数（从右上到左下的线） 
int cdiag[SIZE*2-1]={0};

3.随机生成N个皇后、打印棋盘等

//打印棋盘
void  print(int s[]){  printf("\n");for(int i=0;i

 int  heuristic(int s[]){//重新对列、主、副对角线置0memset(row,0,sizeof(col)); memset(col,0,sizeof(col));memset(pdiag,0,sizeof(pdiag));memset(cdiag,0,sizeof(cdiag));int h=0;int s2=2*SIZE;for(int i=0;i

//将第row1行中的现有皇后调整到第col1列，然后计算其评估值
//h为现有评估值 
int adjust(int s[],int row1,int col1,int h)
{//列上增加值 int nowCol=s[row1];//现在第row1行皇后所在列位置 h+=(col[col1]-col[nowCol]+1);//主对角线上增加值 h+=(pdiag[row1-col1+SIZE-1]-pdiag[row1-nowCol+SIZE-1]+1);//副对角线上增加值  h+=(cdiag[row1+col1]-cdiag[row1+nowCol]+1); return h;
}

//接受第row1行的皇后移动到col1列
void accept(int s[],int row1,int col1)
{col[s[row1]]--;pdiag[row1-s[row1]+SIZE-1]--;cdiag[row1+s[row1]]--;s[row1]=col1;col[col1]++;pdiag[row1-col1+SIZE-1]++;cdiag[row1+col1]++;
}

int findTwo(int s[])
{int col0,col2,flag=0;int row0,row2;for(int i=0;i

void exchange(int s[],int c)
{int r1,r2,r3,r4,k1=0,k2=1;do{srand((unsigned)time(NULL)+k1);r1=rand()%(SIZE);r2=rand()%(SIZE);k1++;}while(r1==r2);swap(s[r1],r2);do{srand((unsigned)time(NULL)+c+k2);r3=rand()%(SIZE);r4=rand()%(SIZE);k2++;}while(r3==r4);swap(s[r3],r4);
}

int hillClimbing(int s[]){int h=heuristic(s);int curr=h;//当前评估代价int min=h;//最小代价int lastMin=h;//上一轮最小代价//下面这几个都是计数器//int counter=0;//最初想随机选择一个优于当前的状态的后继int c=0;//迭代轮次int cc=0;//交换次数int k=0;//没大用while (1){//counter=0;c++;int flag=0;int minValue=s[0],minLine=0;//分别为：代价最小时的皇后的列号、行号for(int i=0;i

//最前面有个符号常量SIZE表示皇后的个数，可修改它，看不同皇后个数花费的时间int main(int argc,char *argv[]) {//int s[SIZE]={4,5,6,3,4,5,6,5};//int s[SIZE]={2,0,6,3,1,4,7,5};randomQueen(s,SIZE);printf("开始大小:%d\n",heuristic(s));printf("\n次数：%d\n",hillClimbing(s));printf("结束大小：%d\n",heuristic(s));    return 0; }

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！