九宫重排

谁践踏了优雅 2022-08-21 01:29 143阅读 0赞

问题描述（[oj][]）  
　　如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。  
经过若干次移动，可以形成第二个图所示的局面。

我们把第一个图的局面记为：12345678.  
　　把第二个图的局面记为：123.46758  
　　显然是按从上到下，从左到右的顺序记录数字，空格记为句点。  
　　本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。  
输入格式  
　　输入第一行包含九宫的初态，第二行包含九宫的终态。  
输出格式  
　　输出最少的步数，如果不存在方案，则输出-1。  
样例输入  
12345678.  
123.46758  
样例输出  
3  
样例输入  
13524678.  
46758123.  
样例输出  
22

> 根据题目的要求，输出最少的步数，很容易确定这是一道广搜题。然而，我们都知道广搜之所以可以实现由近及远的搜索，是因为在程序中维护了一个标记数组来存储已经访问过的状态！哪么这道题该设置一个什么样的数据结构呢？  
> 因为用的是Java，所以直接用了一个Set来存储每一次得到的字符串，代码如下：

import java.util.HashSet;
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    import java.util.Set;
    
    class Type{
        public String str = new String();
        public int step = 0;
        public Type(String str,int step) {
            // TODO Auto-generated constructor stub
            this.str = str;
            this.step = step;
        }
        public void show(){
            System.out.println("str:"+str+",step:"+step);
        }
    }
    //Set比arraylist快，效率高
    public class Main {
    
        public static int tarx,tary;
        public static int[] dirx={-1,1,0,0} ,diry={
       0,0,-1,1};
        public static String src,des;
        public static Queue<Type> que = new LinkedList<Type>();
        public static char[][] grids = new char[3][3];
        public static Set<String> visited = new HashSet<String>();
    
        public static void show(){
            System.out.println("String to Grids:");
            for(int i=0;i<3;i++){
                for(int j=0;j<3;j++) System.out.print(grids[i][j]);
                System.out.println();
            }
        }
        public static void string2Array(String str){
            for(int i=0,j=0;i<3;i++,j+=3) grids[i] = str.substring(j, j+3).toCharArray();
            for(int i=0;i<3;i++){
                for(int j=0;j<3;j++){
                    if(grids[i][j]=='.'){
                        tarx = i;
                        tary = j;
                        break;
                    }
                }
            }
        }
        public static String swap(String str,int cx,int cy,int nx,int ny){
            char a = str.charAt(cx*3+cy);
            char b = str.charAt(nx*3+ny);
            StringBuilder temp = new StringBuilder(str);
            temp.setCharAt(cx*3+cy, b);
            temp.setCharAt(nx*3+ny, a);
            return temp.toString();
        }
    
        public static int BFS(){
            Type head = new Type(src,0);
            visited.add(src);
            que.offer(head);
            int cnt = 0,nx,ny;
            Type cur,next;
            String temp = new String();
            while(!que.isEmpty()){
                cur = que.remove();
                if(cur.str.equals(des)) return cur.step; 
                else{
                    //string2Array(cur.str);//获取当前.所在的位置(tarx,tary)
                    int pos = cur.str.indexOf('.');
                    tarx = pos/3;
                    tary = pos%3;
                    for(int i=0;i<4;i++){
                        nx = tarx+dirx[i];
                        ny = tary+diry[i];//得到下一个点的位置
                        if(nx>=0&&nx<3&&ny>=0&&ny<3){
                            temp = swap(cur.str,tarx,tary, nx, ny);//获取的转换后的字符串
                            if(!visited.contains(temp)){
                                visited.add(temp);
                                next = new Type(temp, cur.step+1);
                                que.offer(next);
                            }
                        }
                    }
                }
            }
            return -1;
        }
    
        public static void main(String[] args) {  
            Scanner in = new Scanner(System.in);
            while(in.hasNext()){
                visited.clear();
                que.clear();
                src = in.next();
                des = in.next();
                long t1 = System.currentTimeMillis();
                int ans = BFS();
                System.out.println(ans);
                long t2 = System.currentTimeMillis();
            // System.out.println("Time cost:"+(t2-t1));
            }
        }  
    
    }

之前做过的题目都是用一个标记数组来存储状态，然而这次用了Set，悲催的超时了  
![运行结果][20160309214438481]

实在不知道该怎么优化了，去网上参考了一下思路，发现了一种更高效的搜索方法——双向广度搜索！  
双向广度优先搜素的一篇博文介绍

广度优先搜索遵循从初始结点开始一层层扩展直到找到目标结点的搜索规则，它只能较好地解决状态不是太多的情况，承受力很有限。  
双向广度搜索，顾名思义就是从正反两个方向进行的搜索，使搜索能尽快接近目标结点，减少了在空间和时间上的复杂度。

有些问题按照广度优先搜索法则扩展结点的规则，既适合顺序，也适合逆序，于是我 们考虑在寻找目标结点或路径的搜索过程中，初始结点向目标结点和目标结点向初始结点同时进行扩展—，直至在两个扩展方向上出现同一个子结点，搜索结束，这 就是双向搜索过程。出现的这个同一子结点，我们称为相交点，如果确实存在一条从初始结点到目标结点的最佳路径，那么按双向搜索进行搜索必然会在某层出现 “相交”，即有相交点，初始结点一相交点一目标结点所形成的一条路径即是所求路径。

使用的数据结构：  
１.backwardQue:从前往后正向搜索的队列，记录正向搜索过程中得到的状态。  
2 .forwardQue:从后往前逆向搜索的队列，记录反向搜索过程中得到的状态。  
由于无论是正向搜索还是逆向搜索，每当在搜索过程中得到一个状态时，都应验证这个状态是否在另一个搜索过程中出现过了，一旦曾经出现了，那么就说明是可以从起始状态到达目标状态的。而且要注意的是，我们不单单要统计在搜索过程中出现的状态，更要统计其从初始状态到达这个状态所走的步数，这样才能在搜索到字符串中时直接返回其键值对的步数。所以在这儿使用的是一个Map而非Set，Map(String，Integer)。  
3 .backwardMap：记录从前往后正向搜索过程中的状态及从初始到达该状态所走的步数。  
4 . forwardMap : 记录从后往前逆向搜索过程中的状态及从初始到达该状态所走的步数。

代码如下：

import java.util.HashMap;
    import java.util.HashSet;
    import java.util.LinkedList;
    import java.util.Map;
    import java.util.Queue;
    import java.util.Scanner;
    import java.util.Set;
    
    class Type{
        public String str = new String();
        public int step = 0;
        public Type(String str,int step) {
            // TODO Auto-generated constructor stub
            this.str = str;
            this.step = step;
        }
        public void show(){
            System.out.println("str:"+str+",step:"+step);
        }
    }
    
    public class Main {
    
        public static int tarx,tary;
        public static int[] dirx={-1,1,0,0} ,diry={
       0,0,-1,1};
        public static String src,des;
        public static char[][] grids = new char[3][3];
        public static Queue<Type> backwardQue = new LinkedList<Type>();
        public static Queue<Type> forwardQue = new LinkedList<Type>();
        public static Map<String, Integer> backwardMap = new HashMap<String, Integer>();
        public static Map<String, Integer> forwardMap = new HashMap<String, Integer>();
    
        public static void show(){
            System.out.println("String to Grids:");
            for(int i=0;i<3;i++){
                for(int j=0;j<3;j++) System.out.print(grids[i][j]);
                System.out.println();
            }
        }
    
        public static String swap(String str,int cx,int cy,int nx,int ny){
            char a = str.charAt(cx*3+cy);
            char b = str.charAt(nx*3+ny);
            StringBuilder temp = new StringBuilder(str);
            temp.setCharAt(cx*3+cy, b);
            temp.setCharAt(nx*3+ny, a);
            return temp.toString();
        }
    
        public static int BFS(){
            Type head = new Type(src,0);
            Type tail = new Type(des,0);
            backwardMap.put(src,0);
            backwardQue.offer(head);
            forwardMap.put(des,0);
            forwardQue.offer(tail);
            int cnt = 0,nx,ny;
            Type cur,next;
            String temp = new String();
            //正向队列和逆向队列的双向搜索
            while(!backwardQue.isEmpty()||!forwardQue.isEmpty()){
                //从前往后的搜索
                if(!backwardQue.isEmpty()){
                    cur =backwardQue.remove();//验证在另一个队列里有没有这个key
                    if(forwardMap.containsKey(cur.str)) return cur.step+forwardMap.get(cur.str); 
                    else{
                        int pos = cur.str.indexOf('.');
                        tarx = pos/3;
                        tary = pos%3;
                        for(int i=0;i<4;i++){
                            nx = tarx+dirx[i];
                            ny = tary+diry[i];//得到下一个点的位置
                            if(nx>=0&&nx<3&&ny>=0&&ny<3){
                                temp = swap(cur.str,tarx,tary, nx, ny);//获取的转换后的字符串
                                if(!backwardMap.containsKey(temp)){
                                    backwardMap.put(temp,cur.step+1);
                                    next = new Type(temp, cur.step+1);
                                    backwardQue.offer(next);
                                }
                            }
                        }
                    }
                }
                //从后往前的搜索
                if(!forwardQue.isEmpty()){
                    cur =forwardQue.remove();//验证在另一个队列里有没有这个key
                    if(backwardMap.containsKey(cur.str)) return cur.step+backwardMap.get(cur.str); 
                    else{
                        int pos = cur.str.indexOf('.');
                        tarx = pos/3;
                        tary = pos%3;
                        for(int i=0;i<4;i++){
                            nx = tarx+dirx[i];
                            ny = tary+diry[i];//得到下一个点的位置
                            if(nx>=0&&nx<3&&ny>=0&&ny<3){
                                temp = swap(cur.str,tarx,tary, nx, ny);//获取的转换后的字符串
                                if(!forwardMap.containsKey(temp)){
                                    forwardMap.put(temp,cur.step+1);
                                    next = new Type(temp, cur.step+1);
                                    forwardQue.offer(next);
                                }
                            }
                        }
                    }
                }
            }
            return -1;
        }
    
        public static void main(String[] args) {  
            Scanner in = new Scanner(System.in);
            while(in.hasNext()){
                backwardMap.clear();
                forwardMap.clear();
                backwardQue.clear();
                forwardQue.clear();
                src = in.next();
                des = in.next();
                long t1 = System.currentTimeMillis();
                int ans = BFS();
                System.out.println(ans);
                long t2 = System.currentTimeMillis();
                //System.out.println("Time cost:"+(t2-t1));
            }
        }  
    
    }

![这里写图片描述][20160310094712395]

偶然发现这道题是属于八数码的一个经典问题，使用的是一种**启发式搜索**。  
[启发式搜索的博文][Link 1]

启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。

[oj]: http://lx.lanqiao.org/problem.page?gpid=T42
[20160309214438481]: /images/20220731/133165cfc4314bc7a5b57b199d7885c5.png
[20160310094712395]: /images/20220731/5d0369e3198d4957b49c2f894761dff3.png
[Link 1]: http://blog.csdn.net/q345852047/article/details/6626684