智能算法实验——八数码问题

八数码游戏实验

一. 问题简介

八数码游戏是经典的益智游戏。九宫排字问题（又称八数码问题）是人工智能当中有名的难题之一。问题是在 3 X 3 方格盘上放有八个数码，剩下第九个为空，每一空格其上下左右的数字可移动至空格。

问题给定初始位置和目标位置，要求通过一些列的数码移动，将初始位置转化为目标位置。

二. 前置知识

康托展开

康托展开的定义

康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。

其中， 为整数，表示原数的第 位在当前未出现元素中是排在第几个，并且有 。

Code

int cantor(int a[], int n) {
  int ans = 0, num = 0;
  for(int i = 1; i <= n; i++) {
    for(int j = i + 1; j <= n; j++) {
      if(a[j] < a[i]) {
        num++;
      }
    }
    ans += num * factorial[n - i]; // 阶乘
    num = 0;
  }
  return ans;
}

逆康托展开

同理，给定一个排列的序号，可以通过逆康拓得到该排列。例如，给出一到五的排列(1，2，3，4，5)，想要得到全排列中排位第61的排列，通过逆康托展开可以得到排列组合为 34152。具体过程如下：
(1) 用 61/ 4! = 2余13，说明a[5]=2,说明比首位小的数有2个，所以首位为3。
(2) 用 13 / 3! = 2余1，说明a[4]=2，说明在第二位之后小于第二位的数有2个，所以第二位为4。
(3) 用 1 / 2! = 0余1，说明a[3]=0，说明在第三位之后没有小于第三位的数，所以第三位为1。
(4) 用 1 / 1! = 1余0，说明a[2]=1，说明在第二位之后小于第四位的数有1个，所以第四位为5。
(5) 最后一位补上剩余的数字2。
通过以上分析，所求排列组合为 34152。

Code

void decantor(int x, int n) {
  vector<int> v, a;
  for(int i = 1; i <= n; i++) {
    v.emplace_back(i);
  }
  for(int i = n; i >= 1; i--) {
    int r = x % factorial[i - 1];
    int t = x / factorial[i - 1];
    x = r;
    sort(v.begin(), v.end());
    a.emplace_back(v[t]);
    v.erase(v.begin() + t);
  }
}

启发式搜索

启发式搜索算法, 即A*算法，读音为A-star。

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

启发中的估价是用估价函数表示的，如：

其中 是节点 的估价函数， 是在状态空间中从初始节点到 节点的实际代价， 是从 到目标节点最佳路径的估计代价。在这里主要是 体现了搜索的启发信息，因为 是已知的。如果说详细点， 代表了搜索的广度的优先趋势。但是当 时，可以省略 ，而提高效率。

启发函数设定

令， 其中， 为当前节点的步数， 为当前数码与目标数码的曼哈顿距离之和。

算法设计

1. 将初始数码压入优先队列。
2. 取出此时堆顶优先级最高的元素。
3. 扩展子节点，向上下左右四个方向移动空格，生成对应子节点。
4. 判断当前子节点是否为最终状态，如果是最终状态则结束搜索，否则执行5。
5. 通过哈希判断是否到达过该节点，如果该状态尚未到达，则放入优先队列。
6. 跳转到步骤2。

八数码问题Code(Astar + 康托展开)

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N = 3.7e5;
const int mod = 998244353;
int pre[N], v[N], factorial[20], a[20], Destination_Cantor;
int dist[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};
bool vis[N];
pair<int, int> point[50];
char table[5] = "udlr";
struct node {
  int maze[3][3];
  int x, y; // 记录x的位置
  int f, g, h; // A*的估价函数
  int flag;
  bool operator < (const node &s) const {
    return f > s.f;
  }
}start, tail;
int Cantor(node tmp) { // 康托展开
  int tot = 0;
  for(int i = 0; i < 3; i++) {
    for(int j = 0; j < 3; j++) {
      a[++tot] = tmp.maze[i][j];
    }
  }
  int ans = 0, num = 0;
  for(int i = 1; i <= tot; i++) {
    for(int j = i + 1; j <= tot; j++) {
      if(a[j] < a[i]) {
        num++;
      }
    }
    ans += num * factorial[tot - i]; // 阶乘
    num = 0;
  }
  return ans + 1;
}
bool check(node tmp) {
    int ar[15] = {0};
    int tot = 0;
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            ar[++tot] = tmp.maze[i][j];
        }
    }
    int sum = 0; 
    for(int i = 1; i <= tot; i++) {
        for(int j = 1; j < i; j++) {
            if(ar[j] == 'x' || ar[i] == 'x') continue;
            if(ar[j] > ar[i]) {
                sum++;
            }
        }
    }
  if(sum & 1) return false;
    return true;
}
void Init() {
  factorial[0] = 1;
  for(int i = 1; i <= 9; i++) {
    factorial[i] = factorial[i - 1] * i;
  }
  node tmp;
  int tot = 0;
  for(int i = 0; i < 3; i++) {
    for(int j = 0; j < 3; j++) {
      tmp.maze[i][j] = ++tot;
    }
  }
  tmp.maze[2][2] = 'x';
  Destination_Cantor = Cantor(tmp);
  int l = 0, r = 0;
  for(int i = 1; i <= 9; i++) {
    point[i % 9].first = l;
    point[i % 9].second = r;
    r++;
    if(r == 3) {
      l++, r = 0;
    }
  }
}
int cal_H(node tmp) {
  int sum = 0;
  for(int i = 0; i < 3; i++) {
    for(int j = 0; j < 3; j++) {
      int now = tmp.maze[i][j];
      if(now == 'x') now = 0;
      sum += abs(point[now].first - i) + abs(point[now].second - j);
    }
  }
  return sum;
}
void print(node tmp) {
  string ans;
  int sum = Destination_Cantor;
  while(pre[sum] != -1) {
    ans += table[v[sum]];
    sum = pre[sum];
  }
  reverse(ans.begin(), ans.end());
  cout << ans << '\n';
}
void Astar(node now) {
    priority_queue<node> q;
  memset(vis, 0, sizeof(vis));
  memset(pre, -1, sizeof(pre));
  memset(v, -1, sizeof(v));
    now.h = cal_H(now), now.g = 0, now.flag = -1, now.f = now.g + 2 * now.h;
  q.push(now);
  vis[Cantor(now)] = true;
    while(!q.empty()) {
    auto tmp = q.top(); q.pop();
    if(Cantor(tmp) == Destination_Cantor) {
      print(tmp);
      return ;
    }
    for(int i = 0; i < 4; i++) {
      tail.x = tmp.x + dist[i][0];
      tail.y = tmp.y + dist[i][1];
      int x = tmp.x, y = tmp.y;
      if(tail.x < 0 || tail.x >= 3 || tail.y < 0 || tail.y >= 3) continue;
      for(int j = 0; j < 3; j++) {
        for(int k = 0; k < 3; k++) {
          tail.maze[j][k] = tmp.maze[j][k]; 
        }
      }
      swap(tail.maze[x][y], tail.maze[tail.x][tail.y]);
      int cur = Cantor(tail);
      if(!check(tail)) {
        continue;
      }
      if(!vis[cur]) {
        vis[cur] = true;
        tail.g = tmp.g + 1;
        tail.h = cal_H(tail);
        tail.f = tail.g + 2 * tail.h;
        if(tail.x == x + 1) tail.flag = 1; // 向下
        else if(tail.x == x - 1) tail.flag = 2; // 向上
        else if(tail.y == y + 1) tail.flag = 3; // 向右
        else if(tail.y == y - 1) tail.flag = 4; // 向左
        pre[cur] = Cantor(tmp);
        v[cur] = i;
        q.push(tail);
      }
    }
    }
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  string str;
  Init();
  while(getline(cin, str)) {
    int r = 0, c = 0;
    for(int i = 0; i < str.size(); i++) {
      if(isdigit(str[i])) {
        start.maze[r][c] = str[i] - '0';
        c++;
        if(c == 3) {
          c = 0, r++;
        } 
      } else if(str[i] == 'x') {
        start.maze[r][c] = str[i];
        start.x = r, start.y = c;
        c++;
        if(c == 3) {
          c = 0, r++;
        }
      }
    }
    int now = Cantor(start);
    if(now == Destination_Cantor) {
      cout << '\n'; continue;
    }
    if(!check(start)) {
      cout << "unsolvable\n";
      continue;
    }
    Astar(start);
  }
  return 0;
}
// 1234567x8
/*
1 2 3 
4 5 6
7 x 8
*/