【每日算法】使用「雙向 BFS」解決搜尋空間爆炸問題（附啟發式搜尋 AStar 算法）

題目描述

這是 LeetCode 上的 127. 單詞接龍，難度為困難。

Tag : 「雙向 BFS」

字典 wordList 中從單詞 beginWord 和 endWord 的轉換序列是一個按下述規格形成的序列：

序列中第一個單詞是 beginWord 。
序列中最後一個單詞是 endWord 。
每次轉換隻能改變一個字母。
轉換過程中的中間單詞必須是字典 wordList 中的單詞。

給你兩個單詞 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 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord、endWord 和 wordList[i] 由小寫英文字母組成
beginWord != endWord
wordList 中的所有字元串互不相同

基本分析

根據題意，每次隻能替換一個字元，且每次産生的新單詞必須在

wordList

出現過。

一個樸素的實作方法是，使用 BFS 的方式求解。

從

beginWord

出發，枚舉所有替換一個字元的方案，如果方案存在于

wordList

中，則加入隊列中，這樣隊列中就存在所有替換次數為的單詞。然後從隊列中取出元素，繼續這個過程，直到遇到

endWord

或者隊列為空為止。

同時為了「防止重複枚舉到某個中間結果」和「記錄每個中間結果是經過多少次轉換而來」，我們需要建立一個「哈希表」進行記錄。

哈希表的 KV 形式為

{ 單詞 : 由多少次轉換得到 }

。

當枚舉到新單詞

str

時，需要先檢查是否已經存在與「哈希表」中，如果不存在則更新「哈希表」并将新單詞放入隊列中。

這樣的做法可以確定「枚舉到所有由

beginWord

到

endWord

的轉換路徑」，并且由

beginWord

到

endWord

的「最短轉換路徑」必然會最先被枚舉到。

雙向 BFS

經過分析，BFS 确實可以做，但本題的資料範圍較大：

1 <= beginWord.length <= 10

樸素的 BFS 可能會帶來「搜尋空間爆炸」的情況。

想象一下，如果我們的

wordList

足夠豐富（包含了所有單詞），對于一個長度為的

beginWord

替換一次字元可以産生個新單詞（每個替換點可以替換另外個小寫字母），第一層就會産生個單詞；第二層會産生超過個新單詞 ...

随着層數的加深，這個數字的增速越快，這就是「搜尋空間爆炸」問題。

【每日算法】使用「雙向 BFS」解決搜尋空間爆炸問題（附啟發式搜尋 AStar 算法）

在樸素的 BFS 實作中，空間的瓶頸主要取決于搜尋空間中的最大寬度。

那麼有沒有辦法讓我們不使用這麼寬的搜尋空間，同時又能保證搜尋到目标結果呢？

「雙向 BFS」可以很好的解決這個問題：

同時從兩個方向開始搜尋，一旦搜尋到相同的值，意味着找到了一條聯通起點和終點的最短路徑。

「雙向 BFS」的基本實作思路如下：

建立「兩個隊列」分别用于兩個方向的搜尋；
建立「兩個哈希表」用于「解決相同節點重複搜尋」和「記錄轉換次數」；
為了盡可能讓兩個搜尋方向“平均”，每次從隊列中取值進行擴充時，先判斷哪個隊列容量較少；
如果在搜尋過程中「搜尋到對方搜尋過的節點」，說明找到了最短路徑。

「雙向 BFS」基本思路對應的僞代碼大緻如下：

d1、d2 為兩個方向的隊列
m1、m2 為兩個方向的哈希表，記錄每個節點距離起點的

// 隻有兩個隊列都不空，才有必要繼續往下搜尋
// 如果其中一個隊列空了，說明從某個方向搜到底都搜不到該方向的目标節點
while(!d1.isEmpty() && !d2.isEmpty()) {
    if (d1.size() < d2.size()) {
        update(d1, m1, m2);
    } else {
        update(d2, m2, m1);
    }
}

// update 為從隊列 d 中取出一個元素進行「一次完整擴充」的邏輯
void update(Deque d, Map cur, Map other) {}

回到本題，我們看看如何使用「雙向 BFS」進行求解。

估計不少同學是第一次接觸「雙向 BFS」，是以這次我寫了大量注釋。

建議大家帶着對「雙向 BFS」的基本了解去閱讀。

代碼：

class Solution {
    String s, e;
    Set<String> set = new HashSet<>();
    public int ladderLength(String _s, String _e, List<String> ws) {
        s = _s;
        e = _e;
        // 将所有 word 存入 set，如果目标單詞不在 set 中，說明無解
        for (String w : ws) set.add(w);
        if (!set.contains(e)) return 0;
        int ans = bfs();
        return ans == -1 ? 0 : ans + 1;
    }

    int bfs() {
        // d1 代表從起點 beginWord 開始搜尋（正向）
        // d2 代表從結尾 endWord 開始搜尋（反向）
        Deque<String> d1 = new ArrayDeque<>(), d2 = new ArrayDeque();

        /*
         * m1 和 m2 分别記錄兩個方向出現的單詞是經過多少次轉換而來
         * e.g.
         * m1 = {"abc":1} 代表 abc 由 beginWord 替換 1 次字元而來
         * m1 = {"xyz":3} 代表 xyz 由 endWord 替換 3 次字元而來
         */
        Map<String, Integer> m1 = new HashMap<>(), m2 = new HashMap<>();
        d1.add(s);
        m1.put(s, 0);
        d2.add(e);
        m2.put(e, 0);

        /*
         * 隻有兩個隊列都不空，才有必要繼續往下搜尋
         * 如果其中一個隊列空了，說明從某個方向搜到底都搜不到該方向的目标節點
         * e.g.
         * 例如，如果 d1 為空了，說明從 beginWord 搜尋到底都搜尋不到 endWord，反向搜尋也沒必要進行了
         */
        while (!d1.isEmpty() && !d2.isEmpty()) {
            int t = -1;
            // 為了讓兩個方向的搜尋盡可能平均，優先拓展隊列内元素少的方向
            if (d1.size() <= d2.size()) {
                t = update(d1, m1, m2);
            } else {
                t = update(d2, m2, m1);
            }
            if (t != -1) return t;
        }
        return -1;
    }

    // update 代表從 deque 中取出一個單詞進行擴充，
    // cur 為目前方向的距離字典；other 為另外一個方向的距離字典
    int update(Deque<String> deque, Map<String, Integer> cur, Map<String, Integer> other) {
        // 擷取目前需要擴充的原字元串
        String poll = deque.pollFirst();
        int n = poll.length();

        // 枚舉替換原字元串的哪個字元 i
        for (int i = 0; i < n; i++) {
            // 枚舉将 i 替換成哪個小寫字母
            for (int j = 0; j < 26; j++) {
                // 替換後的字元串
                String sub = poll.substring(0, i) + String.valueOf((char)('a' + j)) + poll.substring(i + 1);
                if (set.contains(sub)) {
                    // 如果該字元串在「目前方向」被記錄過（拓展過），跳過即可
                    if (cur.containsKey(sub)) continue;

                    // 如果該字元串在「另一方向」出現過，說明找到了聯通兩個方向的最短路
                    if (other.containsKey(sub)) {
                        return cur.get(poll) + 1 + other.get(sub);
                    } else {
                        // 否則加入 deque 隊列
                        deque.addLast(sub);
                        cur.put(sub, cur.get(poll) + 1);
                    }
                }
            }
        }
        return -1;
    }
}

時間複雜度：令 wordList 長度為， beginWord 字元串長度為。由于所有的搜尋結果必須都在 wordList 出現過，是以算上起點最多有節點，最壞情況下，所有節點都聯通，搜尋完整張圖複雜度為；從 beginWord 出發進行字元替換，替換時進行逐字元檢查，複雜度為。整體複雜度為
空間複雜度：同等空間大小。

總結

這本質其實是一個「所有邊權均為

」最短路問題：将

beginWord

和所有在

wordList

出現過的字元串看做是一個點。每一次轉換操作看作産生邊權為

的邊。問題求以

beginWord

為源點，以

endWord

為彙點的最短路徑。

借助這個題，我向你介紹了「雙向 BFS」，「雙向 BFS」可以有效解決「搜尋空間爆炸」問題。

對于那些搜尋節點随着層數增加呈倍數或指數增長的搜尋問題，可以使用「雙向 BFS」進行求解。

【補充】啟發式搜尋 AStar

可以直接根據本題規則來設計 A* 的「啟發式函數」。

比如對于兩個字元串

直接使用它們不同字元的數量來充當估值距離，我覺得是合适的。

因為不同字元數量的內插補點可以確定不會超過真實距離（是一個理論最小替換次數）。

注意：本題資料比較弱，用 A* 過了，但通常我們需要「確定有解」，A* 的啟發搜尋才會發揮真正價值。而本題，除非

endWord

本身就不在

wordList

中，其餘情況我們無法很好提前判斷「是否有解」。這時候 A* 将不能帶來「搜尋空間的優化」，效果不如「雙向 BFS」。

Java 代碼：

class Solution {
    class Node {
        String str;
        int val;
        Node (String _str, int _val) {
            str = _str;
            val = _val;
        }
    }
    String s, e;
    int INF = 0x3f3f3f3f;
    Set<String> set = new HashSet<>();
    public int ladderLength(String _s, String _e, List<String> ws) {
        s = _s;
        e = _e;
        for (String w : ws) set.add(w);
        if (!set.contains(e)) return 0;
        int ans = astar();
        return ans == -1 ? 0 : ans + 1;
    }
    int astar() {
        PriorityQueue<Node> q = new PriorityQueue<>((a,b)->a.val-b.val);
        Map<String, Integer> dist = new HashMap<>();
        dist.put(s, 0);
        q.add(new Node(s, f(s)));

        while (!q.isEmpty()) {
            Node poll = q.poll();
            String str = poll.str;
            int distance = dist.get(str);
            if (str.equals(e)) {
                break;
            }
            int n = str.length();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < 26; j++) {
                    String sub = str.substring(0, i) + String.valueOf((char)('a' + j)) + str.substring(i + 1);
                    if (!set.contains(sub)) continue;
                    if (!dist.containsKey(sub) || dist.get(sub) > distance + 1) {
                        dist.put(sub, distance + 1);
                        q.add(new Node(sub, dist.get(sub) + f(sub)));
                    }
                }
            }
        }
        return dist.containsKey(e) ? dist.get(e) : -1;
    }
    int f(String str) {
        if (str.length() != e.length()) return INF;
        int n = str.length();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += str.charAt(i) == e.charAt(i) ? 0 : 1;
        }
        return ans;
    }
}

Python 3 代碼：

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        class PriorityQueue:
            def __init__(self):
                self.queue = []
                self.explored = set()

            def __contains__(self, item):
                return item in self.explored

            def __add__(self, other):
                heapq.heappush(self.queue, other)
                self.explored.add(other[2])

            def __len__(self):
                return len(self.queue)

            def pop(self):
                return heapq.heappop(self.queue)

        def heuristic(curr, target):
            return sum(1 for a, b in zip(curr, target) if a != b)

        wordList = set(wordList)
        if endWord not in wordList:
            return 0
        front = PriorityQueue()
        front.__add__((1, 0, beginWord))
        while front:
            l, _, s = front.pop()
            if s == endWord:
                return l
            for i in range(len(s)):
                for c in string.ascii_lowercase:
                    t = s[:i] + c + s[i + 1:]
                    if t in wordList and t not in front:
                        front.__add__((l + 1, heuristic(t, endWord), t))
        return 0

最後

這是我們「刷穿 LeetCode」系列文章的第

No.127

篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先将所有不帶鎖的題目刷完。

【每日算法】使用「雙向 BFS」解決搜尋空間爆炸問題（附啟發式搜尋 AStar 算法）

題目描述

基本分析

雙向 BFS

總結

【補充】啟發式搜尋 AStar

最後

繼續閱讀

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

查找檔案中的字元串

第三章 Joomla!擴充開發--後端開發（續2）

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

express 搭建背景建構工程目錄結構

hdu7108哈希