A-A+

八皇后人工智能解决

2011年06月12日 编程开发 评论 270 条 阅读 3,989 views 次

人工智能策略应用,解决N皇后问题,皇后个数剧增的情况下,程序执行时间增加较少

import java.util.Random;
import java.util.Scanner;
/**
* 人工智能策略应用,解决N皇后问题,皇后个数剧增的情况下,程序执行时间增加较少
* 主要步骤:
* 1,随机存放皇后,并判断冲突个数**如何随机摆放N皇后?如何判断冲突个数,以什么为判定标准?
* 2,改变皇后位置,再次判断冲突个数,如果冲突个数减少,或相同则保留本次改变,否则还原至上一次
* 3,循环直至冲突个数为零,程序结束
* 细节:
* 1,用二维数组来表示皇后位置,0表示该位置为空,1表示该位置被皇后占据
* 2,假设棋盘上的两个皇后的坐标分别为(i1,j1)和(i2,j2),
*     不允许(i1-i2)=(j1-j2)或者(i1+j1)=(i2+j2)的情况出现
* 3,随机排列N皇后:如何使得初始冲突尽可能的少:
*     选择每行中插入一个皇后,在行插入的同时保证每列上只有一个皇后,从而保证行不冲突,列也不冲突
*     这样的随机插入应该是较优的插入策。
* 4, 是否需要创建类来进行皇后排列的存储,暂时未考虑,待定,如果需要,添加
*
* @author antter
*
*/
public class EightQueen {

public static void main(String[] args) {
System.out.println("输入皇后个数:");
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt();//获取皇后个数
int[][] queenArray = new int[num][num];
RandomSetQueen(queenArray,num);

System.out.println(checkConflict(queenArray,num));
while(checkConflict(queenArray,num) != 0 ){
RandomSetQueen(queenArray,num);
//            showArray(queenArray,num);
int count = checkConflict(queenArray, num);
//            System.out.println();
boolean success = false;
for(int i = 0; (!success)&&(i < num); i ++){
for(int j = 0;(!success)&&(j < num); j ++){
int[][] newArray = copyArray(queenArray,num);
conversion(newArray,num,i,j);//将第i行的元素转换为第j列位置
int newCount = checkConflict(newArray,num);
if(newCount < count){
//如果冲突个数减少,则保留变换
conversion(queenArray,num,i,j);
count = newCount;
if(newCount == 0)
success = true;
}
}
}
}
showArray(queenArray,num);

}
//随机排列皇后位置,并尽量减少冲突个数
public static void RandomSetQueen(int[][] array,int num){
for(int i = 0; i < num; i++ )
for(int j = 0;j < num; j++)
array[i][j] = 0;
Random random=new Random();
for(int i = 0;i < num;i++){
int r = random.nextInt(num);
array[i][r] = 1;
}
}
public static void showArray(int[][] array,int num){
for(int i = 0;i < num;i++){
for(int j = 0;j < num;j++)
System.out.print(array[i][j] + " " );
System.out.println();
}
}
//统计冲突个数,以每行、列、斜线上,冲突皇后个数的累加
public static int checkConflict(int[][] array,int num){

//由于初始化得特殊性,每行上不可能存在冲突皇后
//只需要统计列及斜线上的冲突个数
//列冲突的简单统计
int conflict = 0;//用于记录冲突个数
int biasNum = 2 * num - 1;//斜线个数
int[] col = new int[num];//用于存储每列上皇后个数
for(int i = 0;i < num;i++){
col[i] = 0;//对col进行初始化为0
}
int[] pos_bias = new int [biasNum];//用于统计正斜线方向的冲突皇后个数
int[] neg_bias = new int [biasNum];//用于统计负斜线方向的冲突皇后个数

for(int i = 0; i < biasNum; i ++){
pos_bias[i] = 0;//初始化
neg_bias[i] = 0;//初始化
}
//观察得:在正斜线方向的皇后位置在一维数组中可表示为 j - i + num - 1 ;负斜线方向上的皇后位置表示为 i + j;
//在检索每行中的皇后位置时,可同时对列冲突,正斜线,负斜线的冲突进行统计
for(int i = 0; i < num; i++)
for(int j = 0; j < num; j++)
if(array[i][j] == 1){
col[j]++;
pos_bias[j- i + num - 1]++;
neg_bias[i + j]++;
break;//每行中只会存在一个皇后,检测到之后,剩余位置无需再次检测,可有效减少循环次数
}
//在统计冲突个数时,考虑一维数组中元素值大于等于2的进行累加
for(int i = 0;i < biasNum; i ++){
if(pos_bias[i] >= 2){
conflict = conflict + pos_bias[i];
}
if(neg_bias[i] >= 2){
conflict = conflict + neg_bias[i];
}
if((i < num)&&(col[i] >= 2)){
conflict = conflict + col[i];
}
}
return conflict;
}
//对皇后位置进行变换??如何进行变换,同时能够记录已变换位置,不会出现重复变换,并能够判断何时
//不能够再次变换,只能再次考虑重新生成新的array。重新判断
//可以考虑,对每一行中的元素,依次遍历每行中的每一个位置,当冲突减少时,保留改变,
//当所有元素都遍历完成后,如果还不能完成位置安排,则重新生成新的Array
//将Array位置进行转换,将第i行的元素转换为第j列位置,再次进行冲突测试
public static void conversion(int[][] array,int num,int i,int j){
for(int s = 0; s <num; s ++){
if(array[i] == 1){
array[i] = 0;
array[i][j] = 1;
break;
}
}
}
//对数组进行拷贝,可能有更简单的办法,尚未想到
public static int[][]copyArray(int[][] array,int num){
int[][] newArray = new int[num][num];
for(int i = 0; i < num; i++ )
for(int j = 0;j < num; j++)
newArray[i][j] = array[i][j];
return newArray;
}

}

-----------------------------------------------------------------------------我是分割线-----------------------

供稿者:兄弟二金

标签:
Copyright © 风恋尘香 保留所有权利.   Theme  Ality

用户登录