算法提高课汇总

算法思路

$A^*$算法 — 对最少步数模型$bfs$的优化.

原题是否有解

如果题目无解, 即原图中不存在最短路径时, $A^*$算法最终会像$bfs$一样遍历所有状态, 且每次优先
队列操作时间为$O(\lg(n))$, 此时算法的时间复杂度比普通的$bfs$还糟糕. 所以首先判断题目是否有解.

八数码有解的充要条件: 将原状态按行展开成一维数列, 若数列逆序对数目为奇数, 则原题无解; 否则有解.
(对于展开后列数为奇数的数码均适用).

必要性

原题有解 --> 逆序对个数为偶数.

考虑将数字$a$与空格x交换位置:

• 同行交换: 一维展开数列不变, 逆序对数目的奇偶性不变.

• 同列交换: 向前/向后跳过两个数字. 也就是交换后有两个逆序对发生变化, 变化的组合为$(+1, +1)$,
  $(+1,-1)$, $(-1,-1)$, 任意组合对数列逆序对个数的奇偶性均无影响.

由于目标状态展开后为12345678, 逆序对数目为0, 即偶数. 由于交换位置不会改变数列逆序对数目的
奇偶性, 所以如果原题有解, 则原状态展开后逆序对数目必定是偶数.

必要性

逆序对个数为偶数 --> 原题有解:

略.

启发函数

估价函数$f$的计算:

对于每个数字, 其从原位置到目标位置至少($f(u)\le g(u)$)需要哈密顿距离步.

$f(state)$: 所有数字到其目标位置哈密顿距离之和.

具体实现

AcWing 1107. 魔板 问题的优化 — 加入启发函数和优先队列.

具体代码

#include <queue>
#include <iostream>
#include <algorithm>
#include <unordered_map>

#define x first
#define y second

using namespace std;

typedef pair<int, string> pis; //<启发函数, 顶点状态>

int f(string u)
{
    int res = 0;
    for( int i = 0; i < 9; i ++ )
    {
        if( u[i] != 'x' )
        {
            int t = u[i] - '1'; //目标位置
            res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);
        }
    }
    return res;
}

string bfs(string start)
{
    string end = "12345678x"; //目标状态
    char op[] = "urdl";
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

    unordered_map<string, int> dist;
    unordered_map<string, pis> pre;
    priority_queue<pis, vector<pis>, greater<pis>> heap;
    dist[start] = 0;
    heap.push({0, start});

    while( heap.size() )
    {
        pis cur = heap.top(); heap.pop();
        string u = cur.y;

        if( u == end )  break; //终点出队 算法结束

        int x, y;
        for( int i = 0; i < 9; i ++ )
        {
            if( u[i] == 'x' )
            {
                x = i / 3, y = i % 3;
                break;
            }
        }
        for( int i = 0; i < 4; i ++ )
        {
            int nx = x + dx[i], ny = y + dy[i];
            if( nx < 0 || nx >= 3 || ny < 0 || ny >= 3 )    continue;

            string v = u;
            swap(v[x * 3 + y], v[nx * 3 + ny]); //扩展顶点u -> v
            if( dist.count(v) == 0 || dist[v] > dist[u] + 1 )
            {//类似dijkstra算法过程
                dist[v] = dist[u] + 1;
                pre[v] = {op[i], u};
                heap.push({dist[v] + f(v), v});
            }
        }
    }

    string res;
    while( end != start )
    {
        res += pre[end].x;
        end = pre[end].y;
    }
    reverse(res.begin(), res.end());
    return res;
}

int main()
{
    string start, seq;
    char c;
    while( cin >> c )
    {
        start += c;
        if( c != 'x' )  seq += c;
    }

    int cnt = 0; //逆序对个数
    for( int i = 0; i < 8; i ++ )
    {
        for( int j = i + 1; j < 8; j ++ )
        {
            if( seq[i] > seq[j] )
                cnt ++;
        }
    }
    if( cnt & 1 )   puts("unsolvable");
    else    cout << bfs(start) << endl;

    return 0;
}