隐式图的搜索问题（Java代码实现）

心已赠人 2023-10-04 08:12 13阅读 0赞

### 文章目录 ###

*   *  一、实验介绍
     *  二、相关Java代码
     *  三、运行结果展示
     *  四、附录
     *   *  1.解法二（C++篇）个人CSDN链接
         *  2.参考文献
     *  五、README文件

## 一、实验介绍 ##

*  建立图的启发式搜索方法求解九宫重排问题。
 *  采用A\*算法求解九宫重排问题。
 *  3х3九宫棋盘，放置数码为1~8的8个棋子，棋盘中留有一个空格，空格周围的棋子可以移动到空格中，从而改变棋盘的布局。根据给定初始布局和目标布局，移动棋子从初始布局到达目标布局，求解移动步骤并输出。请设计算法，使用合适的搜索策略，在较少的空间和时间代价下找到最短路径。
 *  启发式策略工作扩展步骤如下  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70]

## 二、相关Java代码 ##

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collections;
    import java.util.Scanner;
    
    public class main implements Comparable {
        private int[] num = new int[9];
        //估计函数f(n)：从起始状态到目标的最小估计值
        private int evaluation;
        //d(n)：当前的深度，即走到当前状态的步骤
        private int depth;
        //启发函数 h(n)：到目标的最小估计(记录和目标状态有多少个数不同)
        private int 
    heuristic;
        //当前状态的父状态
        private main parent;
        //保存最终路径
        private ArrayList<main> answer = new ArrayList<main>();
    
        public int[] getNum() {
            return num;
        }
    
        public void setNum(int[] num) {
            this.num = num;
        }
    
        public int getDepth() {
            return depth;
        }
    
        public void setDepth(int depth) {
            this.depth = depth;
        }
    
        public int getEvaluation() {
            return evaluation;
        }
    
        public void setEvaluation(int evaluation) {
            this.evaluation = evaluation;
        }
    
        public int getHeuristic() {
            return
    heuristic;
        }
    
        public void setHeuristic(int
    heuristic) {
            this.
    heuristic =
    heuristic;
        }
    
        public main getParent() {
            return parent;
        }
    
        public void setParent(main parent) {
            this.parent = parent;
        }
    
        /**
         * 判断当前状态是否为目标状态
         */
        public boolean isTarget(main target) {
            return Arrays.equals(getNum(), target.getNum());
        }
    
        /**
         * 求估计函数f(n) = g(n)+h(n);
         * 初始化状态信息
         */
        public void init(main target) {
            int temp = 0;
            for (int i = 0; i < 9; i++) {
                if (num[i] != target.getNum()[i])
                    //记录当前节点与目标节点差异的度量
                    temp++;
            }
            this.setHeuristic(temp);
            if (this.getParent() == null) {
                //初始化步数（深度）
                this.setDepth(0);
            }
            else {
                //记录步数
                this.depth = this.parent.getDepth() + 1;
            }
            //返回当前状态的估计值
            this.setEvaluation(this.getDepth() + this.getHeuristic());
        }
    
        /**
         * 求逆序值并判断是否有解，逆序值同奇或者同偶才有解
         */
        public boolean isSolvable(main target) {
            int reverse = 0;
            for (int i = 0; i < 9; i++) {
                //遇到0跳过
                for (int j = 0; j < i; j++) {
                    if (num[j] > num[i] && num[j] != 0 && num[i] != 0)
                        reverse++;
                    if (target.getNum()[j] > target.getNum()[i] && target.getNum()[j] != 0 && target.getNum()[i] != 0)
                        reverse++;
                }
            }
            if (reverse % 2 == 0)
                return true;
            return false;
        }
    
        /**
         * 对每个子状态的f(n)进行由小到大排序
         */
        public int compareTo(Object o) {
            main c = (main) o;
            //默认排序为f(n)由小到大排序
            return this.evaluation - c.getEvaluation();
        }
    
        /**
         * 返回0在八数码中的位置
         */
        public int getZeroPosition() {
            int position = -1;
            for (int i = 0; i < 9; i++) {
                if (this.num[i] == 0) {
                    position = i;
                }
            }
            return position;
        }
    
        /**
         * 去重复，当前状态不重复返回-1
         * 状态集合
         * 判断当前状态是否存在于open表中
         */
        public int isContains(ArrayList<main> open) {
            for (int i = 0; i < open.size(); i++) {
                if (Arrays.equals(open.get(i).getNum(), getNum())) {
                    return i;
                }
            }
            return -1;
        }
    
        /**
         * 一维数组
         */
        public boolean isMoveUp() {
            int position = getZeroPosition();
            if (position <= 2) {
                return false;
            }
            return true;
        }
    
    
        public boolean isMoveDown() {
            int position = getZeroPosition();
            if (position >= 6) {
                return false;
            }
            return true;
        }
    
    
        public boolean isMoveLeft() {
            int position = getZeroPosition();
            if (position % 3 == 0) {
                return false;
            }
            return true;
        }
    
    
        public boolean isMoveRight() {
            int position = getZeroPosition();
            if ((position) % 3 == 2) {
                return false;
            }
            return true;
        }
    
        /**
         *  返回移动后的状态
         */
        public main moveUp(int move) {
            main temp = new main();
            int[] num1
     = num.clone();
            temp.setNum(num1
    );
            //0的位置
            int position = getZeroPosition();
            //与0换位置的元素的位置
            int p = 0;
            switch (move) {
                case 0:
                    p = position - 3;
                    temp.getNum()[position] = num[p];
                    break;
                case 1:
                    p = position + 3;
                    temp.getNum()[position] = num[p];
                    break;
                case 2:
                    p = position - 1;
                    temp.getNum()[position] = num[p];
                    break;
                case 3:
                    p = position + 1;
                    temp.getNum()[position] = num[p];
                    break;
            }
            temp.getNum()[p] = 0;
            return temp;
        }
    
        /**
         * 按照3*3格式输出
         */
        public void print() {
            for (int i = 0; i < 9; i++) {
                if (i % 3 == 2) {
                    System.out.println(this.num[i]);
                } else {
                    System.out.print(this.num[i] + "  ");
                }
            }
        }
    
        /**
         * 将最终答案路径保存下来并输出
         */
        public void printRoute() {
            main temp = null;
            int count = 0;
            temp = this;
            System.out.println("****③开始移动****");
            while (temp != null) {
                answer.add(temp);
                temp = temp.getParent();
                count++;
            }
            for (int i = answer.size() - 1; i >= 0; i--) {
                answer.get(i).print();
                System.out.println("************");
            }
            System.out.println("**④至少需要移动的步数**：" + (count - 1));
        }
    
        /**
         *  open表
         *  close表
         *  父状态
         *  目标状态
         */
        public void operation(ArrayList<main> open, ArrayList<main> close, main parent, main target) {
            //判断是否在close表中
            if (this.isContains(close) == -1) {
                //获取在open表中的位置
                int position = this.isContains(open);
                //判断是否在open表中
                if (position == -1) {
                    //指明它的父状态
                    this.parent = parent;
                    //计算它的估计值
                    this.init(target);
                    //把它添加进open表
                    open.add(this);
                } else {
                    //跟已存在的状态作比较，如果它的步数较少则是较优解
                    if (this.getDepth() < open.get(position).getDepth()) {
                        //把已经存在的相同状态替换掉
                        open.remove(position);
                        this.parent = parent;
                        this.init(target);
                        open.add(this);
                    }
                }
            }
        }
    
        public static void main(String args[]) {
            //定义open表
            ArrayList<main> open = new ArrayList<main>();
            //定义close表
            ArrayList<main> close = new ArrayList<main>();
            main start = new main();
            main target = new main();
    
            Scanner s = new Scanner(System.in);
            int num2
    [] = new int[9];
            int 
    num3[] = new int[9];
            System.out.println("***①请输入初始状态***：");
            for (int i = 0; i < 9; i++) {
                num2
    [i] = s.nextInt();
            }
            System.out.println("***②请输入目标状态***：");
            for (int j = 0; j < 9; j++) {
                
    num3[j] = s.nextInt();
            }
            s.close();
    
            start.setNum(num2
    );
            target.setNum(
    num3);
            long startTime = System.currentTimeMillis();
            if (start.isSolvable(target)) {
                //初始化初始状态
                start.init(target);
                open.add(start);
                while (open.isEmpty() == false) {
                    //按照evaluation的值排序
                    Collections.sort(open);
                    //从open表中取出最小估值的状态并移出open表
                    main best = open.get(0);
                    open.remove(0);
                    close.add(best);
    
                    if (best.isTarget(target)) {
                        //输出
                        best.printRoute();
                        long end = System.currentTimeMillis();
                        System.out.println("**⑤此程序运行： " + (end - startTime) + " ms");
                        System.exit(0);
                    }
    
                    int move;
                    //由best状态进行扩展并加入到open表中
                    //0的位置上移之后状态不在close和open中设定best为其父状态，并初始化f(n)估值函数
                    //判断是否可以上移
                    if (best.isMoveUp()) {
                        //上移标记
                        move = 0;
                        //best的一个子状态
                        main up = best.moveUp(move);
                        up.operation(open, close, best, target);
                    }
                    //0的位置下移之后状态不在close和open中设定best为其父状态，并初始化f(n)估值函数
                    if (best.isMoveDown()) {
                        move = 1;
                        main down = best.moveUp(move);
                        down.operation(open, close, best, target);
                    }
                    //0的位置左移之后状态不在close和open中设定best为其父状态，并初始化f(n)估值函数
                    if (best.isMoveLeft()) {
                        move = 2;
                        main left = best.moveUp(move);
                        left.operation(open, close, best, target);
                    }
                    //0的位置右移之后状态不在close和open中设定best为其父状态，并初始化f(n)估值函数
                    if (best.isMoveRight()) {
                        move = 3;
                        main right = best.moveUp(move);
                        right.operation(open, close, best, target);
                    }
                }
            }
            else {
                System.out.println("抱歉，目标状态无法实现！");
            }
        }
    }

## 三、运行结果展示 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][20210312215731974.png]

## 四、附录 ##

### 1.解法二（C++篇）个人CSDN链接 ###

[https://editor.csdn.net/md/?articleId=114684468][https_editor.csdn.net_md_articleId_114684468]

### 2.参考文献 ###

1.[https://www.sogou.com/link?url=hedJjaC291OB0PrGj\_c3jPqV8iJQiL4Wim8oR1fyrtNWiXnyK1n-GVFro1BrEKsSHcpPnSGgxJEVuzaE0zfm9A…][https_www.sogou.com_link_url_hedJjaC291OB0PrGj_c3jPqV8iJQiL4Wim8oR1fyrtNWiXnyK1n-GVFro1BrEKsSHcpPnSGgxJEVuzaE0zfm9A]  
2.[https://zhuanlan.zhihu.com/p/45663817][https_zhuanlan.zhihu.com_p_45663817]

## 五、README文件 ##

1.数据结构：隐式图的搜索问题
    2.编程语言：Java
    3.编译环境：JDK1.8
    4.开发工具：IntelliJ IDEA

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210312215251607.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210312215658133.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210312215709896.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210312215721569.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MTcwMjY1,size_16,color_FFFFFF,t_70
[20210312215731974.png]: https://img-blog.csdnimg.cn/20210312215731974.png
[https_editor.csdn.net_md_articleId_114684468]: https://editor.csdn.net/md/?articleId=114684468
[https_www.sogou.com_link_url_hedJjaC291OB0PrGj_c3jPqV8iJQiL4Wim8oR1fyrtNWiXnyK1n-GVFro1BrEKsSHcpPnSGgxJEVuzaE0zfm9A]: https://www.sogou.com/link?url=hedJjaC291OB0PrGj_c3jPqV8iJQiL4Wim8oR1fyrtNWiXnyK1n-GVFro1BrEKsSHcpPnSGgxJEVuzaE0zfm9A..
[https_zhuanlan.zhihu.com_p_45663817]: https://zhuanlan.zhihu.com/p/45663817