# NPuzzle **Repository Path**: Airsku/npuzzle ## Basic Information - **Project Name**: NPuzzle - **Description**: 人工智能路径搜索实验n-puzzle - **Primary Language**: Unknown - **License**: MulanPSL-2.0 - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 2 - **Forks**: 1 - **Created**: 2022-10-22 - **Last Updated**: 2024-10-28 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # README ## Abstract 本项目分别通过使用不同的搜索算法 Astar，IDAstar 和不同的启发函数 曼哈顿距离，不相交模式数据库 进行求解8-puzzle，15-puzzle问题。 ## Solvable 判断当前npuzzle问题是否可解，具体理论见后面引用条目1。 ```java //逆序数求法：遍历state[i][j]之后的数，统计比state[i][j]小的数的个数， public boolean solvable() {//PathFinding中的方法 //判断初始状态的逆序数的奇偶性是否相同 return ((Position)initialState).parity() == ((Position)goalState).parity(); } //求逆序数inv的奇偶性，返回0/1 public int parity() {//Position中的方法 // 根据Puzzle奇偶阶数分类讨论 int inv=(this.size%2==0)?blank[0]:0; for(int i=0;i6048。同时考虑每个状态和将牌位置以及将牌值有关，所以我们可以基于位进行哈希值。具体可以带入计算，体会一下。 ![](asserts/fig3.png) ```java public static int[] positions3 = {-1, 0, 1, 2, 3, 0, 1, 2, 3}; public static int[] positions4 = {-1, 0, 0, 1, 2, 1, 2, 0, 1, 3, 4, 2, 3, 5, 4, 5}; public int hashCode() { int hash = 0; if(size==3) { for (int i = 0; i < n; i++) { hash += (points[i].row * size + points[i].col) * Math.pow(size * size, DisjointDatabaseBuilder.positions3[points[i].val]); } } else{ for (int i = 0; i < n; i++) { hash += (points[i].row * size + points[i].col) * Math.pow(size * size, DisjointDatabaseBuilder.positions4[points[i].val]); } } return hash; } ``` ## Algorithm #### blinded search BFS，DFS 直接暴力搜索，不多解释。 #### heuristic search A\*，IDA\* **A\***：利用 启发函数计算启发值 来进行深度优先搜索。 ```java //已经访问过的节点集合 private final Set explored; //还未扩展的节点队列，本质是一个优先队列加HashSet private final AbstractFrontier frontier; public Deque search(Problem problem) { //如果可直接判断问题是否可解，无解时直接返回解路径为null if (!problem.solvable()){ return null; } frontier.clear(); explored.clear(); //搜索树的根节点 Node root = problem.root(predictor); this.frontier.add(root); while (true) { if (frontier.isEmpty()) return null; //失败 Node node = frontier.poll(); //choose the lowest-cost node in frontier //如果已经到达目标状态， if (problem.goal(node.getState())) { return generatePath(node); } //将当前结点放入explored表中 explored.add(node.getState()); for (Node child : problem.childNodes(node, predictor)) { // 如果新扩展的节点，没有在Explored和Fringe中出现过。 // 因为两个node的状态相同，则视为二者相同（equals函数）， // 所以contains函数判断frontier中是否存在跟child的状态相同的结点 if (!explored.contains(child.getState()) && !frontier.contains(child)) { frontier.offer(child); } else { //child出现在Explored或Fringe中 //在启发函数满足单调条件的前提下，如果child是出现在Explored表里的节点，肯定不在Fringe中； //而且到达这个节点的新路径肯定不会比旧路径更优 frontier.discardOrReplace(child); } } } } ``` **IDA\***：利用 启发函数计算启发值+剪枝 来进行迭代深度优先搜索。具体算法过程参考本项目中resources/Iterative Deepening A star.pptx文件。 ```java //裁剪阈值 private int cutoff; //下一轮迭代的裁剪阈值 private int newCutoff; //最大迭代深度 private int maxIteratorDepth = 256; //统计扩展结点数 private int expanded = 0; private final Stack openStack; public Deque search(Problem problem) { if (!problem.solvable()){ return null; } //获取根节点 openStack.clear(); Node root = problem.root(predictor); cutoff = root.evaluation(); while (cutoff < maxIteratorDepth) { openStack.push(root); newCutoff = cutoff; //当栈未空时继续，执行带裁剪值的深度优先搜索 expanded = 0; while (!openStack.empty()) { expanded++; Node node = openStack.pop(); //更新裁剪值为未被探索节点中最小的评估值 if (problem.goal(node.getState())) { return generatePath(node); } //当小于等于裁剪值时，继续向深处搜索 for (Node child : problem.childNodes(node, predictor)) { //剪枝，防止节点探索回到父节点 if (child.evaluation() <= cutoff) { if (node.getParent() == null || !node.getParent().equals(child)) { openStack.push(child); } } else { //记录大于当前cutoff的最小值 newCutoff = (newCutoff > cutoff) ? (Math.min(child.evaluation(), newCutoff)) : child.evaluation(); } } } //更新裁剪值 cutoff = newCutoff; } return null; } ``` ：启发函数是启发式搜索的关键所在，启发函数的好坏决定了搜索速度的快慢。 #### heuristic function 不在位将牌数MisPlaced，曼哈顿距离Manhattan，非加性数据库Non-addictiveDatabase，不相交模式数据库DisjointPatternDatabase **不在位将牌数**：计算所有当前状态的某一位置上的值和目标状态对应位置上的值不同的将牌个数。 ```java public int getMisPlaced(Position goal)//Position中的方法 { //如果成员变量mp未初始化，则进行初始化，并保存初始化值，防止以后再用到重复计算 if(this.mp==-1) this.mp=misPlaced(goal); return this.mp; } private int misPlaced(Position goal) { int mp=0; for(int i=0;i0?i-gi:gi-i)+((j-gj)>0?j-gj:gj-j); mht+=t; } } return mht; } ``` **不相交模式数据库**：将原状态划分为多个子状态，对所有子状态到其目标状态的距离进行预计算，将其存储到数据库中，多个子状态的到其目标子状态的距离之和作为原状态的启发值。具体实现看我们提交的代码中的那个builder类。 实现思路：将每个tile分割为子tile，比如8-puzzle划分为两个子集{1，2，3，4}和{5，6，7，8}，分别求他们的构成状态到其目标状态的距离。而如何求子集中子状态到其目标状态的距离呢？比如子集{1，2，3，4}，我们将其看作{1，2，3，4，0，0，0，0，0}，即除1234外其余的将牌都为0，都为空白，1234可以移动至任意空白将牌的位置上。对它进行一个BFS搜索，即可由目标状态导出所有由子集{1，2，3，4}构成的状态。如下图所示，经检验，如此计算的启发值一般大于等于曼哈顿距离求得的启发值，因为存在碰撞冲突的情况。 ![](asserts/fig1.png) ```java private final Queue stateQueue = new ArrayDeque(); public int[] BFS(SubPuzzleState root, int num) { stateQueue.clear(); stateQueue.add(root); HashSet stateSet = new HashSet<>();//保存已经访问过的子状态 stateSet.add(root.hashCode()); SubPuzzleState state, child; int[] cost = new int[num]; while (!stateQueue.isEmpty()) { state = stateQueue.poll(); for (int i = 0; i < root.getN(); i++) { for (int d = 0; d < 4; d++) { if (state.applicable(i, d)) { child = state.move(i, d);//move函数会计算好child的一切属性，包括cost if (!stateSet.contains(child.hashCode())) { stateQueue.add(child); stateSet.add(child.hashCode()); cost[child.hashCode()] = child.getCost(); } } } } } System.out.println("Map size = " + stateSet.size()); stateSet.clear(); return cost; } //具体理论看以下论文 //链接: https://pan.baidu.com/s/1670jDJhP7PasPojNNOT0WA?pwd=1234 提取码: 1234 复制这段内容后打开百度网盘手机App，操作更方便哦 ``` **非加性模式数据库**：略，自行看以下论文。 ``` 不相交模式数据库论文 链接: https://pan.baidu.com/s/1670jDJhP7PasPojNNOT0WA?pwd=1234 提取码: 1234 复制这段内容后打开百度网盘手机App，操作更方便哦 ``` ## Analysis **搜索算法**：是基于启发值的，细节上的优化并不能提高多少效率。只有结构上的优化才有可能加速搜索。迭代加深本身不仅是实现了深度优先的功能，它还隐晦地包含着广度优先的思想，是对BFS和DFS的一个综合，所以速度快。 **启发值**：用于帮助我们选择下一步怎么走，而启发值中包含一定的启发信息，它包含的启发信息越多，启发效果就越好。这也是判定启发函数好坏的一个指标。在上述启发函数中，有misPlaced