Bidrectional search

发表于   |  

本文介绍双向搜索算法.

1.Bidrectional search

双向搜索是找源结点和目标结点间最短路径的图搜索算法. 它同时进行两个搜索 ：

  1. 前向搜索 : 从 源结点 到 目标结点 的搜索.
  2. 后向搜索 : 从 目标结点 向 源结点 搜索.

前向搜索和后向搜索会分别构造两颗树, 当两颗树的结点相遇时就会终止搜索. 或者, 当一侧的优先队列为空了, 搜索失败.

使用 Bidrectional search 可以缩短搜索的时间. 比如 : 对于一颗分支为 $b$ 的树, 从 源结点 到 目标结点 的距离为 $d$, 则通过 BFS/DFS 搜索的时间复杂度为 $O(b^d)$ . 如果使用 Bidrectional search 则 前向搜索 和 后向搜索 的时间复杂度分别为 $O(b^{d/2})$ , 总的时间复杂度则为 $O(b^{d/2} + b^{d/2})$ , 远比 $O(b^d)$ 小的多.

Bidrectional search的一个难点是如何保证前向搜索和后向搜索一定会相遇。 我们可知，对于广度优先搜索，一定是可以相遇的，那么对于其它搜索算法比如A*呢？(一些研究者在者方面做研究, 提高相遇的概率, 水平有限不在这里叙述)

leetcode上的126.Word Ladder II 就需要用双端breadth-first search来求解, 才能保证不出现TLE.

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {

        Set<String> wordSet = new HashSet<>(wordList);

        if(!wordSet.contains(endWord)) return new ArrayList<>();

        if(wordSet.contains(beginWord)) wordSet.remove(beginWord);
        wordSet.remove(endWord);

        Set<String> beginSet = new HashSet<>(), endSet = new HashSet<>(), visited = new HashSet<>();
        beginSet.add(beginWord);
        endSet.add(endWord);

        //只是存储后继, 而不是存储路径
        Map<String, List<String>> map = new HashMap<>();

        int flag = 0, bLen = 1, eLen = 1;
        boolean done = false;

        while(!beginSet.isEmpty() && !endSet.isEmpty()) {
            if(beginSet.size() > endSet.size()) {
                Set<String> temp = beginSet;
                beginSet = endSet;
                endSet = temp;

                flag++;
            }

            if(done) break;

            Set<String> nextLevel = new HashSet<>();
            for(String word : beginSet) {
                char[] wordToChar = word.toCharArray();

                for(int i = 0; i < word.length(); i++) {
                    char oldChar = wordToChar[i];

                    for(char c = 'a'; c <= 'z'; c++) {
                        wordToChar[i] = c;

                        String newWord = String.valueOf(wordToChar);

                        String key = flag % 2 == 0 ? word : newWord;
                        String val = flag % 2 == 0 ? newWord : word;

                        if(endSet.contains(newWord)) {
                            done = true;

                            List<String> t = map.getOrDefault(key, new ArrayList<>());
                            t.add(val);
                            map.put(key, t);
                        }

                        if(done || visited.contains(newWord) || !wordSet.contains(newWord)) continue;

                        List<String> t = map.getOrDefault(key, new ArrayList<>());
                        t.add(val);
                        map.put(key, t);

                        nextLevel.add(newWord);
                        // System.out.println(beginSet + "\t" + endSet);
                        // System.out.println(map);
                    }

                    wordToChar[i] = oldChar;
                }
            }
            visited.addAll(nextLevel);
            beginSet = nextLevel;
        }//while

        map.put("null", Arrays.asList(beginWord));

        List<List<String>> res = new ArrayList<>();

        generateList(res, new ArrayList<>(), "null", endWord, map);

        return res;
    }

    void generateList(List<List<String>> res, List<String> list, String startWord, String endWord, Map<String, List<String>> map) {

        if(startWord.equals(endWord)) {res.add(new ArrayList<>(list)); return;}

        for(String word : map.getOrDefault(startWord, new ArrayList<>())) {
            list.add(word);
            generateList(res, list, word, endWord, map);
            list.remove(word);
        }
    }
}