Algorithm

N数码问题

Posted by Xsp on January 29, 2018

康托展开

一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。实质是计算当前排列在所有由小到大全排列中的顺序。 计算公式：。

例如，3 5 7 4 1 2 9 6 8 展开为 98884。因为

解释： 排列的第一位是3，比3小的数有两个，以这样的数开始的排列有8!个，因此第一项为 排列的第二位是5，比5小的数有1、2、3、4，由于3已经出现，因此共有3个比5小的数，这样的排列有7!个，因此第二项为 以此类推，直至

// 阶乘
vector<int> factorial{1,1,2,6,24,120,720,5040,40320,362880};

// 时间复杂度 O(n^2)
int cantor(vector<int> board) {
    int x = 0, n = board.size();

    for (int i = 0; i < n; i++) {
        int smaller = 0;
        for (int j = i + 1; j < n; j++) {
            if (board[i] > board[j]) smaller++;
        }
        x += factorial[n - 1 - i] * smaller;
    }

    return x;
}

// 98884
cantor(vector<int>{3, 5, 7, 4, 1, 2, 9, 6, 8});

逆展开

如n=9,x=98884时：

98884 / 8! = 2, 说明2个数比第一个数小，第一位是3, x = 98884 % 8! = 18244
18244 / 7! = 3, 说明3个数比第二个数小，第二位是4, x = 18244 % 7! = 3124
… 以此类推。

// 这里n=9即考虑 1-9的数，如果考虑0的话再另行计算
vector<int> decantor(int x, int n) {
    // avail 存放可选
    vector<int> ret, avail;

    for (int i = 1; i <= n; i++) avail.push_back(i);

    for (int i = n; i >= 1; i--) {
        int quotient = x / factorial[i - 1];
        int remain = x % factorial[i - 1];

        x = remain;

        ret.push_back(avail[quotient]);
        avail.erase(avail.begin() + quotient);
    }

    return ret;
}
// 3, 5, 7, 4, 1, 2, 9, 6, 8
decantor(98884, 9);

广度优先搜索

代码框架

BFS() {
    初始化队列
    while(队列非空 && 未找到目标节点) {
        取队首节点，将扩展出的非重复节点放入队尾(注意去重，不然死循环了)，
        必要时记住每个节点的父节点(例如题目不只要求最小步数，还要求每一步如何走的)
    }
}

N数码有解判断

移动0的位置不改变排列的奇偶性，所以奇排列和偶排列不能相互转换。

即如果当前状态和目标状态都为奇排列或者都为偶排列，那可能有解，但如果不同，则一定无解。

奇排列：排列中逆序数的个数为奇数。

一个问题：在n-puzzle问题中，求逆序数为什么不考虑0？？？

N数码状态存储

字符串

对于一个mn的数组，则存储一个状态就需要 mn 字节。存储代价高。

整数

直接看成一个m*n位整数，例如 3x3的数组，那这个9位数最大为 876543210。如果用字符数组存储，一个字符元素可以放8个状态（256，ASCII码）。这个字符数组仍然需要将近 876543210 / 8 的字节来存储。存储代价依然很高。

理解：因为有很多重复以及不存在的状态，比如 788888888 这个数并没有对应的状态。

n进制数

比如 3x3的数组，用9进制表示的话，最大为 ，转换为十进制 ，又减少了一定的空间。

理解：9进制相对于10进制又减少了一些不存在的状态的表示，比如 799999999 在9进制中不表示，减少的也是这些数的表示。

阶乘

最后，也就是用康托展开了，一一映射，没有浪费的空间来表示不存在的状态。

leetcode 773

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>

using namespace std;

struct Node {
    vector<int> board;
    int x, y, hash;
    int moves;
    Node(vector<int> board, int x, int y, int hash, int moves)
        :board(board), x(x), y(y), hash(hash), moves(moves){}
    Node(){}
};

bitset<720> flags;
vector<vector<int>> dir{ {0, 1}, {0, -1}, {-1, 0}, {1, 0}};
vector<int> factorial{1,1,2,6,24,120,720,5040,40320,362880};

int cantor(vector<int> board) {
    int x = 0, n = board.size();

    for (int i = 0; i < n; i++) {
        int smaller = 0;
        for (int j = i + 1; j < n; j++) {
            if (board[i] > board[j]) smaller++;
        }
        x += factorial[n - 1 - i] * smaller;
    }

    return x;
}

bool check(vector<int> board) {
    int reverseNum = 0;
    for (int i = 0; i < board.size(); i++) {
        if (board[i] == 0) continue;
        for (int j = i + 1; j < board.size(); j++) {
            if (board[j] == 0) continue;
            if (board[i] > board[j]) {
                reverseNum++;
            }
        }
    }
    return reverseNum % 2 == 0;
}

int slidingPuzzle(vector<vector<int>>& board) {
    vector<int> tmpboard;
    int ret = 0, x = 0, y = 0, target = cantor({1,2,3,4,5,0});

    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board[0].size(); j++) {
            if (board[i][j] == 0) {
                x = i;
                y = j;
            }
            tmpboard.push_back(board[i][j]);
        }
    }

    if (!check(tmpboard)) return -1;

    queue<Node> q;
    q.push(Node(tmpboard, x, y, cantor(tmpboard), 0));

    while (!q.empty()) {
        Node cur = q.front();
        q.pop();

        if (cur.hash == target) {
            return cur.moves;
        }
        for (int i = 0 ; i < 4; i++) {
            int tmpX = cur.x + dir[i][0];
            int tmpY = cur.y + dir[i][1];
            if (tmpX < 0 || tmpX > 1 || tmpY < 0 || tmpY > 2) continue;

            Node tmp = cur;
            tmp.board[cur.x * 3 + cur.y] = tmp.board[tmpX * 3 + tmpY];
            tmp.board[tmpX * 3 + tmpY] = 0;

            tmp.x = tmpX;
            tmp.y = tmpY;
            tmp.hash = cantor(tmp.board);
            tmp.moves++;

            if (flags[tmp.hash]) continue;
            flags.set(tmp.hash);

            q.push(tmp);
        }
    }

    return -1;
}

int main() {
    vector<vector<int>> board{
        {3,2,4},
        {1,5,0}
    };
    cout << slidingPuzzle(board) << endl;

    return 0;
}

POJ 1077

一点问题：

1.以下输入为啥不行？

vector<int> board(9);

for (int i = 0; i < 9; i++) {
    cin >> board[i];
    if (board[i] > 9) board[i] = 0;
}

2.一开始没引入 bitset，报错，xcode咋没错？

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>

using namespace std;

struct Node {
    vector<int> board;
    int x, y, hash;
    string path;
    Node(vector<int> board, int x, int y, int hash, string path)
        :board(board), x(x), y(y), hash(hash), path(path){}
    Node(){}
};

bitset<362880> flags;
vector<vector<int>> dir{ {0, 1}, {0, -1}, {-1, 0}, {1, 0}};
string pathDir = "rlud";
vector<int> factorial{1,1,2,6,24,120,720,5040,40320,362880};

int cantor(vector<int> board) {
    int x = 0, n = board.size();

    for (int i = 0; i < n; i++) {
        int smaller = 0;
        for (int j = i + 1; j < n; j++) {
            if (board[i] > board[j]) smaller++;
        }
        x += factorial[n - 1 - i] * smaller;
    }

    return x;
}

bool check(vector<int> board) {
    int reverseNum = 0;
    for (int i = 0; i < board.size(); i++) {
        if (board[i] == 0) continue;
        for (int j = i + 1; j < board.size(); j++) {
            if (board[j] == 0) continue;
            if (board[i] > board[j]) {
                reverseNum++;
            }
        }
    }
    return reverseNum % 2 == 0;
}

string slidingPuzzle(vector<int> board) {
    int ret = 0, x = 0, y = 0, target = cantor({1,2,3,4,5,6,7,8,0});

    for (int i = 0; i < board.size(); i++) {
        if (board[i] == 0) {
            x = i / 3;
            y = i % 3;
            break;
        }
    }

    if (!check(board)) return "unsolvable";

    queue<Node> q;
    q.push(Node(board, x, y, cantor(board), ""));

    while (!q.empty()) {
        Node cur = q.front();
        q.pop();

        if (cur.hash == target) {
            return cur.path;
        }
        for (int i = 0 ; i < 4; i++) {
            int tmpX = cur.x + dir[i][0];
            int tmpY = cur.y + dir[i][1];
            if (tmpX < 0 || tmpX > 2 || tmpY < 0 || tmpY > 2) continue;

            Node tmp = cur;
            tmp.board[cur.x * 3 + cur.y] = tmp.board[tmpX * 3 + tmpY];
            tmp.board[tmpX * 3 + tmpY] = 0;

            tmp.x = tmpX;
            tmp.y = tmpY;
            tmp.hash = cantor(tmp.board);
            tmp.path += pathDir[i];

            if (flags[tmp.hash]) continue;
            flags.set(tmp.hash);

            q.push(tmp);
        }
    }

    return "unsolvable";
}

int main() {

    vector<int> board;

    string s;
    getline(cin, s);

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == ' ') continue;
        if (s[i] == 'x') board.push_back(0);
        else board.push_back(s[i] - '0');
    }

    cout << slidingPuzzle(board) << endl;

    return 0;
}

改进：

  • 双向广搜（DBFS），从目标节点和起始节点同时进行扩展，直到一个扩展队列中出现另外一个队列中已经扩展的节点。即两个扩展方向出现了交点。
  • 预处理，即一开始从目标节点彻底的广搜一遍，找出从目标节点所能到达的其它节点。
  • A*算法。
  • 分支限界法，给定节点以优先级，f(x) = 当前节点到根节点的路径的长度 + 排列X中的不在自然位置的数字的个数。f(x)小的优先级高。

HDU 1043

HDU 1043 有多组数据。而上面POJ只有一组数据，所以直接BFS在HDU上会超时。

以下这样写A不掉。。。不知到是不是输入写的不对。

int main() {
    string s;
    getline(cin, s);

    vector<string> out;
    while (!s.empty()) {
        vector<int> board;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') continue;
            if (s[i] == 'x') board.push_back(0);
            else board.push_back(s[i] - '0');
        }
        out.push_back(slidingPuzzle(board));
        getline(cin, s);
        cout << s << endl;
    }
    for (string str : out) {
        cout << str << endl;
    }
    return 0;
}

参考

CATALOG
    FEATURED TAGS
    前端 360前端星 JavaScript Shell Mac/Linux C++ Algorithm Java 分布式 多线程 Docker Zookeeper