算法搜索

隐式图搜索的概念与例子

字数统计: 2.4k字   |   阅读时长: 9分
, , ,

摘要: 隐式图搜索的概念，以单词接龙为例

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们首先介绍隐式图搜索的相关概念，然后解决一个非常经典的用 BFS 解决的隐式图搜索问题，用建图和不建图的方式均给出了解决方案。同时增加了一种减少无效转移的搜索方式：双向搜索。

隐式图搜索

在图算法中，隐式图可以理解为图的一种表示，其顶点和边在计算机内存中并不表示为显式的对象。而是从其他输入中通过算法来确定。

很多搜索问题并没有显式地给一张图，只是给了一些状态之间可能的转换关系等。这些关系可以理解为一组规则，用于定义任何指定顶点的所有邻居。比如一个棋盘局面是是个状态，状态的转移是棋盘上可鞥的走子方法形成的新局面。

这类问题的一个难点是意识到问题是一个图上的搜索问题，只是这个图是隐式图。当我们意识到了这是一个图搜索问题后，就有很多算法以及优化方法可以考虑了。

在实际处理的时候，可以建图，也可以不建图。如果建图的话，建图方式就很关键了，这决定了建出的图是否有很多无效状态。

能不建图的话肯定是不建图更好，可以节约时间和空间。不建图的话，顶点可以理解为某种状态，边可以理解为从一个状态向另一个状态的移动。

隐式图搜索的时间复杂度

状态数

状态数比较直接，就是隐式图中的节点数。与建图方式有关，不好的建图方式会造成很多无效的节点。

转移代价

从当前状态转移到相邻状态，就是在隐式图上从一个点向相邻节点连边，要找到所有相邻节点并判定是否还未选过。

如果是邻接矩阵，每次转移都要枚举所有点，先判定是否构成边、再判定是否未选过，一次转移的代价为 $O(N)$；

如果是邻接表，每次转移只需要判定相邻点是否未选过，一次转移的代价为摊销 $O(E/N)$。

因此总时间复杂度大致为 $O(到达状态数 \times 转移代价)$，因此优化方法主要有两条路：减少状态数、减少失败的边数。

隐式图搜索的优化

减少状态(节点)总数

例如 【搜索难题】力扣1036-有限BFS,二维离散化 题中的处理方式：基于二维离散化把对结果无影响的行和列去掉、基于提前退出的有限BFS，都可以理解为减少了状态总数。

减少失败转移次数

对于 BFS，双向BFS，可以理解为减少了失败转移的次数，优先级队列BFS也隐含了减少失败转移次数的思想，参考文章 优先级队列BFS，【搜索难题】力扣778-优先级队列BFS

对于 DFS，剪枝是最常见的减少无效转移次数的方法。

题目：127. 单词接龙

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> … -> sk：

  • 每一对相邻的单词只差一个字母。
  • 对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
  • sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

示例 1：
输入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
输出：5
解释：一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”, 返回它的长度 5。

示例 2：
输入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”]
输出：0
解释：endWord “cog” 不在字典中，所以无法进行转换。

提示：

1
2
3
4
5
6
7
1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord、endWord 和 wordList[i] 由小写英文字母组成
beginWord != endWord
wordList 中的所有字符串 互不相同

隐式图

本题的难点是想到是图的问题，因为乍一看好像是字符串的问题，细一看才发现是图的最短路问题。

能发现是图的问题：无向无权图上的最短路径，套 BFS 模板的基础思路就有了，之后再考虑怎么优化。

节点：beginWord，endWord，wordList 中的词，是图的节点，

边：两个词可以改变一个字母转换，构成一条边。无向边，无权重。

建图 + BFS

先建图：枚举所有节点对，检查是否只相差一个字符，如果是就在邻接表 g 中加双向边。同时判断是否为终点，如果是则标记终点 ed。时间复杂度 $O(N^{2}L)$。

建图后在无向无权图上 BFS，时间复杂度 $O(N+E)$。

总时间复杂度 $O(N^{2}L)$。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        if(wordList.empty()) return 0;
        int n = wordList.size();

        vector<int> d; // 到起点的距离, 同时 -1 表示未被访问过
        vector<vector<int> > g; // 邻接表
        d.assign(n + 1, -1);
        g.assign(n + 1, vector<int>());
        int ed = -1; // 终点, 可能取不到

        // 建图过程
        for(int i = 0; i < n; ++i)
        {
            for(int j = i + 1; j < n; ++j)
            {
                if(_check(wordList[i], wordList[j]))
                {
                    g[i].push_back(j);
                    g[j].push_back(i);
                }
            }
            if(_check(wordList[i], beginWord))
            {
                g[n].push_back(i); // n 是起点
                g[i].push_back(n);
            }
            if(wordList[i] == endWord)
                ed = i;
        }

        // BFS
        queue<int> q;
        q.push(n); // 起点
        d[n] = 0; // 与起点的距离
        while(!q.empty())
        {
            int u = q.front(); // 当前点
            q.pop();
            for(int v: g[u]) // 下一点
            {
                if(d[v] == -1) // 未访问过
                {
                    q.push(v);
                    d[v] = d[u] + 1;
                    if(v == ed)
                        return d[v] + 1;
                }
            }
        }
        return 0;
    }

private:
    bool _check(string& s1, string& s2)
    {
        int cnt = 0;
        for(int i = 0; i < (int)s1.size(); ++i)
            if(s1[i] != s2[i])
                ++cnt;
        return cnt == 1;
    }
};

优化1：不显式建图

不建邻接表，直接在 BFS 的每步枚举所有可行状态(节点)，若可以连边，且此前没选过，则将节点进队，并更新距离。

这样可以理解为邻接矩阵的BFS，每个枚举到的节点都要与所有其它节点判定一次，总时间复杂度 $O(N^{2}L)$ ，这是常数级的优化。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution_2 {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        if(wordList.empty()) return 0;
        int n = wordList.size();

        vector<int> d; // 到起点的距离
        d.assign(n + 1, -1);
        d[n] = 1;

        wordList.push_back(beginWord);

        // BFS
        queue<int> q;
        q.push(n); // 起点
        while(!q.empty())
        {
            int u = q.front(); // 当前点
            q.pop();
            for(int v = 0; v < n; ++v) // 下一点
            {
                if(d[v] == -1) // 未访问过
                {
                    if(_check(wordList[u], wordList[v]))
                    {
                        if(wordList[v] == endWord)
                            return d[u] + 1;
                        d[v] = d[u] + 1;
                        q.push(v);
                    }
                }
            }
        }
        return 0;
    }

private:
    bool _check(string& s1, string& s2)
    {
        int cnt = 0;
        for(int i = 0; i < (int)s1.size(); ++i)
            if(s1[i] != s2[i])
                ++cnt;
        return cnt == 1;
    }
};

优化2：双向 BFS

从起点 BFS 直至终点，最终会形成一棵树，类似与层序遍历。

对于无向图，从起点搜终点和从终点搜起点都会形成一颗树，形状可能会不一样。

如果两个方向的BFS都是随着层数加深，当前层节点数越来越多的结构的话，那么从起点和终点同时BFS，可以减少很多无效转移。

这个方法可以带来多少提升跟两个方向的树的形状有关系。如果两个方向的树都是随着深度加深越来越宽的结构，并且深度比较深的话，可以有明显的加速，但是时间复杂度还是难以分析。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution_3 {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        if(wordList.empty()) return 0;
        int n = wordList.size();

        vector<int> d; // 到起点的距离
        d.assign(n + 1, 0); // 双向BFS, 节点染色，<0 和 >0 是两种颜色

        wordList.push_back(beginWord);

        // BFS
        queue<int> q;
        d[n] = 1;
        q.push(n); // 起点

        // 双向 BFS -- 找到终点进队
        // 若没有点进队，则连接不到终点，退化成单向BFS
        for(int i = 0; i < n; ++i)
        {
            if(wordList[i] == endWord)
            {
                d[i] = -1; // 给终点染色
                q.push(i);
                break;
            }
        }

        while(!q.empty())
        {
            int u = q.front(); // 当前点
            q.pop();
            for(int v = 0; v <= n; ++v) // 下一点
            {
                if(_check(wordList[u], wordList[v]))
                {
                    if(d[v] == 0) // 未访问过
                    {
                        d[v] = (d[u] > 0 ? d[u] + 1 : d[u] - 1);
                        q.push(v);
                    }
                    else
                    {
                        if((d[u] ^ d[v]) < 0) // 异号，颜色不同
                            return abs(d[u]) + abs(d[v]);
                    }
                }
            }
        }
        return 0;
    }

private:
    bool _check(string& s1, string& s2)
    {
        int cnt = 0;
        for(int i = 0; i < (int)s1.size(); ++i)
            if(s1[i] != s2[i])
                ++cnt;
        return cnt == 1;
    }
};
Share