7.5 路径寻找问题

引入

很多问题都可以以归结为图的遍历,但这些问题中的图不是事先给定、从程序中读入的,而是由程序动态生成的,称为隐式图。状态空间搜索也与回溯法不同,回溯法一般是要找到一个或者所有满足约束条件的解,儿状态空间搜索一般是要找到一个从初始状态到终止状态的路径。
路径寻找问题可以归结为隐式图的遍历,它的任务是找到一条从初始装套到终止状态的最优路径,而不是像回溯法那样找到一个符合某些要求的解。

例题分析

例题:八数码问题

编号为1~8的8个正方形滑块被摆成3行3列(一个格子留空)。每次可以把与空格相邻的滑块移入空格。给定初始局面和目标局面,求最小移动步数。如果不可能,输出-1。

分析及代码

可以把八数码问题归结为最短路问题,图的结点就是9个格子中的滑块编号。无权图上的最短路可以用BFS求解。

typedef int State[9]; // 定义状态类型
const int amxstate =1000000;
State st[maxstate], goal; // 状态
int dist[maxstate]; // 距离
// 如果需要输出方案,可以加入一个编号数组 int fa[maxstate]

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
// BFS, 返回目标状态在st数组下标
int bfs(){
    init_lookup_table(); // 初始化
    int front = 1, rear = 2;
    while(fornt < rear){
        State& s = st[front];
        if (memcmp(goal, s, sizeof(s)) == 0) return front;
        int z;
        for(z = 0; z < 9; z++) if(!s[z]) break; // 找0
        int x = z/3, y = z%3; // 获取行列编号
        for(int d = 0; d < 4; d++){
            int newx = x + dx[d];
            int newy = y + dy[d];
            int newz = newx * 3 + newy;
            if(newx >= 0 && newx < 3 && newy >= 0 && newy < 3){ // 如果合法
                State& t = st[rear];
                memcpy(&t, &s, sizeof(s)); // 扩展新结点
                t[newz] = s[z];
                t[z] = s[newz];
                dist[rear] = dist[front] + 1; // 更新新结点的距离值
                if(try_to_insert(rear)) rear++; // 如果成功插入查找表,修改队尾指针
            }
        }
        front++; // 扩展完毕之后修改一下队尾指针
    }
    return 0; // 失败返回
}
// 这里用到了memcmp和memcpy完成了整块内存的比较和复制,比用循环要快。
int main(){
    for(int i = 0; i < 9; i++) scanf("%d", &st[1][1]); // 起始状态
    for(int i = 0; i < 9; i++) scnaf("%d", &goal[i]); // 目标状态
    int ans = bfs(); // 返回目标状态的下标
    if(ans > 0) printf("%d\n", dist[ans]);
    else printf("-1\n");
    return 0;
}

代码当中,init_lookup_table()try_to_insert(rear)没有实现。这两项用于初始化和判重。
下面讨论三种常见的方法来解决判重问题。

  • 方法一: 把排列变成整数,然后只开一个一维数组。也就是说,设计一套排列的编码和解码函数,把0-8的全排列和0-362879的整数一一对应。
int vis[362880], fact[9];
void init_lookup_table()[
    fact[0] = 1;
    for(int i = 1; i < 9; i++) fact[i] = fact[i-1] * i;
}
int try_to_insert(int s){
    int code = 0;
    for(int i 0; i < 9; i++){
        int cnt = 0;
        for(int j = i+1; j < 9; j++) if(st[s][j] < st[s][i]) cnt++;
        code += fact[8-i] * cnt;
    }
    if(vis[code]) return 0;
    return vis[code] = 1;
}

编码解码法优点在于时间效率高,但是适用范围不大,因为如果隐式图的总结点数非常高,那编码数组还是开不下。

  • 方法二:哈希。设计一个哈希函数h(x),然后将任意结点x映射到某个给定范围[0,M-1]的整数即可。其中M是程序员根据内存大小自选的。在理想情况下,只需要开一个大小为M的数组就可以完成判重。但是此时往往会有不同点的哈希值相同,因此需要把哈希值相同的状态组织成链表。
const int hashsize = 1000003;
int head[hashsize], next[maxstate];
void init_lookup_table(){
    memset(head, 0, sizeof(head));
}
int hash(State& s){
    int v = 0;
    for(int i = 0; i < 9; i++) v = v * 10 + s[i];
    return v % hashsize;
}
int try_to_insert(int s){
    int h = hash(st[s]);
    int u = head[h];
    while(u){
        if(memcmp(st[u], st[s]), sizeof(st[s])) == 0) return 0;
        u = next[u];
    }
    next[s] = head[h];
    head[h] = s;
    return 1;
}

哈希表执行效率高,适用范围广。除了BFS中的结点判重之外,还可以用到其他需要快速查找的地方。
在哈希表中,对效率起到关键作用的是哈希函数。如果哈希函数选取得当,几乎不会有结点的哈希值相同,且此时链表查找速度也较快;但如果严重冲突,哈希表会退化成少数几条常常的链表,查找速度非常缓慢。
前面的编码函数就可以看做一个完美的哈希函数。

  • 方法三:用STL中的集合t。把状态转化成9位十进制整数,就可以用set<int>判重。
set<int> vis;
void init_insert_table() { vis.clear(); }
int try_to_insert(int s){
    int v = 0;
    for(int i = 0; i < 0 ; i++) v = v* 10 + st[s][i];
    if(vis.count(v)) return 0;
    return 1;
}

集合是三种方法中效率最低的一种。

例题:倒水问题(UVa 10603)

有装满水的6升的杯子、空的3升杯子和1升杯子,三个杯子都没有刻度。在不使用其他道具的情况下,如何量出四升的水?
本题的任务是解决一般性问题:设3个杯子的容量分别是abc,最初只有第三个杯子装满了c升水,其他两个杯子为空。最少需要倒多少升水才能让某一个杯子中的水有d升呢?如果无法做到,就让某个杯子中的水是e升,e<d且尽量接近d

代码

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

struct Node{
    int v[3], dist;
    bool operator < (const Node& rhs) const{
        return dist > rhs.dist;
    }
}

const int maxn = 200 + 5;
int vis[maxn][maxn], cap[3], ans[maxn];

void update_ans(const Node& u){
    for(int i = 0; i < 3; i++){
        int d = u.v[i];
        if(ans[d] < 0 || u. dist < ans[d]) ans[d] = u.dist;
    }
}

void solve(int a, int b, int c, int d){
    cap[0] = a; cap[1] = b; cap[2] = c;
    memset(vis, 0, sizeof(vis));
    memset(ans, -1, sizeof(ans));
    priority_queue<Node> q;

    Node start;
    start.dist = 0;
    start.v[0] = 0; start.v[1] = 0; start.v[2] = c;
    q.push(start);

    vis[0][0] = 1;
    while(!q.empty()){
        Node u = q.top(); q.pop();
        update_ans(u);
        if(ans[d] >= 0) break;
        for(int i = 0; i < 3; i++)
            for(int j = 0; j < 3; j++) if(i != j){
                if(u.v[i] == 0 || u.v[j] == cap[j]) continue;
                int amount = min(cap[j], u.v[i] + u.v[j]) - u.v[j];
                Node u2;
                memcpy(&u2, &u, sizeof(u));
                u2.dist = u.dist + amount;
                u2.v[i] -= amount;
                u2.v[j] += amount;
                if(!vis[u2.v[0]][u2.v[1]]){
                    vis[u2.v[0]][u2.v[1]] = 1;
                    q.push(u2);
                }
            }
    }
    while(d >=  0){
        if(ans[d] >= 0){
            printf("%d %d\n", ans[d], d);
            return;
        }
        d--;
    ]
}

int main(){
    int T, a, b, c, d;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d%d%d", &a, &b, &c, &d);
        solve(a, b, c, d);
    }
    return 0;
}