隐式图搜索的概念与例子

  |  

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

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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