1. IT分享知识网首页

人工智能之八数码问题

老牧童 • • 未分类 • 阅读 128

人工智能之八数码问题人工智能之八数码问题，主要是采用A*算法的思想，来搜索最优路径，解决问题。

大家好，欢迎来到IT知识分享网。人工智能之八数码问题"

八数码难题实验报告

问题描述

八数码难题  

  3×3九宫棋盘，放置数码为1 – 8的8个棋牌，剩下一个空格，只能通过棋牌向空格的移动来改变棋盘的布局。

  • 求解的问题——给定初始布局（即初始状态）和目标布局（即目标状态），如何移动棋牌才能从初始布局到达目标布局

·        解答路径——就是一个合法的走步序列

初始状态S0：  2     3   目标状态Sg：1  2  3 

                          1  8  4                            8 0  4                                       

                          7  6 5                             7 6  5

问题分析

采用启发式搜索的方式解决此问题，利用A*算法，通过估价函数来选择一条最佳路径。

•   估价函数的定义：
对节点n定义f*(n)=g*(n)+h*(n),表示从S开始约束通过节点n的一条最佳路径的代价。
希望估价函数f 定义为：f(n)=g(n)+h(n)
                            —— g是g*的估计 ，h是h*的估计

•   g*(n)：从s到n的最小路径代价值

•   h*(n)：从n到g的最小路径代价值

•   f*(n)=g*(n)+h*(n)：从s经过n到g的最小路径的总代价值

•   g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值

•   g(n)通常选择为当前所找到的从初始节点S到节点n的“最佳”路径的代价值，显然有g(n) ³g*(n)

具体解决思路是，通过给定的初始状态，推算该状态下能产生的所有可能的情况，加入到等待队列中，通过A*算法来计算这些状态接近结果的距离大概是多少，然后根据这个距离来选取最小的状态继续搜寻，如此循环，直到找到结果。

下面是具体实现代码，首先是主流程类：

import java.util.ArrayList;
import java.util.Scanner;

/**
 * 程序入口，这里主要是输入初始数据
 * @author 41571
 *2 8 3 1 6 4 7 0 5
 */
public class Project {
	private int total = 0;
	public static int[][] Goal = {
  
  {1,2,3},{8,0,4},{7,6,5}};
	private Node ini;
	private ArrayList<Node> nodeList = new ArrayList<Node>();//需要检测的情况
	private ArrayList<Node> result = new ArrayList<Node>();//检测过的情况
	private ArrayList<Node> end = new ArrayList<Node>();//结果
	
	public Project(){	//初始化最初状态
		System.out.println("输入初始状态，0表示空格");
		Scanner in = new Scanner(System.in);
		String numString = in.nextLine();
		ini = new Node(numString);
		nodeList.add(ini);
		Looking();
	}
	
	public static void main(String args[]){		//主函数
		new Project();
	}
	
	public void Looking(){	//遍历，根据权值遍历
		Node pro;boolean a = true;
		while(a){
			sort();		//冒泡排序，把权值最小的放在队列最后
			pro = nodeList.get(nodeList.size() - 1);	//获得栈顶元素
			if(isSame(pro)){	//当前要检测的节点是否已经遍历过了
				total++;
				result.add(pro);		//先加入检测过的队列
				int[][] data = pro.getNum().getData();	//获得当前检测的节点数据
				int deep = pro.getDepth();		//获得当前检测的节点的深度
				nodeList.remove(nodeList.size() - 1);	//把当前节点移出遍历队列
				if(pro.getNum().isSame(Goal)){		//当前节点是否是目标
					print();
					break;
				}else{		//不是目标，开始生成移动后的节点
					if(pro.getNum().isUp()){
						int[][] da = new int[3][3];
						for(int i = 0;i <3;i ++)for(int j = 0;j < 3;j ++){da[i][j] = data[i][j];}
						Num num = new Num(da);
						Node node = new Node(num.up(),deep+1,pro);
						if(isSame(node)){
							nodeList.add(node);	//生成移动后的节点并把当前节点作为父节点加入其中
							total++;
						}
					}
					if(pro.getNum().isDown()){
						int[][] da = new int[3][3];
						for(int i = 0;i <3;i ++)for(int j = 0;j < 3;j ++){da[i][j] = data[i][j];}
						Num num = new Num(da);
						Node node = new Node(num.down(),deep+1,pro);
						if(isSame(node)){
							nodeList.add(node);
							total++;
						}
					}
					if(pro.getNum().isLift()){
						int[][] da = new int[3][3];
						for(int i = 0;i <3;i ++)for(int j = 0;j < 3;j ++){da[i][j] = data[i][j];}
						Num num = new Num(da);
						Node node = new Node(num.lift(),deep+1,pro);
						if(isSame(node)){
							nodeList.add(node);
							total++;
						}
					}
					if(pro.getNum().isRight()){
						int[][] da = new int[3][3];
						for(int i = 0;i <3;i ++)for(int j = 0;j < 3;j ++){da[i][j] = data[i][j];}
						Num num = new Num(da);
						Node node = new Node(num.right(),deep+1,pro);
						if(isSame(node)){
							nodeList.add(node);
							total++;
						}
					}
				}
			}else	//已经遍历过这个节点，直接移除
				nodeList.remove(nodeList.size() - 1);
		}
	}
	private boolean isSame(Node pro) {	//判断pro是否遍历过，即是否出现在遍历过的队列中
		// TODO Auto-generated method stub
		for(int i = 0;i < result.size();i ++){
			if(result.get(i).getNum().isSame(pro.getNum().getData())){
				return false;
			}
		}
		return true;
	}
	private void print() {		//输出结果函数
		// TODO Auto-generated method stub
		delEnd(result.get(result.size()-1));
		for(int i = end.size()-1;i > 0 ;i --){
			System.out.println("第"+(end.size()-i)+"步--------------------");
			end.get(i).getNum().show();
		}
		/*for(int i = 0;i < result.size();i ++){
			System.out.println("第"+(i+1)+"步--------------------");
			result.get(i).getNum().show();
		}*/
		
		System.out.println("第"+(end.size())+"步--------------------");
		for(int i = 0;i < 3;i ++){
			for(int j = 0;j < 3;j ++){
				if(Goal[i][j] == 0){
					System.out.print("  ");
				}
				else
				System.out.print(Goal[i][j]+" ");
			}
			System.out.println("");
		}
		System.out.println("一共查找了"+result.size()+"个点.");
		System.out.println("一共产生了"+total+"个点.");
	}
	
	private void delEnd(Node node){		//除去多余的步骤，采用递归，从后向前根据父节点找出最短的路径
		end.add(node);
		if(node.getFather()!=null){
			delEnd(node.getFather());
		}
	}
	
	private void sort() {	//冒泡排序，由大到小
		// TODO Auto-generated method stub
		Node node;
		if(nodeList.size()>1)
			for(int i = 0;i < nodeList.size();i ++){
				for(int j = i+1;j < nodeList.size();j ++){
					if(nodeList.get(i).getValue()<nodeList.get(j).getValue()){
						node = nodeList.get(i);
						nodeList.set(i, nodeList.get(j));
						nodeList.set(j, node);
					}
				}
			}
	}
}

这里是节点类Node：

/**
 * 八数码的每个节点，节点内容包括
 * 数据num
 * 深度depth
 * 总权重value
 * 每个位置距离目标位置的和weight
 * 两个构造函数，参数是输入的字符串,因为只有初始状态会用到这个构造函数，所以深度会是0
 * 另一个构造函数，Num对象和深度depth
 * 具有的方法有
 * 从输入的信息提取数据num的getNum
 * 
 * @author 41571
 *
 */
public class Node {
	private Num num;
	private int depth = 0;
	private int weight = 0;
	private int value = 0;
	private Node father;
	
	public Node(Num num,int depth,Node father){		//中间遍历需要产生的节点，这里需要记录父节点
		this.num = num;
		this.weight = this.num.getWeight();
		this.depth = depth;
		this.value = this.depth + this.weight;
		this.father = father;
	}
	public Node(String numString){		//用来产生最初的根节点，这里不需要父节点
		this.num = getNum(numString);
		this.weight = this.num.getWeight();
		this.depth = 0;
		this.value = this.depth + this.weight;
	}
	
	public Num getNum(String numString){	//把一行String数据转化为int型数组
		int[][] num = new int[3][3];	//二维数组
		int[] nums = new int[9];	//一维数组
		char[] numChar;
		numChar = numString.toCharArray();
		int a = 0;
		for(int i = 0;i < numChar.length;i++){
			if(' ' != numChar[i]){
				nums[a++] = numChar[i];
			}
		}
		a = 0;
		for(int j = 0;j < nums.length;j++){
			num[a][j%3] = nums[j] - 48;
			if(j%3 == 2)
				a++;
		}
		return new Num(num);
	}
	public Num getNum(){
		return this.num;
	}
	public int getDepth(){
		return this.depth;
	}
	public int getWeight(){
		return this.weight;
	}
	public int getValue(){
		return this.value;
	}
	public Node getFather(){
		return this.father;
	}
}

为了方便对节点所存储的状态的操作，我添加了Num类，用来实现对具体八数码的数字的移动：

/**
 * 数据类，存放数据
 * 具有的功能，空格的上下左右的移动函数
 * up，down，lift，right
 * 以及移动是否安全，isUp，isDown，isLift，isRight
 * 以及显示函数show
 * 还有获得每个位置距离目标位置的和的函数getWeight
 * @author 41571
 *
 */

public class Num {
	private int [][] data;
	private int [] zero = new int[2];	//0点所在的位置
	public Num(int[][] data){
		this.data = new int[3][3];
		this.data = data;
		this.zero = this.getZero();
	}
	public void show(){		//打印
		for(int i = 0;i < this.data.length;i ++){
			for(int j = 0;j < this.data[i].length;j ++){
				if(data[i][j] == 0) System.out.print("  ");
				else System.out.print(data[i][j]+" ");
			}
			System.out.println("");
		}
	}
	public boolean isUp(){		//能上移吗
		if(zero[0] >= 1) return true;
		return false;
	}
	public Num up(){	//上移
		if(zero[0] >= 1){
			this.data[zero[0]][zero[1]] = this.data[zero[0]-1][zero[1]];
			this.data[zero[0]-1][zero[1]] = 0;
		}
		return this;
	}
	public boolean isDown(){	//能下移吗
		if(zero[0] <= 1) return true;
		else return false;
	}
	public Num down(){		//下移
		if(zero[0] <= 1){
			this.data[zero[0]][zero[1]] = this.data[zero[0]+1][zero[1]];
			this.data[zero[0]+1][zero[1]] = 0;
		}
		return this;
	}
	public boolean isLift(){		//能左移吗
		if(zero[1] >= 1) return true;
		else return false;
	}
	public Num lift(){		//左移
		if(zero[1] >= 1){
			this.data[zero[0]][zero[1]] = this.data[zero[0]][zero[1]-1];
			this.data[zero[0]][zero[1]-1] = 0;
		}
		return this;
	}
	public boolean isRight(){		//能右移吗
		if(zero[1] <= 1) return true;
		else return false;
	}
	public Num right(){		//右移
		if(zero[1] <= 1){
			this.data[zero[0]][zero[1]] = this.data[zero[0]][zero[1]+1];
			this.data[zero[0]][zero[1]+1] = 0;
		}
		return this;
	}
	public int[] getZero(){	//获得空格即是0所在位置
		int a = 0;
		for(int i = 0;i < this.data.length;i ++){
			for(int j = 0;j < this.data[i].length;j ++){
				if(this.data[i][j] == 0){
					zero[0] = i;
					zero[1] = j;
					a = 1;
					break;
				}
			}
			if(a == 1) break;
		}
		if(a == 0)	System.out.println("这个八数码中没有空格");
		return zero;
	}
	public int getWeight(){ 	//获得每个位置距目标位置的和
		int total = 0;
		for(int i = 0;i < this.data.length;i ++){
			for(int j = 0;j < this.data[i].length;j ++){
				//System.out.print("查找"+i+","+j+" 数据 "+data[i][j]);
				if(data[i][j]!=0)
					total+=getEveryoneWeight(i,j);
			}
		}
		return total;
	}
	private int getEveryoneWeight(int i, int j) {		//获得每个格子上的数距原位置的移动步数
		// TODO Auto-generated method stub
		int row = 0,col = 0,a = 0;
		for(int m = 0;m < Project.Goal.length;m ++){
			for(int n = 0;n < Project.Goal[m].length;n ++){
				if(this.data[i][j] == Project.Goal[m][n]){
					//System.out.println("  目标在"+m+","+n+" 数据"+Project.Goal[m][n]);
					row = i - m;
					col = j - n;
					a = 1;
					break;
				}
			}
			if(a == 1) break;
		}
		if(row < 0) row = 0 - row;
		if(col < 0) col = 0 - col;
		return (row + col);
	}
	public int[][] getData(){
		return this.data;
	}
	public boolean isSame(int[][] same){	//判断是否一样
		for(int i = 0;i <same.length;i ++){
			for(int j = 0;j < same.length;j ++){
				if(same[i][j]!=this.data[i][j])
					return false;
			}
		}
		return true;
	}
}

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/12606.html

赞 (0)
老牧童老牧童
0

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信