八数码问题的广搜解法

由来

前几天在openjude做题,做到了http://bailian.openjudge.cn/practice/1077/ 这题,由于对算法还不太熟悉,花了好几个个晚上终于用广搜写出来了。

算法思想

有解性

在做的过程中,很多次发现跑的好像死循环了,觉得不因该,然后Google了一下,发现了八数码问题的有解性。由于八数码问题,并非一定有解,所以我们要判断给出的状态与目标状态的的排列奇偶性,如果奇偶性不一致则无解。

状态扩展

从初始状态逐渐深入,用队列保存扩展出来的节点状态,直到找出目标节点状态,则搜索完成。

存储状态

由于状态空间极大,需要考虑一个好的编码方式,是节点状态存储占用的空间最小。由于状态总数,为9!个,即362880个状态。我们可以将每个状态都看做是从0到8的一个排列组合。用排列在全部排列中的位置来表示。

判断重复

在状态扩展中,如果出现和以前节点同样的状态,则为重复不必考虑,所以我们需要判断是否重复。我们可以用一个大小为362880的判重数组来表示。

状态转移

然而由于我们将状态存储为一个int的排列组合,在状态转移的过程中无法直接使用,所以我们需要将状态从int转换为字符串形式,转移之后在转换为int.所以我们需要两个将状态在两种形式直接转换的函数。

代码


package com.dreamhu;


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.BitSet;

class Node {
    int status;
    int father;
    char move;

    public Node(int status, int father, char move) {
        this.status = status;
        this.father = father;
        this.move = move;
    }
}

public class Main {
    public static final int MAX = 400000;
    static BitSet Flags = new BitSet(362880);
    static char[] result = new char[MAX];
    static Node[] myQueue = new Node[MAX];
    static int qHead;
    static int qTail;
    static char[] sz4Moves = {'u', 'd', 'r', 'l'};
    static long[] factorial = new long[21];
    static long goalStatus = StrStatusToIntStatus("123456780".toCharArray());

    static int GetPermutationNumForInt(int[] perInt, int len) {
        //perInt里放着整数 0到 len-1 的一个排列,求它是第几个排列
        //len不能超过21
        int num = 0;
        boolean[] used = new boolean[21];
        for (int i = 0; i < len; i++) {
            int n = 0;
            for (int j = 0; j < perInt[i]; ++j) {
                if (!used[j])
                    ++n;
            }
            num += n * factorial[len - i - 1];
            used[perInt[i]] = true;

        }
        return num;
    }
    static int GetPermutationNum(char[] s1, char[] s2, int len) {
        int[] perInt = new int[21]; //要转换成 [0,len-1] 的整数的排列
        for (int i = 0; i < len; ++i)
            for (int j = 0; j < len; ++j) {
                if (s2[i] == s1[j]) {
                    perInt[i] = j;
                    break;
                }
            }
        return GetPermutationNumForInt(perInt, len);

    }


    static void GenPermutationByNum(char[] s1, char s2[], int len, int No)
    //根据排列编号,生成排列 len不能超过21
    { //[s1,s1+len) 里面放着第0号 permutation,,排列的每个元素都不一样
        int[] perInt = new int[21]; //要转换成 [0,len-1] 的整数的排列
        boolean[] used = new boolean[21];
        for (int i = 0; i < len; ++i) {
//            int tmp;
//            int n = 0;
            int j;
            for (j = 0; j < len; ++j) {
                if (!used[j]) {
                    if (factorial[len - i - 1] >= No + 1) {
                        break;
                    } else {
                        No -= factorial[len - i - 1];
                    }
                }
            }
            perInt[i] = j;
            used[j] = true;
        }
        for (int i = 0; i < len; ++i) {
            s2[i] = s1[perInt[i]];
        }

    }
    static int StrStatusToIntStatus(final char[] strStatus) {//字符串形式的状态,转换为整数形式的状态(排列序号)
        return GetPermutationNum("012345678".toCharArray(), strStatus, 9);
    }

    static void IntStatusToStrStatus(int n, char[] strStatus) {//整数形式的状态(排列序号),转换为字符串形式的状态
        GenPermutationByNum("012345678".toCharArray(), strStatus, 9, n);
    }

    static long NewStatus(int nStatus, char cMove) {
//求从nStatus经过 cMove 移动后得到的新状态。若移动不可行则返回-1
        char[] szTmp = new char[20];
        int nZeroPos = 0;
        IntStatusToStrStatus(nStatus, szTmp);
        for (int i = 0; i < 9; ++i)
            if (szTmp[i] == '0') {
                nZeroPos = i;
                break;
            } //返回空格的位置
        switch (cMove) {
            case 'u':
                if (nZeroPos - 3 < 0) return -1; //空格在第一行
                else {
                    szTmp[nZeroPos] = szTmp[nZeroPos - 3];
                    szTmp[nZeroPos - 3] = '0';
                }
                break;
            case 'd':
                if (nZeroPos + 3 > 8) return -1; //空格在第三行
                else {
                    szTmp[nZeroPos] = szTmp[nZeroPos + 3];
                    szTmp[nZeroPos + 3] = '0';
                }
                break;
            case 'l':
                if (nZeroPos % 3 == 0) return -1; //空格在第一列
                else {
                    szTmp[nZeroPos] = szTmp[nZeroPos - 1];
                    szTmp[nZeroPos - 1] = '0';
                }
                break;
            case 'r':
                if (nZeroPos % 3 == 2) return -1; //空格在第三列
                else {
                    szTmp[nZeroPos] = szTmp[nZeroPos + 1];
                    szTmp[nZeroPos + 1] = '0';
                }
                break;
        }
        return StrStatusToIntStatus(szTmp);
    }
    static boolean Bfs(int nStatus) { //寻找从初始状态nStatus到目标的路径
        int nNewStatus;
        Flags.clear(); //清除所有扩展标记
        qHead = 0;
        qTail = 1;
        myQueue[qHead] = new Node(nStatus, -1, '0');
        while (qHead != qTail) { //队列不为空
            nStatus = myQueue[qHead].status;
            if (nStatus == goalStatus) //找到目标状态
                return true;
            for (int i = 0; i < 4; i++) { //尝试4种移动
                nNewStatus = (int) NewStatus(nStatus, sz4Moves[i]);
                if (nNewStatus == -1) {
                    continue; //不可移,试下一种
                }
                if (Flags.get(nNewStatus)) {
                    continue; //扩展标记已经存在,则不入队
                }
                Flags.set(nNewStatus, true); //设上已扩展标记
                myQueue[qTail++] = new Node(nNewStatus, qHead, sz4Moves[i]); //新节点入队列
            }
            qHead++;
        }
        return false;
    }
    public static void main(String[] args) {
        // write your code here
        factorial[0] = factorial[1] = 1;
        for (int i = 2; i < 21; ++i)
            factorial[i] = i * factorial[i - 1];
        goalStatus = StrStatusToIntStatus("123456780".toCharArray());
        char[] szLine = new char[50];
        char[] szLine2 = new char[20];
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader bufferedReader = new BufferedReader(reader);
        try {
            szLine = bufferedReader.readLine().toCharArray();
        } catch (IOException e) {
            e.printStackTrace();
        }
        int i, j;
        //将输入的原始字符串变为数字字符串
        for (i = 0, j = 0; i<szLine.length; i++) {
            if (szLine[i] != ' ') {
                if (szLine[i] == 'x') {
                    szLine2[j++] = '0';
                } else {
                    szLine2[j++] = szLine[i];
                }
            }
        }
        szLine2[j] = 0; //字符串形式的初始状态
        int sumGoal = 0; //从此往后用奇偶性判断是否有解
        for (int k = 0; k < 8; ++k) {
            sumGoal += k - 1;
        }
        int sumOri = 0;
        for (int p = 0; p < 9; ++p) {
            if (szLine2[p] == '0')
                continue;
            for (int o = 0; o < i; ++o) {
                if (szLine2[o] < szLine2[o] && szLine2[o] != '0')
                    sumOri++;
            }
        }
        if (sumOri % 2 != sumGoal % 2) {
            System.out.println("unsolvable");
            return;
        }
        //上面用奇偶性判断是否有解
        if (Bfs(StrStatusToIntStatus(szLine2))) {
            int nMoves = 0;
            int nPos = qHead;
            do { //通过father找到成功的状态序列,输出相应步骤
                result[nMoves++] = myQueue[nPos].move;
                nPos = myQueue[nPos].father;
            } while (nPos != 0); //nPos = 0 说明已经回退到初始状态了
            for (int l = nMoves - 1; l >= 0; l--)
                System.out.print(result[l]);
        } else {
            System.out.println("unsolvable");
        }

    }


}
文章目录
  1. 1. 由来
  2. 2. 算法思想
    1. 2.1. 有解性
    2. 2.2. 状态扩展
    3. 2.3. 存储状态
    4. 2.4. 判断重复
    5. 2.5. 状态转移
  3. 3. 代码