人工智能試驗報告_八皇后問題

1、八里后問題八皇后問題是一個古老而著名的問題,是回溯算法的典型例題.該問題是 十九世紀著名的數(shù)學家高斯1850年提出：在8X8格的國際象棋上擺放八個皇后,使其不能互相攻擊,即任意兩個皇 后都不能處于同一行、同一列或同一斜線上,問有多少種擺法.根本思想：在open表中保存已生成而未考察的結(jié)點,并用啟發(fā)函數(shù)h(x)對它們?nèi)窟M行估價,從中選出最優(yōu)結(jié)點進行擴展,而不管這個結(jié)點出現(xiàn)在搜索樹的什么地 方.(1)把初始結(jié)點S0放入open表中,計算h(S0);(2)假設open表為空,那么搜索失敗,EXIT(3)移出open表中第一個結(jié)點N放入closed表中,并冠以序號n(4)假設目標結(jié)點Sg=N那么搜索

2、成功,EXIT(5)假設N不可擴展,那么轉(zhuǎn)步驟；(6)擴展N,計算每個子結(jié)點x的函數(shù)值h(x),并將所有子結(jié)點配以指向 N的返回指針后放入open表中,再對open表中的所有子結(jié)點按其函數(shù)值大小 以升序排序,轉(zhuǎn)步驟2; 采用啟發(fā)式修補解N皇后問題#include<time.h>#include <iostream>采用啟發(fā)式修補解N皇后問題#include<time.h>#include <iostream>using .namespace std;void shuffle(int Queen,const int n).隨機取得各行的初始皇后位置

3、,以Queeni表示第i行的皇后位置for(int i=0;i<n;i )Queeni=abs(rand()%n;int collision(int Queen,const int row,const int column,const int n).計算每個位置的沖突值int bug=0;for(int i=0;i<n;i ).if (i!=row)&&(Queeni=column|(Queeni-column)=(i-row)|(Queeni-column)=(row-i)/ 同列,同對角線的情況bug ;return bug;void show(int Quee

4、n,const int n).打印皇后圖cout<<"廠"；for(int k=0;k<n-1;k )cout<<" 丁"cout<<" 丁"<<endl;for(int i=0;i<n-1;i ).cout<<" "for(int j=0;j<n;j )cout«(j=Queeni)? "X"：I喻皇后的位置用"X"cout«endl;cout«" p&qu

5、ot;forQ=0;j<n-1;j)cout«"十；cout«" +"«endl;cout«" |for(int j=O;j<n;j)cout«(j=Queenn-1 )? "X"：I陶皇后的位置用,沒有的用_coutvvendl;cout«"for(k=0;k<n-1;k)cout«"cout«" "«endl;cout«endl;int repair(int Queen,co

6、nst int n)啟發(fā)式修補int max=-1;/標志行行之間沖突數(shù)int minbug=n;int count=0;while(max!=0&&count<=100)-max=0;for(int i=0;i<n;i ).minbug=collision(Queen,i,Queeni,n);取得當前的沖突數(shù),不斷優(yōu)化int temp=Queeni;for(int j=0;j<n;j ).int bug=collision(Queen,i,j,n);if(bug<=minbug&&j!=temp). /保持皇后在等沖突的情況下不斷變更位

7、置,有利于后面行的優(yōu)化 minbug=bug;Queeni=j;if (minbug>max)max=minbug;show(Queen,n);count ;return count;void main().int n=-1;int step=0;cout<<"Input N (you would better input a interge minor to 15):"<<endl;cin>>n;if(n<=0).cout<<"Illegal Input!"<<endl;return;int* Queen=new intn;srand(time(NULL);取得隨機種子shuffle(Queen,n);cout<<"The oringinal state:"<<endl;show(Queen,n);step=repair(Queen,n);if(step>100).cout<<"Could find solution within 100 steps,Try again!"<<endl;return;cout<<"