博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
补第四周作业总结——8 puzzle
阅读量:6305 次
发布时间:2019-06-22

本文共 5118 字,大约阅读时间需要 17 分钟。

8 puzzle已经提供了解决思路,早期的人工智能算法A。我只能感觉它的神奇,但是没法创造性地使用它。只能按部就班地完成这周的作业。

难点在于对过程的不理解。这个33的格子搜索算法没有尽头,随着步数的越来越多,所耗资源也越来越大。因此,判断是否可解只能交换两个格子作为twin,同时计算两个,肯定只有一个可解。
因此用数组来表示board,很多步骤实现非常难看。
Board.java

import edu.princeton.cs.algs4.Queue;import edu.princeton.cs.algs4.StdRandom;public class Board {    private int[][] blocks;    private int blank_x; // index of blank block    private int blank_y; // index of blank block    public Board(int[][] blocks){        if(blocks == null)            throw new IllegalArgumentException();        this.blocks = new int[blocks.length][blocks.length];        for(int i=0; i
neighbors() { Queue
que = new Queue<>(); int[][] neighbor; int[][] dirs = new int[][]{ {blank_x-1, blank_y}, {blank_x+1, blank_y}, {blank_x, blank_y-1}, {blank_x, blank_y+1} }; for(int[] dir : dirs){ if(validIdx(dir)){ neighbor = copy(); neighbor[blank_x][blank_y] = neighbor[dir[0]][dir[1]]; neighbor[dir[0]][dir[1]] = 0; que.enqueue(new Board(neighbor)); } } return que; } private void exch(int[][] blocks, int x1, int y1, int x2, int y2) { int temp = blocks[x2][y2]; blocks[x2][y2] = blocks[x1][y1]; blocks[x1][y1] = temp; } private boolean validIdx(int[] dir) { if(dir[0] >= 0 && dir[0] < dimension() && dir[1] >= 0 && dir[1] < dimension()) return true; return false; } private int[][] copy() { int [][] newBlocks = new int[dimension()][dimension()]; for(int i=0; i

Solver.java

import edu.princeton.cs.algs4.In;import edu.princeton.cs.algs4.MinPQ;import edu.princeton.cs.algs4.Queue;import edu.princeton.cs.algs4.StdOut;import java.util.Stack;public class Solver {    private Queue
solutions; public Solver(Board initial) { if(initial == null) throw new IllegalArgumentException(); find(initial); } private boolean find(Board initial) { MinPQ
pq, qp; pq = new MinPQ<>(); qp = new MinPQ<>(); // twin Stack
process = new Stack<>(); solutions = new Queue<>(); pq.insert(new Node(initial, 0)); qp.insert(new Node(initial.twin(), 0)); while(true){ Node chosen = pq.delMin(); Node t_chosen = qp.delMin(); if(chosen.board.isGoal()) { Node end = chosen; while(end != null){ process.add(end.board); end = end.prev; } break; } if(t_chosen.board.isGoal()) { break; } for(Board neighbor : chosen.board.neighbors()) { Node n = new Node(neighbor, chosen.moves+1); n.prev = chosen; if(chosen.prev != null && neighbor.equals(chosen.prev.board)) { continue; // critical optimisation } pq.insert(n); } for(Board neighbor : t_chosen.board.neighbors()) { Node n = new Node(neighbor, t_chosen.moves+1); n.prev = t_chosen; if(t_chosen.prev != null && neighbor.equals(t_chosen.prev.board)) { continue; } qp.insert(n); } } while(! process.isEmpty()) { solutions.enqueue(process.pop()); } return !solutions.isEmpty(); } private class Node implements Comparable
{ public Node prev; public Board board; public int moves; public int priority; public Node(Board board, int moves) { this.board = board; this.moves = moves; priority = moves + board.manhattan(); } @Override public int compareTo(Node o) { return priority - o.priority; } } public boolean isSolvable() { return !solutions.isEmpty(); } public int moves() { return solutions.size()-1; } public Iterable
solution() { if(!isSolvable()) return null; return solutions; } public static void main(String[] args) { // create initial board from file In in = new In(args[0]); int n = in.readInt(); int[][] blocks = new int[n][n]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) blocks[i][j] = in.readInt(); Board initial = new Board(blocks); // solve the puzzle Solver solver = new Solver(initial); // print solution to standard output if (!solver.isSolvable()) StdOut.println("No solution possible"); else { StdOut.println("Minimum number of moves = " + solver.moves()); for (Board board : solver.solution()) StdOut.println(board); } }}

转载于:https://www.cnblogs.com/hyper-xl/p/8507221.html

你可能感兴趣的文章
python 异常
查看>>
last_insert_id()获取mysql最后一条记录ID
查看>>
可执行程序找不到lib库地址的处理方法
查看>>
bash数组
查看>>
Richard M. Stallman 给《自由开源软件本地化》写的前言
查看>>
oracle数据库密码过期报错
查看>>
修改mysql数据库的默认编码方式 .
查看>>
zip
查看>>
How to recover from root.sh on 11.2 Grid Infrastructure Failed
查看>>
rhel6下安装配置Squid过程
查看>>
《树莓派开发实战(第2版)》——1.1 选择树莓派型号
查看>>
在 Linux 下使用 fdisk 扩展分区容量
查看>>
结合AlphaGo算法和大数据的量化基本面分析法探讨
查看>>
如何在 Ubuntu Linux 16.04 LTS 中使用多个连接加速 apt-get/apt
查看>>
《OpenACC并行编程实战》—— 导读
查看>>
机器学习:用初等数学解读逻辑回归
查看>>
如何在 Ubuntu 中管理和使用逻辑卷管理 LVM
查看>>
Oracle原厂老兵:从负面案例看Hint的最佳使用方式
查看>>
把自己Github上的代码添加Cocoapods支持
查看>>
C语言OJ项目参考(2493)四则运算
查看>>