pku 1077 Eight 经典8数码问题单向BFS + A* BFS + 双向BFS

蔚落 2022-08-10 09:35 146阅读 0赞

本题的判重的状态的保存用到了全排列的变进制hash方法.

详细的解释见:

[http://www.cppblog.com/longzxr/archive/2009/08/04/92151.html][http_www.cppblog.com_longzxr_archive_2009_08_04_92151.html]

下面是我三个版本的算法实现

分别为:

单向BFS

A\* BFS

双向BFS

对于本题, 效率递增.

一. 下面是单向BFS算法的实现

目前我的效率只有907MS, 险超时.

Memory: 4132K, Time: 907MS

\#include <iostream> \#include <queue> \#include <stack> using namespace std; int factor\[8\] = \{1, 2, 6, 24, 120, 720, 5040, 40320\}; bool hash\[362880\]; //计算排列的hash值 int get\_hash\_code(char str\[\]) \{ int i, j; int ret = 0, cnt; for(i = 1; i < 9; ++i) \{ cnt = 0; for(j = 0; j < i; ++j) if(str\[j\] > str\[i\]) cnt++; ret += cnt\*factor\[i-1\]; \} return ret; \} struct State \{ char str\[10\]; int place; int hashCode; \}; char begin\[10\]; int beginIndex; char end\[10\] = "123456780"; int dv\[\] = \{-3, 3, -1, 1\}; char dd\[\] = \{'u', 'd', 'l', 'r'\}; char preDir\[362880\]; int preHashCode\[362880\]; inline void exchange(char\* str, int i, int j) \{ char temp = str\[i\]; str\[i\] = str\[j\]; str\[j\] = temp; \} inline bool ok(int place, int d) \{ if(place % 3 == 0 && d == -1) return false; if(place % 3 == 2 && d == 1) return false; if(place / 3 == 0 && d == -3) return false; if(place / 3 == 2 && d == 3) return false; return true; \} bool bfs() \{ memset(hash, 0, sizeof(hash)); queue<State> q; State temp; temp.place = beginIndex; //当前x的位置 strcpy(temp.str, begin); //当前状态字符串 temp.hashCode = get\_hash\_code(temp.str); //当前hashCode preDir\[temp.hashCode\] = '\*'; preHashCode\[temp.hashCode\] = -1; //当前状态的前一状态的hashCode hash\[temp.hashCode\] = true; q.push(temp); while (!q.empty()) \{ State s = q.front(); q.pop(); for(int i = 0; i < 4; ++i) \{ if(ok(s.place, dv\[i\])) \{ temp.place = s.place+dv\[i\]; //当前x的位置 strcpy(temp.str, s.str); //当前状态字符串 exchange(temp.str, s.place, temp.place); temp.hashCode = get\_hash\_code(temp.str); //当前的hashCode if(strcmp(end, temp.str) == 0) \{ preHashCode\[temp.hashCode\] = s.hashCode; preDir\[temp.hashCode\] = dd\[i\]; char ans\[1000\]; int index = 0; int tempHashCode = temp.hashCode; while(preHashCode\[tempHashCode\] != -1) \{ ans\[index++\] = preDir\[tempHashCode\]; tempHashCode = preHashCode\[tempHashCode\]; \} for(int j = index-1; j >= 0; --j) printf("%c", ans\[j\]); printf("/n"); return true; \} if(!hash\[temp.hashCode\]) \{ preDir\[temp.hashCode\] = dd\[i\]; preHashCode\[temp.hashCode\] = s.hashCode; 当前状态的前一状态的hashCode hash\[temp.hashCode\] = true; q.push(temp); \} \} \} \} return false; \} int main() \{ int i; for(i = 0; i < 9; ++i) \{ cin >> begin\[i\]; if(begin\[i\] == 'x') \{ begin\[i\] = '0'; beginIndex = i; \} \} begin\[9\] = '/0'; if(!bfs()) printf("unsolvable/n"); return 0; \}

二. 加上A\*算法估价后的A\*搜索代码

Memory: 3868K, Time: 391MS

\#include <iostream> \#include <queue> \#include <stack> using namespace std; int factor\[8\] = \{1, 2, 6, 24, 120, 720, 5040, 40320\}; bool hash\[362880\]; //计算排列的hash值 int get\_hash\_code(char str\[\]) \{ int i, j; int ret = 0, cnt; for(i = 1; i < 9; ++i) \{ cnt = 0; for(j = 0; j < i; ++j) if(str\[j\] > str\[i\]) cnt++; ret += cnt\*factor\[i-1\]; \} return ret; \} struct State \{ char str\[10\]; int place; int hashCode; int g, f; bool operator < (const State& r) const \{ return f > r.f; \} \}; class Cmp \{ public: bool operator()(const State& l, const State& r) const \{ return l < r; \} \}; char begin\[10\]; int beginIndex; char end\[10\] = "123456780"; int dv\[\] = \{-3, 3, -1, 1\}; char dd\[\] = \{'u', 'd', 'l', 'r'\}; char preDir\[362880\]; int preHashCode\[362880\]; inline void exchange(char\* str, int i, int j) \{ char temp = str\[i\]; str\[i\] = str\[j\]; str\[j\] = temp; \} inline bool ok(int place, int d) \{ if(place % 3 == 0 && d == -1) return false; if(place % 3 == 2 && d == 1) return false; if(place / 3 == 0 && d == -3) return false; if(place / 3 == 2 && d == 3) return false; return true; \} inline int get\_dis(int p) \{ return (2-p/3) + (2-p%3); \} bool bfs() \{ memset(hash, 0, sizeof(hash)); priority\_queue<State, vector<State>, Cmp> q; State temp; temp.place = beginIndex; //当前x的位置 strcpy(temp.str, begin); //当前状态字符串 temp.hashCode = get\_hash\_code(temp.str); //当前hashCode preDir\[temp.hashCode\] = '\*'; preHashCode\[temp.hashCode\] = -1; //当前状态的前一状态的hashCode temp.g = 0; temp.f = 0; hash\[temp.hashCode\] = true; q.push(temp); while (!q.empty()) \{ State s = q.top(); q.pop(); for(int i = 0; i < 4; ++i) \{ if(ok(s.place, dv\[i\])) \{ temp.place = s.place+dv\[i\]; //当前x的位置 strcpy(temp.str, s.str); //当前状态字符串 exchange(temp.str, s.place, temp.place); temp.hashCode = get\_hash\_code(temp.str); //当前的hashCode if(strcmp(end, temp.str) == 0) \{ preHashCode\[temp.hashCode\] = s.hashCode; preDir\[temp.hashCode\] = dd\[i\]; char ans\[1000\]; int index = 0; int tempHashCode = temp.hashCode; while(preHashCode\[tempHashCode\] != -1) \{ ans\[index++\] = preDir\[tempHashCode\]; tempHashCode = preHashCode\[tempHashCode\]; \} for(int j = index-1; j >= 0; --j) printf("%c", ans\[j\]); printf("/n"); return true; \} if(!hash\[temp.hashCode\]) \{ preDir\[temp.hashCode\] = dd\[i\]; preHashCode\[temp.hashCode\] = s.hashCode; 当前状态的前一状态的hashCode temp.g = s.g+1; temp.f = temp.g + get\_dis(temp.place); hash\[temp.hashCode\] = true; q.push(temp); \} \} \} \} return false; \} int main() \{ int i; for(i = 0; i < 9; ++i) \{ cin >> begin\[i\]; if(begin\[i\] == 'x') \{ begin\[i\] = '0'; beginIndex = i; \} \} begin\[9\] = '/0'; if(!bfs()) printf("unsolvable/n"); return 0; \}

三. 这是使用双向BFS的代码, 事实证明, 这题还是使用双向BFS更快.

Rank: 207 Memeory: 3232K, Time: 0MS

\#include <iostream> \#include <queue> \#include <stack> \#include <stdio.h> \#include <string.h> using namespace std; int factor\[8\] = \{1, 2, 6, 24, 120, 720, 5040, 40320\}; bool hash1\[362880\]; bool hash2\[362880\]; //计算排列的hash值 int get\_hash\_code(char str\[\]) \{ int i, j; int ret = 0, cnt; for(i = 1; i < 9; ++i) \{ cnt = 0; for(j = 0; j < i; ++j) if(str\[j\] > str\[i\]) cnt++; ret += cnt\*factor\[i-1\]; \} return ret; \} struct State \{ char str\[10\]; int place; int hashCode; \}; char begin\[10\]; int beginIndex; char end\[10\] = "123456780"; int dv\[\] = \{-3, 3, -1, 1\}; char dd1\[\] = \{'u', 'd', 'l', 'r'\}; char dd2\[\] = \{'d', 'u', 'r', 'l'\}; char preDir\[362880\]; int preHashCode\[362880\]; char ans\[1000\]; inline void exchange(char\* str, int i, int j) \{ char temp = str\[i\]; str\[i\] = str\[j\]; str\[j\] = temp; \} inline bool ok(int place, int d) \{ if(place % 3 == 0 && d == -1) return false; if(place % 3 == 2 && d == 1) return false; if(place / 3 == 0 && d == -3) return false; if(place / 3 == 2 && d == 3) return false; return true; \} bool deal1(queue<State>& q1, char& dir, State& s, State& temp) \{ s = q1.front(); q1.pop(); for(int i = 0; i < 4; ++i) \{ if(ok(s.place, dv\[i\])) \{ temp.place = s.place+dv\[i\]; //当前x的位置 strcpy(temp.str, s.str); //当前状态字符串 exchange(temp.str, s.place, temp.place); temp.hashCode = get\_hash\_code(temp.str); //当前的hashCode if(hash2\[temp.hashCode\]) \{ dir = dd1\[i\]; return false; \} if(!hash1\[temp.hashCode\]) \{ preDir\[temp.hashCode\] = dd1\[i\]; preHashCode\[temp.hashCode\] = s.hashCode; 当前状态的前一状态的hashCode hash1\[temp.hashCode\] = true; q1.push(temp); \} \} \} return true; \} bool deal2(queue<State>& q2, char& dir, State& s, State& temp) \{ s = q2.front(); q2.pop(); for(int i = 0; i < 4; ++i) \{ if(ok(s.place, dv\[i\])) \{ temp.place = s.place+dv\[i\]; //当前x的位置 strcpy(temp.str, s.str); //当前状态字符串 exchange(temp.str, s.place, temp.place); temp.hashCode = get\_hash\_code(temp.str); //当前的hashCode if(hash1\[temp.hashCode\]) \{ dir = dd2\[i\]; return false; \} if(!hash2\[temp.hashCode\]) \{ preDir\[temp.hashCode\] = dd2\[i\]; preHashCode\[temp.hashCode\] = s.hashCode; 当前状态的前一状态的hashCode hash2\[temp.hashCode\] = true; q2.push(temp); \} \} \} return true; \} bool bfs() \{ memset(hash1, 0, sizeof(hash1)); memset(hash2, 0, sizeof(hash2)); queue<State> q1; queue<State> q2; State temp; //q1 temp.place = beginIndex; //当前x的位置 strcpy(temp.str, begin); //当前状态字符串 temp.hashCode = get\_hash\_code(temp.str); //当前hashCode preHashCode\[temp.hashCode\] = -1; //当前状态的前一状态的hashCode hash1\[temp.hashCode\] = true; q1.push(temp); //q2 temp.place = 8; strcpy(temp.str, end); temp.hashCode = get\_hash\_code(temp.str); preHashCode\[temp.hashCode\] = -1; hash2\[temp.hashCode\] = true; q2.push(temp); //done while (!q1.empty() && !q2.empty()) \{ char ch; State s; if(!deal1(q1, ch, s, temp)) \{ int index = 0; int v = s.hashCode; while(preHashCode\[v\] != -1) \{ ans\[index++\] = preDir\[v\]; v = preHashCode\[v\]; \} for(int i = index-1; i >= 0; --i) printf("%c", ans\[i\]); printf("%c", ch); v = temp.hashCode; while(preHashCode\[v\] != -1) \{ printf("%c", preDir\[v\]); v = preHashCode\[v\]; \} printf("/n"); return true; \} if(!deal2(q2, ch, s, temp)) \{ int index = 0; int v = temp.hashCode; while (preHashCode\[v\] != -1) \{ ans\[index++\] = preDir\[v\]; v = preHashCode\[v\]; \} for(int i = index-1; i >= 0; --i) printf("%c", ans\[i\]); printf("%c", ch); v = s.hashCode; while(preHashCode\[v\] != -1) \{ printf("%c", preDir\[v\]); v = preHashCode\[v\]; \} printf("/n"); return true; \} \} return false; \} int main() \{ int i; for(i = 0; i < 9; ++i) \{ cin >> begin\[i\]; if(begin\[i\] == 'x') \{ begin\[i\] = '0'; beginIndex = i; \} \} begin\[9\] = '/0'; if(!bfs()) printf("unsolvable/n"); return 0; \}

附：

IDA\*算法：

#include <stdio.h>
    #include <string.h>
    #define ABS(x) ((x)<0?-(x):(x))
    typedef struct
    {
        int stat[10];
        int x;
    }node_t;
    node_t st;
    int stack[1000002];
    int dist[10][10];
    /*
     *  d --  0
     *  r --- 1
     *  u --- 2
     *  l --- 3
     */
    char act[] = "drul";
    int dir[4] = {3, 1, -3, -1};
    int mv[10][5] = {
       {0},
                    {2, 0, 1},      /* 1 */
                    {3, 0, 1, 3},   /* 2 */
                    {2, 0, 3},      /* 3 */
                    {3, 0, 1, 2},   /* 4 */
                    {4, 0, 1, 2, 3},/* 5 */
                    {3, 0, 2, 3},   /* 6 */
                    {2, 1, 2},      /* 7 */
                    {3, 1, 2, 3},   /* 8 */
                    {2, 2, 3}       /* 9 */
                    };
    int found, top, min;
    int get_dist(int i, int j)
    {
        int x1 = (i - 1) / 3 + 1;
        int y1 = (i - 1) % 3 + 1;
        int x2 = (j - 1) / 3 + 1;
        int y2 = (j - 1) % 3 + 1;
        return ABS(x1 - x2) + ABS(y1 - y2);
    }
    void init_dist()
    {
        int i, j;
        for(i = 1;i <= 9; i++)
            for(j = 1;j <= 9; j++) dist[i][j] = get_dist(i, j);
    }
    int heur(node_t node)
    {
        int sum = 0, i;
        for(i = 1;i <= 9; i++) sum += dist[i][node.stat[i]];
        return sum;
    }
    int is_solvable(node_t st)
    {
        int res = 0, i, j;
        for(i = 1;i <= 9; i++)
            for(j = 1;j < i; j++) if(st.stat[i] < st.stat[j]) res++;
        res += dist[9][st.x];
        return (res & 1) == 0;
    }
    int init()
    {
        char str[2];
        int i;
        for(i = 1;i <= 9; i++)
        {
            if(scanf("%s", str) == EOF) return 0;
            if(str[0] == 'x')
            {
                st.stat[i] = 9;
                st.x = i;
            }
            else st.stat[i] = str[0] - '0';
        }
        return 1;
    }
    void output()
    {
        int i;
        for(i = 1;i <= top; i++) printf("%c", act[stack[i]]);
        printf("\n");
    }
    void dfs(int p, int dp, int maxdp)
    {
        int f = heur(st);
        int i, k, t;
        if(min > f) min = f;
        if(f + dp > maxdp || found) return;
        if(f == 0)
        {
            output();
            found = 1;
            return;
        }
        for(i = 1;i <= mv[p][0]; i++)
        {
            k = mv[p][i];
            t = dir[k] + p;
            st.stat[p] = st.stat[t];
            st.stat[t] = 9;
            stack[++top] = k;
            dfs(t, dp + 1, maxdp);
            top--;
            st.stat[t] = st.stat[p];
            st.stat[p] = 9;
        }
    }
    void ida_star(node_t st)
    {
        int maxdp = heur(st);
        found = 0;
        while(found == 0)
        {
            min = 0x7fffffff;
            top = 0;
            dfs(st.x, 0, maxdp);
            maxdp += min;
        }
    }
    int main()
    {
        init_dist();
        while(init())
        {
            if(is_solvable(st) == 0)
            {
                printf("unsolvable\n");
                continue;
            }
            ida_star(st);
        }
        return 0;
    }

[http_www.cppblog.com_longzxr_archive_2009_08_04_92151.html]: http://www.cppblog.com/longzxr/archive/2009/08/04/92151.html