精华内容
下载资源
问答
  • C++课程设计---用A*算法求解八数码问题
  • A*算法求解八数码问题 java实现

    千次阅读 2020-01-27 20:08:00
    A*算法求解八数码问题1.估价函数2.搜索过程3.流程图4.八数码的估计函数设计5.编码实现6.结果 1.估价函数 首先定义估价函数。计算一个节点的估价函数,可以分成两个部分:g(n)已经付出的代价(起始节点到当前节点)...

    1.估价函数

    首先定义估价函数。计算一个节点的估价函数,可以分成两个部分:g(n)已经付出的代价(起始节点到当前节点)和h(n)将要付出的代价(当前节点到目标节点)。节点n的估价函数f(n)定义为f(n)=g(n)+h(n)。在A搜索算法中使用的就是估价函数f(n)=g(n)+h(n)。
    接下来定义最优估价函数f*(n)=g*(n)+h*(n),其中g*(n)为起点到n状态的最短路径代价值,h*(n)是n状态到目的状态的最短路径的代价值。这样f*(n)就是起点出发通过n状态而到达目的状态的最佳路径的总代价值。但在绝大部分实际问题中并不存在f*(n)这样的先验函数,但可以将f(n)作为f*(n)的一个近似估计函数。在A及A搜索算法中,g(n)作为g(n)的近似估价。g(n)与g*(n)可能并不相等,但在搜索过程中有g(n)>=g*(n),当搜索过程中已发现了到达n状态的最佳状态时,它们才相等。同样,可以用h(n)代替h*(n)作为n状态到目的状态的最小代价估计值。虽然在绝大数情况下无法计算h*(n),但是要判别某一h(n)是否大于h*(n)还是可能的。所以如果A搜索算法所使用的估价函数f(x)所能达到的f(n)中的h(n)<=h*(n)时它就为A*搜索算法

    2.搜索过程

    启发式图搜索算法使用两张表记录状态信息:在open表中保留所有已生产而未扩展的状态。在closed表中记录已扩展过的状态。算法中是根据某些启发信息来排列open表的。它既不同于宽度优先使用的队列,也不同于深度优先所使用的堆栈,而是按一个状态的启发估价函数值的大小排列的一个表。进入open表的状态不是简单地排在队尾或队首,而是根据其估值的大小插入到表中合适的位置,每次从表中优先取出启发估价函数最小的状态加以扩展。
    A*算法的搜索过程是基于估价函数的一种加权启发式图搜索算法,搜索过程如下:
    1.把初始结点放入到open表
    2.若open表为空,则搜索失败,退出
    3.移出open表中第一个结点N放入closed表中,也就是估价函数最小的节点,并顺序编号n
    4.若目标结点的状态等于结点N的状态,则搜索成功,结束
    5.若N不可扩展则转步骤2
    6.扩展节点N,生成一组节点N的子节点,对这组子节点做如下操作:
    (1)考察是否有已在open表或closed表中存在的结点。若有则再考察其中有无N的先辈结点,若有则删除之,对于其余节点也删除,但由于它们又被第二次生成,因此需要考虑是否修改已经存在于open表或closed表中的这些结点及其后裔的返回指针和f(x)的值。修改原则是:选f(x)值小的路径走。
    (2)为其余子节点配上指向N的返回指针后放入open表中,并对open表按f(x)值以升序排序,转向步骤2

    3.流程图

    在这里插入图片描述

    4.八数码的估计函数设计

    估计函数是由两部分构成的,节点深度d(n)其实就是当前已经走的步数,不用额外设计函数;启发函数h(n)是比较重要的一个部分,启发函数的设计直接影响了估计函数的效率,有几种定义方法:
    (1)当前节点与目标节点差异的度量 => 当前结点与目标节点相比,位置不符的数字个数
    (2)当前节点与目标节点距离的度量 => 当前结点与目标节点格局位置不符的数字移动到目标节点中对应位置的最短距离之和
    估计函数一:
    八数码的g(n)为已经搜索的步数,八数码的h(n)为当前结点与目标节点差异的数量
    估计函数二:
    当前结点与目标节点格局位置不符的数字移动到目标节点中对应位置的最短距离之和

    5.编码实现

    package Astatr;
    
    import java.util.*;
    
    
    public class Astar {
        private int N=3;
        Scanner input=new Scanner(System.in);
        int Map[][]=new int[N][N];
        int target[][]=new int[N][N];
        List<Node> openList=new ArrayList<>();    //A*算法open列表
        List<Node> closeList=new ArrayList<>();   //A*算法closed列表
    
        List<Node> queue=new ArrayList<>();   //bfs队列
    
        HashMap<Integer,int []> targetmap=new HashMap<>();  //估价函数二所用的映射功能
        List<Node>  nodeList=new ArrayList<>();  //节点列表用于存储所有扩展节点
    
        Node Start;
        Node Target;
        Comparator<Node> comparator=new Comparator<Node>() {    //比较函数,根据f(n)的值可以将openlist或closedlist从小到大排列
            @Override
            public int compare(Node o1, Node o2) {
                if(o1.getF()>o2.getF())
                    return 1;
                else if(o1.getF()==o2.getF())
                    return 0;
                else
                    return -1;
            }
        };
    
        public Astar(){
            if(init()) {
                A_algorithm();    //可以更改为bfs()测试bfs的性能
            }else{
                System.out.println("无解");
            }
        }
        boolean init(){         //初始化函数,用于输入初始八数码和目标八数码
            System.out.println("请输入八数码的初始状态:");
           for(int i=0;i<N;i++){
               for(int j=0;j<N;j++){
                   Map[i][j]=input.nextInt();
               }
           }
           Start=new Node();
           Start.setState(Map);
            System.out.println("请输入八数码的目标状态:");
            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++){
                    target[i][j]=input.nextInt();
                    int index[]={i,j};
                    targetmap.put(target[i][j],index);
                }
            }
           Target=new Node();
            Target.setState(target);
            if(isSolve(Start,Target)){
                return true;
            }else{
                return false;
            }
        }
        public boolean isSolve(Node start,Node target){     //判断是否有解
        		/*
        		对于八数码问题,首先要判断当前的状态能不能到达目的状态,这里需要用到奇排列和偶排列的概念。八数码虽然是个二维数组,但也可以展开看成是一个一维序列。奇排列只能转换成奇排列,偶排列只能转换成偶排列。判断奇偶排列的方法就是:对于每个数,求出排在它之前的比它大的数的个数,然后将这些个数加起来,得到的数是奇数就是奇排列,是偶数就是偶排列,若起始状态和目标状态一个是奇排列一个数偶排列,那么肯定到达不了目标状态。
        		*/
            int startNum[]=start.getSequence();
            int endNum[] =target.getSequence();
            int st = 0;
            int et = 0;
            for (int i = N * N - 2; i >= 0; i--) {
                for (int j = i - 1; j >= 0; j--) {
                    if (startNum[i] > startNum[j])
                        st++;
                    if (endNum[i] > endNum[j])
                        et++;
                }
            }
            if (st % 2 == et % 2)
                return true;
            return false;
        }
    
        int IndexInList(List<Node> list,Node node){    //判断某一状态是否在列表中 
            for (int index = 0; index < list.size(); index++) {
                int i = 0,j=0;
                for (i = 0; i <N; i++) {
                    for(j=0;j<N;j++) {
                        if ((list.get(index).getState()[i][j]) != node.getState()[i][j])
                            break;
                    }
                    if (j < N)
                        break;
                }
                if (i==N&&j==N) {
                    return index;
                }
            }
            return -1;
        }
    
        public boolean isCanMove(int x,int y){    //是否可以移动0
            if(x<0||x>=3||y<0||y>=3){
                return false;
            }
            return true;
        }
        Node getNext(Node now,int direction){   //移动函数,用于获得下一状态
            int dx[]=new int[]{0,0,-1,1};
            int dy[]=new int[]{-1,1,0,0};
            Node next=new Node();
            int temp[][]=new int[N][N];
            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++)
                    temp[i][j]=now.getState()[i][j];
            }
            int zeroIndex[]=now.getZeroIndex();
            int x0=zeroIndex[0];
            int y0=zeroIndex[1];
            int nextZeroIndex=0;
            int nextx,nexty;
            nextx=x0+dx[direction];
            nexty=y0+dy[direction];
            if(isCanMove(nextx,nexty)){
                temp[x0][y0]=now.getState()[nextx][nexty];
                temp[nextx][nexty]=0;        
               List<Node> path=new ArrayList<>();
                path.addAll(now.path);
                next.setState(temp);
                next.setPath(path);
                return next;
            }else{
                return null;
            }
        }
    
        void A_algorithm(){       //A*算法主体
        Start.setUp2();    //设置估价函数,可以更改为其他估价函数
        Start.path.add(Start);
        openList.add(Start);
        nodeList.add(Start);
        while(!openList.isEmpty()){
            openList.sort(comparator);
            Node best=openList.get(0);
            openList.remove(0);
            closeList.add(best);
            if(best.isTarget(Target)){        //判断是否为目标状态
                System.out.println("-------打印路径------");
                for(int i=0;i<best.path.size();i++){
                    System.out.println("第"+i+"次移动");
                    best.path.get(i).print();
                }
                System.out.println("共扩展了"+nodeList.size()+"个节点");
                return;
            }
            for(int i=0;i<4;i++){
                Node next=getNext(best,i);
                if(next!=null){       //是否可以移动到下一个状态
                    if(IndexInList(closeList,next)==-1){     //如果不在cloesd列表中
                        int index=IndexInList(openList,next);
                        if(index>=0){       //如果在open列表中
                            if(next.getG()<openList.get(index).getG()){    //比较和已在open列表中的深度比较
                                openList.remove(index);     //如果next更小,则将open中已存在的更换为next
                                next.setParent(best);
                                next.setUp2(Target,targetmap);   //设置估价函数,可以更改为其他估价函数
                                next.path.add(next);
                                openList.add(next);
                                nodeList.add(next);
                            }
                        }else{    //如果不在open列表中,则加入到open列表中
                            next.setParent(best);
                            next.setUp2(Target,targetmap);   //设置估价函数,可以更改为其他估价函数
                            next.path.add(next);
                            openList.add(next);
                            nodeList.add(next);
                        }
                    }
                }
            }
        }
     }
    
        void bfs(){    //bfs算法
            Start.setUp3();
            Start.path.add(Start);
            queue.add(Start);
            while(!queue.isEmpty()){
                Node best=queue.get(0);
                queue.remove(0);
                if(best.isTarget(Target)){        //判断是否为目标状态
                    System.out.println("-------打印路径------");
                    for(int i=0;i<best.path.size();i++){
                        System.out.println("第"+i+"次移动");
                        best.path.get(i).print();
                    }
                    System.out.println("共扩展了"+nodeList.size()+"个节点");
                    return;
                }
                for(int i=0;i<4;i++){
                    Node next=getNext(best,i);
                    if(next!=null){       //是否可以移动到下一个状态
                        next.setParent(best);
                        next.setUp3();
                        next.path.add(next);
                        queue.add(next);
                        queue.add(next);
                    }
                }
            }
        }
    
         void printPath(Node end){    //打印路径
              while(end!=null){
                  path.add(end);
                  end=end.getParent();
              }
              for(int i=0;i<path.size();i++){
                  System.out.println("---------第"+(i+1)+"次移动--------");
                   path.get(i).print();
                  System.out.println("-------------------------");
              }
             System.out.println("移动次数:"+path.size());
         }
        public static void main(String[] args) {
            Astar astar=new Astar();
        }
    }
    
    
    
    
    
    class Node {       //用于定义状态的类
        private int N=3;
        int state[][]=new int[3][3];
        private int f;    //估计函数
        private int g;    //当前深度
        private int h;     //目标的估计
        private Node parent;  //存储当前结点的上一个状态
        List<Node> path=new ArrayList<>();   //存储路径
        public Node(){
    
        }
    
        public void setUp(Node target) {   //估价函数一
            int num=0;
            for(int i=0;i<3;i++){
                for(int j=0;j<3;j++)
                if(state[i][j]!=target.getState()[i][j]){
                    num++;
                }
            }
            this.h = num;
            if(this.parent==null){
                this.g=0;
            }else{
                this.g=this.parent.getG()+1;
            }
            this.f=this.g+this.h;
        }
        public void setUp2(Node target,Map<Integer,int[]> map){   //估价函数二
            int num = 0;
            for (int row = 0; row < N; row++) {
                for (int cow = 0; cow < N; cow++) {
                    if (cow != 0 && state[row][cow] != target.getState()[row][cow]){
                        num += Math.abs(row - map.get(state[row][cow])[0]) + Math.abs(cow - map.get(state[row][cow])[1]);
                    }
                }
            }
            this.h = num;
            if(this.parent==null){
                this.g=0;
            }else{
                this.g=this.parent.getG()+1;
            }
            this.f=this.g+this.h;
        }
        public void setUp3(){            //bfs的估价函数
            this.h = 0;
            if(this.parent==null){
                this.g=0;
            }else{
                this.g=this.parent.getG()+1;
            }
            this.f=this.g+this.h;
        }
    
        public int[][] getState() {
            return state;
        }
    
        public void setState(int[][] state) {
            this.state = state;
        }
    
        public int getF() {
            return f;
        }
    
        public void setF(int f) {
            this.f = f;
        }
    
        public int getG() {
            return g;
        }
    
        public void setG(int g) {
            this.g = g;
        }
    
        public Node getParent() {
            return parent;
        }
    
        public void setParent(Node parent) {
            this.parent = parent;
        }
    
        public List<Node> getPath() {
            return path;
        }
    
        public void setPath(List<Node> path) {
            this.path = path;
        }
    
        public boolean isTarget(Node target){
            int i = 0,j=0;
            for (i = 0; i <N; i++) {
                for(j=0;j<N;j++) {
                    if (state[i][j]!= target.getState()[i][j])
                        return false;
                }
            }
            return true;
        }
    
        public int[] getZeroIndex(){     //获得0的位置
            int x0 = 0, y0 = 0;
            for (x0 = 0; x0 < N; x0++) {
                boolean flag = false;
                for (y0 = 0; y0 < N; y0++) {
                    if (state[x0][y0] == 0) {
                        flag = true;
                        break;
                    }
                }
                if (flag)
                    break;
            }
            return new int[]{x0, y0};
        }
    
    
       public void print(){    //打印函数
            for(int i=0;i<3;i++){
               for(int j=0;j<3;j++){
                   System.out.print(state[i][j]+" ");
               }
                System.out.println();
            }
       }
    	
    	public int[] getSequence(){     //获取一维序列
        	int num[]=new int[N*N];
        	int count=0;
        	for(int i=0;i<N;i++)
        		for(int j=0;j<N;j++){
        			if(state[i][j]!=0){
    					num[count++]=state[i][j];
    				}
        		}
        	return num;
        }
    }
    
    
    
    
    public class Test(){
    	 public static void main(String[] args) {
            Astar astar=new Astar();
        }
    }
    

    6.结果

    使用0代替空格的位置,并输出打印路径和移动次数
    比较两种不同的估计函数的结果值
    设定初始状态为
    2 8 3
    1 6 4
    7 0 5
    目标状态为
    1 2 3
    8 0 4
    7 6 5

    不同估价函数的比较

    搜索方法 扩展节点数
    A*算法的估价函数一 14
    A*算法的估价函数二 12
    广度优先搜索(BFS) 684

    对比来看不同的估价函数是能够影响搜索效率的,bfs的效率相比于A*算法是低了很多的。

    展开全文
  • A*算法求解八数码问题 1、A*算法基本思想: 1)建立一个队列,计算初始结点的估价函数f,并将初始结点入队,设置队列头和尾指针。 2)取出队列头(队列头指针所指)的结点,如果该结点是目标结点,则输出路径,程序...
  • 人工智能-A*算法求解八数码问题

    千次阅读 2020-05-07 21:17:34
    试编程实现这一问题求解。 ➢备注:为了程序中表示方便,用0代替空格。 ➢初始状态和目标状态:均由用户通过键盘手工输入或者从文件读入(不可以写死在程序里面)。 ➢实验结果需要包含以下初始状态和目标状态的...

    ➢在一个3×3的九宫中有1-8这8个数字以及一个空格随机摆放在其中的格子里。将该九宫格调整到目标状态。
    ➢规则:每次只能将与空格(上、下、左、右)相邻的一个数字移动到空格中。试编程实现这一问题的求解。
    ➢备注:为了程序中表示方便,用0代替空格。
    ➢初始状态和目标状态:均由用户通过键盘手工输入或者从文件读入(不可以写死在程序里面)。
    ➢实验结果需要包含以下初始状态和目标状态的结果(checkyouranswer:至少需要移动15步)。
    其中代价函数选的是错位的数字,估价函数是步数加错位的数字,输出放在文件中,文件名请自行更改。

    def solution(str1,strend,h1):
        list1=[str1]#存放所有的节点
        routelist=[('',0,h1,h1)]#存放操作步骤,元组表示(父节点,深度(n),错位数字(h),深度加错位总和)
        #closelist=[]#存放已经选过的节点
        openlist=[]#存放有可能被选中的节点
        str2=str1
        str4=""
        list2=[]
        #j=0#列表位置
        while(True):
            p=list1.index(str2)
            n=routelist[p][1]+1
            m=str2.index("0")#0所在位置
            if m//3!=0:#上移条件是否成立
                #上移
                str3=list(str2)
                str3[m],str3[m-3]=str3[m-3],str3[m]
                str3=''.join(str3)
                #
                if str3 not in list1:
                    h = 0
                    if int(str3[8]) != 0:
                        h += 1
                    for i in range(0, 8):#判断错位的数字个数
                        if int(str3[i]) != i+1:
                            h += 1
                        else:
                            continue
                    list1.append(str3)#加入到已出现的状态中
                    routelist.append((p,n,h,n+h))
                    openlist.append((str3,n+h))#加入到有可能被选中的状态中
                else:
                    break
            if m//3!=2:#下移条件是否成立
                #下移
                str3 = list(str2)
                str3[m], str3[m +3] = str3[m + 3], str3[m]
                str3 = ''.join(str3)
                #
                if str3 not in list1:
                    h = 0
                    if int(str3[8]) != 0:
                        h += 1
                    for i in range(0, 8):
                        if int(str3[i]) != i+1:
                            h += 1
                        else:
                            continue
                    list1.append(str3)
                    routelist.append((p,n, h, n + h))
                    openlist.append((str3, n + h))
                else:
                    break
            if m%3!=0:#左移条件是否成立
                #左移
                str3 = list(str2)
                str3[m], str3[m - 1] = str3[m - 1], str3[m]
                str3 = ''.join(str3)
                #
                if str3 not in list1:
                    h = 0
                    if int(str3[8]) != 0:
                        h += 1
                    for i in range(0, 8):
                        if int(str3[i]) != i+1:
                            h += 1
                        else:
                            continue
                    list1.append(str3)
                    routelist.append((p, n, h, n + h))
                    openlist.append((str3, n + h))
                else:
                    break
            if m%3!=2:#右移条件是否成立
                #右移
                str3 = list(str2)
                str3[m], str3[m +1] = str3[m +1], str3[m]
                str3 = ''.join(str3)
                #
                if str3 not in list1:
                    h = 0
                    if int(str3[8]) != 0:
                        h += 1
                    for i in range(0, 8):
                        if int(str3[i]) != i+1:
                            h += 1
                        else:
                            continue
                    list1.append(str3)
                    routelist.append((p,n, h, n + h))
                    openlist.append((str3, n + h))
                else:
                    break
            if len(list1)>10000:
                list1=[]
                break
            #选出最小的n+h一项
            min = 100000
            #八数码比较特殊当出现第一位目标状态时肯定是最优的路径
            if strend not in list1:
                for i in range(0,len(openlist)):
                    if openlist[i][1]<min:
                        str4=openlist[i][0]
                        min=openlist[i][1]
                    else:
                        continue
            else:
                for i in range(0, len(openlist)):
                    if openlist[i][0] == strend:
                        c = openlist[i][1]
                    if openlist[i][1] < min:
                        str4 = openlist[i][0]
                        min = openlist[i][1]
                if c == min:
                    break
                else:
                    continue
            str2 = str4
            openlist.remove((str4, min))
        if len(list1)!=0:
            a=routelist[list1.index(strend)][0]
            list2.append(strend)
            while(True):
                str0 = list1[a]
                a = routelist[a][0]
                list2.append(str0)
                if a==0:
                    break
            list2.append(str1)
            list2=list2[::-1]
            with open('solution.txt','w') as f:
                for i in range(0,len(list2)):
                    st1="第"+str(i)+"步:"
                    f.write(st1)
                    f.write('\n')
                    f.write(list2[i][0:3])
                    f.write('\n')
                    f.write(list2[i][3:6])
                    f.write('\n')
                    f.write(list2[i][6:9])
                    f.write('\n')
                    f.write('\n')
        else:
            print('无解决路径')
    def main():
        str1=input('请输入初始状态,例如(1234567890):')
        strend=input('请输入目标状态,例如(1234567890):')
        h1=0
        if int(str1[8]) != 0:
            h1 += 1#0无法参与循环判断所以单独判断
        for i in range(0, 8):
            if int(str1[i]) != i+1:
                h1 += 1
            else:
                continue
        solution(str1,strend,h1)
    if __name__=="__main__":
        main()
    

    结果
    *第0步:
    153
    246
    708

    第1步:
    153
    246
    078

    第2步:
    153
    046
    278

    第3步:
    153
    406
    278

    第4步:
    103
    456
    278

    第5步:
    013
    456
    278

    第6步:
    413
    056
    278

    第7步:
    413
    256
    078

    第8步:
    413
    256
    708

    第9步:
    413
    206
    758

    第10步:
    413
    026
    758

    第11步:
    013
    426
    758

    第12步:
    103
    426
    758

    第13步:
    123
    406
    758

    第14步:
    123
    456
    708

    第15步:
    123
    456
    780*

    展开全文
  • A*算法求解8数码问题

    2012-04-18 14:19:38
    A*算法八数码问题求解实验报告,问题求解包含在内
  • 实验一 A*算法求解8数码问题 一、实验目的 熟悉和掌握启发式搜索的定义、估价函数和算法过程,并利用A*算法求解N数码难题,理解求解流程和搜索顺序。 二、实验原理 A*算法是一种启发式图搜索算法,其特点在于对...

    目录

    实验一 A*算法求解8数码问题

    一、实验目的

    二、实验原理

    三、实验结果

    四、实验总结

    附录代码

    推荐文章


    实验一 A*算法求解8数码问题

    一、实验目的

    熟悉和掌握启发式搜索的定义、估价函数和算法过程,并利用A*算法求解N数码难题,理解求解流程和搜索顺序。

    二、实验原理

    A*算法是一种启发式图搜索算法,其特点在于对估价函数的定义上。对于一般的启发式图搜索,总是选择估价函数f值最小的节点作为扩展节点。因此,f是根据需要找到一条最小代价路径的观点来估算节点的,所以,可考虑每个节点n的估价函数值为两个分量:从起始节点到节点n的实际代价g(n)以及从节点n到达目标节点的估价代价h(n),且hn≤h*n , h*n 为n节点到目的结点的最优路径的代价。

    图2.1  八数码问题的求解
    八数码问题是在3×3的九宫格棋盘上,摆有8个刻有1~8数码的将牌。棋盘中有一个空格,允许紧邻空格的某一将牌可以移到空格中,这样通过平移将牌可以将某一将牌布局变换为另一布局。针对给定的一种初始布局或结构(目标状态),问如何移动将牌,实现从初始状态到目标状态的转变。如下图2.1表示了一个具体的八数码问题求解。

    三、实验结果

    表3.1 不同启发函数h(n)求解8数码问题的结果比较

     

    启发函数h(n)

    不在位数

    将牌“不在位”的距离和

    0

    初始状态

    283604175

    283604175

    283604175

    目标状态

    123804765

    123804765

    123804765

    最优解

    最佳路径长度

    为:8

    最佳路径为:

    第1层的状态:

    2 8 3

    0 6 4

    1 7 5

    第2层的状态:

    2 8 3

    1 6 4

    0 7 5

    第3层的状态:

    2 8 3

    1 6 4

    7 0 5

    第4层的状态:

    2 8 3

    1 0 4

    7 6 5

    第5层的状态:

    2 0 3

    1 8 4

    7 6 5

    第6层的状态:

    0 2 3

    1 8 4

    7 6 5

    第7层的状态:

    1 2 3

    0 8 4

    7 6 5

    第8层的状态:

    1 2 3

    8 0 4

    7 6 5

    最佳路径长度

    为:8

    最佳路径为:

    第1层的状态:

    2 8 3

    0 6 4

    1 7 5

    第2层的状态:

    2 8 3

    1 6 4

    0 7 5

    第3层的状态:

    2 8 3

    1 6 4

    7 0 5

    第4层的状态:

    2 8 3

    1 0 4

    7 6 5

    第5层的状态:

    2 0 3

    1 8 4

    7 6 5

    第6层的状态:

    0 2 3

    1 8 4

    7 6 5

    第7层的状态:

    1 2 3

    0 8 4

    7 6 5

    第8层的状态:

    1 2 3

    8 0 4

    7 6 5

    最佳路径长度为:8

    最佳路径为:

    第1层的状态:

    2 8 3

    0 6 4

    1 7 5

    第2层的状态:

    2 8 3

    1 6 4

    0 7 5

    第3层的状态:

    2 8 3

    1 6 4

    7 0 5

    第4层的状态:

    2 8 3

    1 0 4

    7 6 5

    第5层的状态:

    2 0 3

    1 8 4

    7 6 5

    第6层的状态:

    0 2 3

    1 8 4

    7 6 5

    第7层的状态:

    1 2 3

    0 8 4

    7 6 5

    第8层的状态:

    1 2 3

    8 0 4

    7 6 5

    扩展节点数

    (不包括叶子节点)

    17

    8

    294

    生成节点数

    (包含叶子节点)

    33

    17

    470

    运行时间

    (迭代次数)

    220.00ms

    120.00ms

    1469.00ms

    四、实验总结

    1、画出A*算法求解N数码问题的流程图。

    根据A*算法的实验原理,f=g(n) +h(n) ;这样估价函数f(n)在g(n)一定的情况下,会或多或少的受距离估计值h(n)的制约,节点距目标点近,h值小,f值相对就小,能保证最短路的搜索向终点的方向进行, 因此f是根据需要找到一条最小代价路径的观点来估算节点的。设计A*算法的流程图如图4.1.1所示,按照流程图编写伪代码,进而编写完整的程序。其中OPEN表保存所有已生成而未考察的节点,CLOSED表中记录已访问过的节点。在扩展结点时,还需要考虑两个表即OPEN表和CLOSED表中是否存在了该节点的后继节点。具体编程思路参照算法4.1

    图4.1.1 A*算法求解八数码问题的流程图

     

    算法4.1

    将起始点加入open表

         当open表不为空时:

           寻找open表中f值最小的点current

           它是终止点,则找到结果,程序结束。

           否则,Open表移出current,对current表中的每一个临近点

               若它不可走或在close表中,略过

               若它不在open表中,加入。

               若它在open表中,计算g值,若g值更小,替换其父节点为current,更新

    它的g值。

         若open表为空,则路径不存在。

     

    2、分析不同的估价函数对A*算法性能的影响。

    对于同一问题启发函数h(n)可以有多种设计方法。在本次时实验中,通过选用“将牌不在位数”和“将牌‘不在位’的距离和”两种不同的启发函数,同时还编写了不考虑h值进行搜索,即不采用启发性搜索的算法(按照广度优先搜索的策略)。正如表3.1所示,我们通过将第一种和第二种启发函数对比,发现第二种启发函数优于第一种启发函数,将采用启发函数与不采用启发性函数对比发现,采用启发性函数远远优于不采用启发性函数。

    下面,以图4.2.2为例,分析第二种启发函数求解的过程。第二种启发函数为h(n)=将牌‘不在位’的距离和,初始时的值为6,将牌1:2,将牌2:1,将牌6:2,将牌7:1,将牌8:2。在实验结果演示(表3.1)时,并没有选取图4.3初始状态来比较不同启发函数以及不采用启发函数对求解效率的影响,而是选取了图4.2.1初始状态进行演示,因为图4.2.2的步骤较为复杂,对于不同启发函数对于实验结果和实验效率的影响较为明显。第三种启发函数是按照广度优先搜索的策略。

        

    图4.2.1 初始状态                 图4.2.2 A*算法求解八数码示意图

    3根据宽度优先搜索算法和A*算法求解八数码问题的结果,分析启发式搜索的特点。

    根据表3-1的结果,我们可以发现采用A*算法求解八数码问题时间以及搜索的节点数目远远小于采用宽度优先搜索算法,这说明对于八数码问题,选用的启发性信息有利于搜索效率的提高。但是理论上来讲,如果选用的启发性信息过强,则可能找不到最优解。

    4实验心得体会

    当时面对300行的代码时,不知从何处下手,通过查阅资料和请教老师,以及与同学深入探讨,仔细研究A*算法之后,才明白程序如何编写,各部分的函数如何构成。同时,通过本次实验,发现选用不同的启发函数,对于实验的结果有较大的影响。正如表3-1所示,选用第一或第二种(也就是采用A*算法)远远优于普通的广度优先搜索,同时,明显的感觉到第二种启发函数效率更高,更快的找到最优解。但是,在实验过程中,也遇到了一些问题,比如初始值的八数码初始值的选择对于实验结果的影响很大,在选取一些样例时,比如1,3,0,2,8,4,7,6,5,实验结果达到20000次依然没有停止,无法比较两种启发函数的优越性,鉴于时间原因,选取一些迭代次数较小就可以达到目标状态的样例进行验证,发现第二种结果优于第一种启发函数的结果。总的来说,实践出真知,只有把书上的理论知识运用到实践,才是真正地掌握。本次实验顺利完成,还是挺开心的。

    附录代码

    #include "iostream"  
    #include "stdlib.h"  
    #include "conio.h"  
    #include <math.h>
    #include <windows.h>
    #define size 3  
    using namespace std;  
    //定义二维数组来存储数据表示某一个特定状态  
    typedef int status[size][size];  
    struct SpringLink;  
      
    //定义状态图中的结点数据结构  
    typedef struct Node  
    {  
        status data;//结点所存储的状态 ,一个3*3矩阵 
        struct Node *parent;//指向结点的父亲结点  
        struct SpringLink *child;//指向结点的后继结点  
        struct Node *next;//指向open或者closed表中的后一个结点  
        int fvalue;//结点的总的路径  
        int gvalue;//结点的实际路径  
        int hvalue;//结点的到达目标的困难程度  
    }NNode , *PNode;  
      
      
    //定义存储指向结点后继结点的指针的地址  
    typedef struct SpringLink  
    {  
        struct Node *pointData;//指向结点的指针  
        struct SpringLink *next;//指向兄第结点  
    }SPLink , *PSPLink;  
      
      
    PNode open;  
    PNode closed;  
    //OPEN表保存所有已生成而未考察的节点,CLOSED表中记录已访问过的节点
      
    //开始状态与目标状态  
    /*
    status startt = {1,3,0,8,2,4,7,6,5};最佳路径为2   
    status startt = {1,3,0,2,8,4,7,6,5};迭代超过20000次,手动停止 
    status startt = {2,8,3,1,6,4,7,0,5}; 
    status startt = {2,8,3,6,0,4,1,7,5}; //实验报告
    */ 
    int t=0; //迭代次数,相当于运行时间 
    int count_extendnode=0;//扩展结点 
    int count_sumnode=0; //生成节点 
    status startt = {2,8,3,6,0,4,1,7,5}; //实验报告
    status target = {1,2,3,8,0,4,7,6,5};  
    //初始化一个空链表  
    void initLink(PNode &Head)  
    {  
        Head = (PNode)malloc(sizeof(NNode));  
        Head->next = NULL;  
    }  
      
      
    //判断链表是否为空  
    bool isEmpty(PNode Head)  
    {  
        if(Head->next == NULL)  
            return true;  
        else  
            return false;  
    }  
      
      
    //从链表中拿出一个数据  
    void popNode(PNode &Head , PNode &FNode)  
    {  
        if(isEmpty(Head))  
        {  
            FNode = NULL;  
            return;  
        }  
        FNode = Head->next;  
        Head->next = Head->next->next;  
        FNode->next = NULL;  
    }  
      
      
      
    //向结点的最终后继结点链表中添加新的子结点  
    void addSpringNode(PNode &Head , PNode newData)  
    {  
        PSPLink newNode = (PSPLink)malloc(sizeof(SPLink));  
        newNode->pointData = newData;  
      
        newNode->next = Head->child;  
        Head->child = newNode;  
    }  
      
      
    //释放状态图中存放结点后继结点地址的空间  
    void freeSpringLink(PSPLink &Head)  
    {  
        PSPLink tmm;  
      
        while(Head != NULL)  
        {  
            tmm = Head;  
            Head = Head->next;  
            free(tmm);  
        }  
    }  
      
      
    //释放open表与closed表中的资源  
    void freeLink(PNode &Head)  
    {  
        PNode tmn;  
      
        tmn = Head;  
        Head = Head->next;  
        free(tmn);  
      
        while(Head != NULL)  
        {  
            //首先释放存放结点后继结点地址的空间  
            freeSpringLink(Head->child);  
            tmn = Head;  
            Head = Head->next;  
            free(tmn);  
        }  
    }  
      
      
    //向普通链表中添加一个结点  
    void addNode(PNode &Head , PNode &newNode)  
    {  
        newNode->next = Head->next;  
        Head->next = newNode;  
    }  
      
      
    //向非递减排列的链表中添加一个结点(已经按照权值进行排序)  
    void addAscNode(PNode &Head , PNode &newNode)  
    {  
        
        PNode P;  
        PNode Q;  
      
        P = Head->next;  
        Q = Head;  
        while(P != NULL && P->fvalue < newNode->fvalue)  
        {  
            Q = P;  
            P = P->next;  
        }  
        //上面判断好位置之后,下面就是简单的插入了  
        newNode->next = Q->next;  
        Q->next = newNode;  
    }  
      
    /*
    //计算结点的 h 值  f=g+h. 按照不在位的个数进行计算 
    int computeHValue(PNode theNode)  
    {  
        int num = 0;  
      
        for(int i = 0 ; i < 3 ; i++)  
        {  
            for(int j = 0 ; j < 3 ; j++)  
            {  
                if(theNode->data[i][j] != target[i][j])  
                    num++;  
            }  
        }  
        return num;  
    }   
    
    //计算结点的 h 值  f=g+h. 按照将牌不在位的距离和进行计算 
    int computeHValue(PNode theNode)  
    {  
        int num = 0;  
      
        for(int i = 0 ; i < 3 ; i++)  
        {  
            for(int j = 0 ; j < 3 ; j++)  
            {  
                if(theNode->data[i][j] != target[i][j]&&theNode->data[i][j] !=0){
                	for(int ii=0;ii<3;ii++){
                		for(int jj=0;jj<3;jj++){
                			if(theNode->data[i][j] == target[ii][jj]){
                				num+=abs(ii-i)+abs(jj-j);
    							break; 
    						}
    					}
    				}
    			}
    			
            }  
        }  
        return num;  
    }  */ 
      
    //计算结点的f,g,h值  
    void computeAllValue(PNode &theNode , PNode parentNode)  
    {  
        if(parentNode == NULL)  
            theNode->gvalue = 0;  
        else  
            theNode->gvalue = parentNode->gvalue + 1;  
      
    //    theNode->hvalue = computeHValue(theNode);  
        theNode->hvalue = 0;  
        theNode->fvalue = theNode->gvalue + theNode->hvalue;  
    }  
      
      
      
    //初始化函数,进行算法初始条件的设置  
    void initial()  
    {  
        //初始化open以及closed表  
        initLink(open);  
        initLink(closed);  
      
        //初始化起始结点,令初始结点的父节点为空结点  
        PNode NULLNode = NULL;  
        PNode Start = (PNode)malloc(sizeof(NNode));  
        for(int i = 0 ; i < 3 ; i++)  
        {  
            for(int j = 0 ; j < 3 ; j++)  
            {  
                Start->data[i][j] = startt[i][j];  
            }  
        }  
        Start->parent = NULL;  
        Start->child = NULL;  
        Start->next = NULL;  
        computeAllValue(Start , NULLNode);  
      
        //起始结点进入open表	  
        addAscNode(open , Start);  
        
    }  
      
      
    //将B节点的状态赋值给A结点  
    void statusAEB(PNode &ANode , PNode BNode)  
    {  
        for(int i = 0 ; i < 3 ; i++)  
        {  
            for(int j = 0 ; j < 3 ; j++)  
            {  
                ANode->data[i][j] = BNode->data[i][j];  
            }  
        }  
    }  
      
      
    //两个结点是否有相同的状态  
    bool hasSameStatus(PNode ANode , PNode BNode)  
    {  
        for(int i = 0 ; i < 3 ; i++)  
        {  
            for(int j = 0 ; j < 3 ; j++)  
            {  
                if(ANode->data[i][j] != BNode->data[i][j])  
                    return false;  
            }  
        }  
        return true;  
    }  
      
      
      
    //结点与其祖先结点是否有相同的状态  
    bool hasAnceSameStatus(PNode OrigiNode , PNode AnceNode)  
    {  
        while(AnceNode != NULL)  
        {  
            if(hasSameStatus(OrigiNode , AnceNode))  
                return true;  
            AnceNode = AnceNode->parent;  
        }  
        return false;  
    }  
      
      
    //取得方格中空的格子的位置  
    void getPosition(PNode theNode , int &row , int &col)  
    {  
        for(int i = 0 ; i < 3 ; i++)  
        {  
            for(int j = 0 ; j < 3 ; j++)  
            {  
                if(theNode->data[i][j] == 0)  
                {  
                    row = i;  
                    col = j;  
                    return;  
                }  
            }  
        }  
    }  
      
      
    //交换两个数字的值  
    void changeAB(int &A , int &B)  
    {  
        int C;  
        C = B;  
        B = A;  
        A = C;  
    }  
      
      
    //检查相应的状态是否在某一个链表中  
    bool inLink(PNode spciNode , PNode theLink , PNode &theNodeLink , PNode &preNode)  
    {  
        preNode = theLink;  
        theLink = theLink->next;  
      
        while(theLink != NULL)  
        {  
            if(hasSameStatus(spciNode , theLink))  
            {  
                theNodeLink = theLink;  
                return true;  
            }  
            preNode = theLink;  
            theLink = theLink->next;  
        }  
        return false;  
    }  
      
      
      
    //产生结点的后继结点(与祖先状态不同)链表  
    void SpringLink(PNode theNode , PNode &spring)  
    {  
        int row;  
        int col;  
      
        getPosition(theNode , row , col);  
      
        //空的格子右边的格子向左移动  
        if(col != 2)  
        {  
            PNode rlNewNode = (PNode)malloc(sizeof(NNode));  
            statusAEB(rlNewNode , theNode);  
            changeAB(rlNewNode->data[row][col] , rlNewNode->data[row][col + 1]);  
            if(hasAnceSameStatus(rlNewNode , theNode->parent))  
            {  
                free(rlNewNode);//与父辈相同,丢弃本结点  
            }  
            else  
            {  
                rlNewNode->parent = theNode;  
                rlNewNode->child = NULL;  
                rlNewNode->next = NULL;  
                computeAllValue(rlNewNode , theNode);  
                //将本结点加入后继结点链表  
                addNode(spring , rlNewNode);  
            }  
        }  
        //空的格子左边的格子向右移动  
        if(col != 0)  
        {  
            PNode lrNewNode = (PNode)malloc(sizeof(NNode));  
            statusAEB(lrNewNode , theNode);  
            changeAB(lrNewNode->data[row][col] , lrNewNode->data[row][col - 1]);  
            if(hasAnceSameStatus(lrNewNode , theNode->parent))  
            {  
                free(lrNewNode);//与父辈相同,丢弃本结点  
            }  
            else  
            {  
                lrNewNode->parent = theNode;  
                lrNewNode->child = NULL;  
                lrNewNode->next = NULL;  
                computeAllValue(lrNewNode , theNode);  
                //将本结点加入后继结点链表  
                addNode(spring , lrNewNode);  
            }  
        }  
        //空的格子上边的格子向下移动  
        if(row != 0)  
        {  
            PNode udNewNode = (PNode)malloc(sizeof(NNode));  
            statusAEB(udNewNode , theNode);  
            changeAB(udNewNode->data[row][col] , udNewNode->data[row - 1][col]);  
            if(hasAnceSameStatus(udNewNode , theNode->parent))  
            {  
                free(udNewNode);//与父辈相同,丢弃本结点  
            }  
            else  
            {  
                udNewNode->parent = theNode;  
                udNewNode->child = NULL;  
                udNewNode->next = NULL;  
                computeAllValue(udNewNode , theNode);  
                //将本结点加入后继结点链表  
                addNode(spring , udNewNode);  
            }  
        }  
        //空的格子下边的格子向上移动  
        if(row != 2)  
        {  
            PNode duNewNode = (PNode)malloc(sizeof(NNode));  
            statusAEB(duNewNode , theNode);  
            changeAB(duNewNode->data[row][col] , duNewNode->data[row + 1][col]);  
            if(hasAnceSameStatus(duNewNode , theNode->parent))  
            {  
                free(duNewNode);//与父辈相同,丢弃本结点  
            }  
            else  
            {  
                duNewNode->parent = theNode;  
                duNewNode->child = NULL;  
                duNewNode->next = NULL;  
                computeAllValue(duNewNode , theNode);  
                //将本结点加入后继结点链表  
                addNode(spring , duNewNode);  
            }  
        }  
    }  
      
      
    //输出给定结点的状态  
    void outputStatus(PNode stat)  
    {  
        for(int i = 0 ; i < 3 ; i++)  
        {  
            for(int j = 0 ; j < 3 ; j++)  
            {  
                cout << stat->data[i][j] << " ";  
            }  
            cout << endl;  
        }  
    }  
      
      
      
    //输出最佳的路径  
    void outputBestRoad(PNode goal)  
    {  
        int deepnum = goal->gvalue;  
      
        if(goal->parent != NULL)  
        {  
            outputBestRoad(goal->parent);  
        }  
        cout << "第" << deepnum-- << "层的状态:" << endl;  
        outputStatus(goal);  
    }  
      
      
    void AStar()  
    {  
    
        PNode tmpNode;//指向从open表中拿出并放到closed表中的结点的指针  
        PNode spring;//tmpNode的后继结点链  
        PNode tmpLNode;//tmpNode的某一个后继结点  
        PNode tmpChartNode; 
    	 
        PNode thePreNode;//指向将要从closed表中移到open表中的结点的前一个结点的指针  
        bool getGoal = false;//标识是否达到目标状态  
        long numcount = 1;//记录从open表中拿出结点的序号  
      	
        initial();//对函数进行初始化  
        initLink(spring);//对后继链表的初始化  
        tmpChartNode = NULL;  
        //Target.data=target;
        	cout<<"1"<<endl;
        PNode Target = (PNode)malloc(sizeof(NNode)); 
        for(int i = 0 ; i < 3 ; i++)  
        {  
            for(int j = 0 ; j < 3 ; j++)  
            {  
                Target->data[i][j] =target[i][j];  
            }  
        }
      	cout<<"1"<<endl;
        cout << "从open表中拿出的结点的状态及相应的值" << endl;
     
        while(!isEmpty(open))  
        {  
        	t++;
            //从open表中拿出f值最小的元素,并将拿出的元素放入closed表中  
            popNode(open , tmpNode); 
            addNode(closed , tmpNode);
    		count_extendnode=count_extendnode+1;    
    		  
            cout << "第" << numcount++ << "个状态是:" << endl;  
            outputStatus(tmpNode);  
            cout << "其f值为:" << tmpNode->fvalue << endl;  
            cout << "其g值为:" << tmpNode->gvalue << endl;  
            cout << "其h值为:" << tmpNode->hvalue << endl;  
      
      
           /* //如果拿出的元素是目标状态则跳出循环  
            if(computeHValue(tmpNode) == 0)  
            {  count_extendnode=count_extendnode-1;
                getGoal = true;  
                break;  
            }*/ 
    		//如果拿出的元素是目标状态则跳出循环  
            if(hasSameStatus(tmpNode,Target)== true)  
            {  count_extendnode=count_extendnode-1;
                getGoal = true;  
                break;  
            }  
      
            //产生当前检测结点的后继(与祖先不同)结点列表,产生的后继结点的parent属性指向当前检测的结点  
            SpringLink(tmpNode , spring);  
      
            //遍历检测结点的后继结点链表  
            while(!isEmpty(spring))  
            {  
                popNode(spring , tmpLNode);  
                //状态在open表中已经存在,thePreNode参数在这里并不起作用  
                if(inLink(tmpLNode , open , tmpChartNode , thePreNode))  
                {  
                    addSpringNode(tmpNode , tmpChartNode);  
                    if(tmpLNode->gvalue < tmpChartNode->gvalue)  
                    {  
                        tmpChartNode->parent = tmpLNode->parent;  
                        tmpChartNode->gvalue = tmpLNode->gvalue;  
                        tmpChartNode->fvalue = tmpLNode->fvalue;  
                    }  
                    free(tmpLNode);  
                }  
                //状态在closed表中已经存在  
                else if(inLink(tmpLNode , closed , tmpChartNode , thePreNode))  
                {  
                    addSpringNode(tmpNode , tmpChartNode);  
                    if(tmpLNode->gvalue < tmpChartNode->gvalue)  
                    {  
                        PNode commu;  
                        tmpChartNode->parent = tmpLNode->parent;  
                        tmpChartNode->gvalue = tmpLNode->gvalue;  
                        tmpChartNode->fvalue = tmpLNode->fvalue;  
                        freeSpringLink(tmpChartNode->child);  
                        tmpChartNode->child = NULL;  
                        popNode(thePreNode , commu);  
                        addAscNode(open , commu);  
                    }  
                    free(tmpLNode);  
                }  
                //新的状态即此状态既不在open表中也不在closed表中  
                else  
                {  
                    addSpringNode(tmpNode , tmpLNode);  
                    addAscNode(open , tmpLNode); 	
    				count_sumnode+=1;//生成节点			 
                }  
            }  
        }  
      
        //目标可达的话,输出最佳的路径  
        if(getGoal)  
        {  
            cout << endl;  
            cout << "最佳路径长度为:" << tmpNode->gvalue << endl;
    		cout << "最佳路径为:" <<endl;
            outputBestRoad(tmpNode);  
        }  
      
        //释放结点所占的内存  
        freeLink(open);  
        freeLink(closed);  
    //    getch();  
    }  
      
      
    int main()  
    { 	double start = GetTickCount(); 
        AStar();  
        printf("生成节点数目:%d\n",count_sumnode);	
        printf("扩展节点数目:%d\n",count_extendnode); 
        printf("运行时间:%f\n",GetTickCount()-start); 
        return 0;  
    }  

    推荐文章

    欢迎大家关注【小果果学长】微信公众号,期待你的点赞和支持!

    展开全文
  • A*算法实现的N数码的演示程序,可以连续演示,单步演示,也可暂停,调节速度。也可查看A*演示过程中的Open表与Close表,演示完成可生成最优路径。具体实现见博客:...
  • 通过八数码难题来解释A*算法问题描述: 用一个3X3的方格阵来表示该问题的一个状态,每格放置1-8的一个数字,剩下一个空格(用0表示)。剩下一个只能通过数字(或空格)的移动来改变方格阵的状态。 要求:根据...

    通过八数码难题来解释A*算法。

    问题描述: 用一个3X3的方格阵来表示该问题的一个状态,每格放置1-8的一个数字,剩下一个空格(用0表示)。剩下一个只能通过数字(或空格)的移动来改变方格阵的状态。

    要求:根据给定初始布局(即初始状态)和目标布局(即目标状态),如何移动数字才能从初始布局到达目标布局,找到合法的走步序列。

    A*算法是一种有序搜索算法,其特点在于对估价函数的定义上。 估价函数f(n) = g(n) + h(n)。f(n)表示从起始节点S到节点n的最小代价g(n)与从节点n到目标节点的最小代价h(n)之和。讲h(n)定义为所有棋子距离目标位置的曼哈顿距离(与目标位置的水平距离和垂直距离之和)之和。 open表中具有最小f值得节点,就是下一步要扩展的节点。

    /**
     * This file is part of algorithm of Grid9.
     */
    package algorithm;
    
    import java.util.ArrayList;
    import java.util.Comparator;
    
    enum MoveAction{
    	up ,
    	right ,
    	down ,
    	left 
    }
    
    public class GridNine {
    
    	private static ArrayList<TNode> open;
    	private static ArrayList<TNode> closed;
    	
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int[][] start = {{2,8,0}, {1,6,3}, {7,5,4}};
    		int[][] target = {{1,2,3},{8,0,4},{7,6,5}};
    		AStar(start, target, 3, 3);
    		
    	}
    
    	public static void AStar(int[][] start, int[][] target, int rowSize, int colSize) {
    		TNode startNode = new TNode(start, rowSize, colSize);
    		startNode.setG(0);
    		startNode.setH(target);
    		System.out.println("start state: \r\n");
    		startNode.displayGrid();
    		
    		TNode targetNode = new TNode(target,rowSize, colSize);
    		targetNode.setG(0);
    		targetNode.setH(target);
    		System.out.println("target state: \r\n");
    		targetNode.displayGrid();
    		
    		// initialize 
    		open = new ArrayList<TNode>();
    		closed = new ArrayList<TNode>();
    		
    		// Step 1, put start node in open table;
    		open.add(startNode);
    		int step =0;
    		// Step 2: judge if open table is empty; failed if empty; otherwise go to next step
    		while(!open.isEmpty()) {
    			// Step 3: pop first node from open table , and put it in closed;
    			open.sort(new TNodeComparator());
    			TNode currNode = open.remove(0);
    			System.out.printf(" Step %d: \r\n", step++);
    			currNode.displayGrid();
    			closed.add(currNode);
    			
    			if (isSameState(currNode, targetNode)) {
    				System.out.println("success");
    				return;
    			}
    			// expand the currNode to generate it's successor nodes
    			// by moving blank cell in the sequence of : up, right, down, left;
    			TNode nextNode =null;
    			for(int i=0; i< 4; i++) {
    				switch (i) {
    				case 0:
    					nextNode = move(currNode, MoveAction.up, target);
    					break;
    				case 1:
    					nextNode = move(currNode, MoveAction.right, target);
    					break;
    				case 2:
    					nextNode = move(currNode, MoveAction.down, target);
    					break;
    				case 3:
    					nextNode = move(currNode, MoveAction.left, target);
    					break;
    				default:
    					
    					break;
    				}
    				
    				if (nextNode != null) {
    					// check if nextNode is in open table
    					if (open.contains(nextNode)) {
    						TNode old = open.get(open.indexOf(nextNode));
    						// compare the gValue of nextNode with old;
    						if (nextNode.getG()< old.getG()) {
    							old.setParent(currNode);
    							old.setG(nextNode.getG());
    						}
    					}
    					else if (closed.contains(nextNode)) {
    						TNode old = closed.get(closed.indexOf(nextNode));
    						if (nextNode.getG()< old.getG()) {
    							old.setParent(currNode);
    							old.setG(nextNode.getG());
    							// remove old from closed table to open table;
    							closed.remove(old);
    							open.add(old);
    						}
    					}
    					else {
    						// add nextNode to open table  if nextNode is not in open table either in closed table;
    						open.add(nextNode);
    					}
    				}
    			}
    		}
    		
    	}
    	
    	
    	static TNode move(TNode node, MoveAction action, int[][] target){
    		// successor node is forbid to move back to same state as parent to avoid dead loop;
    		if (node.getForbiddenMove() == action)
    			return null;
    		
    		int emptyRow = node.getEmptyRow();
    		int emptyCol = node.getEmptyCol();
    		
    		int newRow =0;
    		int newCol =0;
    		int temp ; // temp variable for element moving;
    		TNode newNode = null; 
    		boolean validMove = false;
    		MoveAction successorForbiddenMove = MoveAction.up;
    		
    		switch(action) { 
    			case down:
    				 newRow = emptyRow +1;
    				 newCol = emptyCol;
    				 successorForbiddenMove = MoveAction.up;
    				break;
    			case left:
    				 newRow = emptyRow ;
    				 newCol = emptyCol-1;
    				 successorForbiddenMove = MoveAction.right;
    				break;
    			case right:
    				 newRow = emptyRow ;
    				 newCol = emptyCol + 1;
    				 successorForbiddenMove = MoveAction.left;
    				break;
    			case up:
    				// try move up
    				 newRow = emptyRow -1;
    				 newCol = emptyCol;
    				 successorForbiddenMove = MoveAction.down;
    				break;
    			default:
    				break;
    		}
    		// check if this movement will cause a element exceed the boundary
    		 validMove = exceedBoundary(newRow, newCol, node.getRowSize(), node.getColSize());
    		 if (validMove) {
    							
    				int[][] nextGrid = node.getGridClone() ;
    				// move empty element up by exchange two elements;
    				temp = nextGrid[newRow][newCol];
    				nextGrid[newRow][newCol] = 0;
    				nextGrid[node.getEmptyRow()][node.getEmptyCol()] = temp;
    			
    				
    				newNode = new TNode(nextGrid,node.getRowSize(), node.getColSize());
    				newNode.setG(node.getG() + 1);
    				newNode.setH(target);
    				newNode.setParent(node);
    				newNode.setForbiddenMove(successorForbiddenMove);
    				
    		 }
    		 else {
    		 }
    					
    		return newNode;
    	}
    	
    	static boolean exceedBoundary(int row, int col, int maxRow, int maxCol) {
    		if (row <0 || col <0 || row >=maxRow || col>=maxCol)
    			return false;
    		return true;
    	}
    	
    	static boolean isSameState(TNode node1, TNode node2) {
    		
    		boolean sameState = true;
    		for (int i = 0; i < node1.getRowSize(); i++) {
    			for (int j = 0; j < node1.getColSize(); j++) {
    				if (node1.getGrid()[i][j] != node2.getGrid()[i][j])
    					sameState = false;
    				break;
    
    			}
    
    		}
    		return sameState;
    
    	}
    	
    }
    
    class TNode implements Comparable<TNode>{
    	
    
    	@Override
    	public int compareTo(TNode o) {
    		// TODO Auto-generated method stub
    		return Integer.compare(this.getFValue(), o.getFValue());
    	}
    
    	private int[][] grid ; // the array of grid elements;
    	private int g = 0;  // represent the estimate cost from Start Node to This Node; using depth of this node in solution tree;
    	private int h = 0;  // the estimate cost from This Node to Target Node; using sum of manhattan distance of this Node to Target Node;
    	
    	private TNode parent;  // the parent node;
    	
    	private int rowSize, colSize = 0;
    	private int emptyRow, emptyCol = 0;
    	private MoveAction forbiddenMove;
    	
    	public TNode(int[][] arr, int row, int col) {
    		rowSize= row;
    		colSize = col;
    		grid = new int[rowSize][colSize];
    		
    		for(int i=0; i<row; i++) {
    			for (int j =0 ; j< col; j++) {
    				grid[i][j] =  arr[i][j];
    				if (0 == arr[i][j]) {
    					emptyRow = i;
    					emptyCol = j;
    				}
    			}
    		}
    	}
    	
    
    	public int[][] getGrid() {
    		return grid;
    	}
    
    	public int[][] getGridClone(){
    		int[][] clone = new int[rowSize][colSize];
    		for(int i=0; i<rowSize; i++) {
    			for(int j=0; j<colSize; j++) {
    				clone[i][j] = grid[i][j];
    								
    			}
    		}
    		return clone;
    	}
    
    	public int getRowSize() {
    		return rowSize;
    	}
    
    
    	public int getColSize() {
    		return colSize;
    	}
    
    
    	public int getEmptyRow() {
    		return emptyRow;
    	}
    
    
    	public void setEmptyRow(int emptyRow) {
    		this.emptyRow = emptyRow;
    	}
    
    
    	public int getEmptyCol() {
    		return emptyCol;
    	}
    
    
    	public void setEmptyCol(int emptyCol) {
    		this.emptyCol = emptyCol;
    	}
    
    
    	public int getG() {
    		return g;
    	}
    
    	public void setG(int g) {
    		this.g = g;
    	}
    
    	public int getH() {
    		return h;
    	}
    
    	public int getFValue() {
    		return this.getG() + this.getH();
    	}
    	
    	/**
    	 * calculate and return the h-value (the sum of distance of every node in grid) ;
    	 * @param target the target state ;
    	 */
    	public void setH(int [][]target) {
    		int distance =0;
    		for(int i=0; i<rowSize; i++) {
    			for(int j=0; j<colSize; j++) {
    				if (grid[i][j] != target[i][j]) {
    					distance ++;
    				}
    			}
    		}
    		h =  distance;
    	}
    
    	public TNode getParent() {
    		return parent;
    	}
    
    	public void setParent(TNode parent) {
    		this.parent = parent;
    	}
    	
    	
    	public MoveAction getForbiddenMove() {
    		return forbiddenMove;
    	}
    
    
    	public void setForbiddenMove(MoveAction forbiddenMove) {
    		this.forbiddenMove = forbiddenMove;
    	}
    
    
    	public void displayGrid() {
    		for(int i=0; i<rowSize; i++) {
    			for(int j=0; j<colSize; j++) {
    				System.out.printf("%d\t", grid[i][j]);
    								
    			}
    			System.out.println();
    		}
    		System.out.printf("\tg: %d, h: %d, f: %d\r\n", g, h, this.getFValue());
    	}
    	
    }
    
    class TNodeComparator implements Comparator<TNode>{
    
    	@Override
    	public int compare(TNode o1, TNode o2) {
    		// TODO Auto-generated method stub
    		return Integer.compare(o1.getFValue(), o2.getFValue());
    	}
    
    	
    	
    }

    测试:

    给出起始状态:

    2 8 0

    1 6 3

    7 5 4

    目标状态:

    1 2 3

    8 0 4

    7 6 5

    运行过程如下:

    Step 0: 

    2 8 0

    1 6 3

    7 5 4

    g: 0, h: 8, f: 8

     Step 1: 

    2 8 3

    1 6 0

    7 5 4

    g: 1, h: 7, f: 8

     Step 2: 

    2 8 3

    1 6 4

    7 5 0

    g: 2, h: 6, f: 8

     Step 3: 

    2 8 3

    1 0 6

    7 5 4

    g: 2, h: 6, f: 8

     Step 4: 

    2 8 3

    1 6 4

    7 0 5

    g: 3, h: 5, f: 8

     Step 5: 

    2 8 3

    1 0 4

    7 6 5

    g: 4, h: 3, f: 7

     Step 6: 

    2 0 8

    1 6 3

    7 5 4

    g: 1, h: 8, f: 9

     Step 7: 

    2 0 3

    1 8 4

    7 6 5

    g: 5, h: 4, f: 9

     Step 8: 

    2 8 3

    0 1 4

    7 6 5

    g: 5, h: 4, f: 9

     Step 9: 

    2 6 8

    1 0 3

    7 5 4

    g: 2, h: 7, f: 9

     Step 10: 

    0 2 8

    1 6 3

    7 5 4

    g: 2, h: 7, f: 9

     Step 11: 

    0 2 3

    1 8 4

    7 6 5

    g: 6, h: 3, f: 9

     Step 12: 

    1 2 8

    0 6 3

    7 5 4

    g: 3, h: 6, f: 9

     Step 13: 

    1 2 3

    0 8 4

    7 6 5

    g: 7, h: 2, f: 9

     Step 14: 

    1 2 3

    8 0 4

    7 6 5

    g: 8, h: 0, f: 8

    success

    展开全文
  • A*算法求解15数码问题 一、问题描述 15数码问题八数码问题,是人工智能中一个很典型的智力问题。15数码问题是在4×4方格盘上,放有15个数码,剩下一个位置为空(方便起见,用0表示空),每一空格其上下左右的...
  • A*算法求解15数码问题

    千次阅读 2018-04-17 11:26:57
    目录 一、问题描述 二、算法简介 三、算法步骤 四、评估函数 五、参考资料 ...一、问题描述 ...利用A*算法进行表1到表2的转换,要求空白块移动次数最少。...转换规则为:空白块只可以与上下左右四个...A*算法是一种在...
  • 提问:如何使用A*算法得到从初始状态到目标状态的搜索过程。 代码如下: #include “pch.h” #include #include <stdlib.h> #include <conio.h> #include <math.h> void Copy_node(struct node *...
  • A*算法求解N数码问题(AI实验一)

    千次阅读 2020-05-21 18:48:01
    A*算法求解N数码问题,要求程序内,输入给定初始状态和目标状态,输出所需步数,过程状态及时间(程序可直接运行,无需再手动输入)。 2.实验目的及要求 熟悉和掌握启发式搜索的定义、估价函数和算法过程 利用A*...
  • * 设计一个启发函数,利用A*算法求解15数码问题 * * 要求: 尽可能用与A*算法一致的思路实现算法, 力求简单明了地给出一个解. * 1)打印并上交带有关键步骤说明的程序代码. * 2)演示运行过程,并回答老师的...
  • 网上的代码大多使用C++实现。... TEST_MODE 表示使用测试样例进行测试,设置为False即可实现随机输入。 MODE代表使用的启发函数,1表示放错位置个数作为估值...AStarAlgorithm函数是A*算法的主体,其他的函数用于作业要...
  • A*搜索算法解决八数码问题-网页版-AngularJS+jQuery
  • A*算法是一种启发式图搜索算法,其特点在于对估价函数的定义上。对于一般的启发式图搜索,总是选择估价函数 f 值最小的节点作为扩展...八数码问题是在 3×3 的九宫格棋盘上,摆有 8 个刻有 1~8 数码的将牌。棋盘中有一
  • A*算法求解八数码问题 Github仓库:https://github.com/dick20/Artificial-Intelligence 问题介绍   八数码问题也称为九宫问题。在3x3的棋盘,摆有个棋子,每个棋子上标有1至8的某一数字,不同棋子上标的数字不...
  • A*算法求解N数码

    2020-05-09 16:39:26
    2.利用A*算法求解N数码难题,理解求解流程和搜索顺序 3.熟练掌握numpy库的相关函数(单独库,需要使用‘pip install numpy’安装) 实验原理: A*算法是一种启发式图搜索算法,其特点在于对估价函数的定义上。对于...
  • 算法程序: 设计一个启发函数,利用A算法求解15数码问题。 要求: 尽可能用与A算法一致的思路实现算法, 力求简单明了地给出一个解. 一、A*算法 A算法是一种常用的启发式搜索算法。 在A算法中,一个结点位置的好坏用...
  • 八数码问题A*算法求解

    万次阅读 2019-05-16 17:51:33
    下面是人工智能八数码问题使用A*算法求解的源码放在博客上记录一下。程序使用放错位置的棋子的个数作为启发式函数。 #include <iostream> #include <vector> #include <queue&g...
  • 人工智能作业,用python实现A*算法搜索解决八数码问题,测试通过

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,661
精华内容 1,064
关键字:

a*算法求解八数码问题