1. 項(xiàng)目概述從單向BFS到雙向BFS的思維躍遷“字串變換”這個(gè)問題乍一看就是個(gè)典型的字符串搜索問題給你一個(gè)起始串A、一個(gè)目標(biāo)串B以及若干條形如abc-xyz的替換規(guī)則問能否在有限步內(nèi)將A變成B并求最少步數(shù)。很多人的第一反應(yīng)就是標(biāo)準(zhǔn)的BFS廣度優(yōu)先搜索從起點(diǎn)開始每一步應(yīng)用所有可能的規(guī)則生成新狀態(tài)直到找到目標(biāo)。這個(gè)思路完全正確也是解決此類問題的基石。然而當(dāng)我在AcWing上刷到這道題并看到它被歸入“算法提高課”和“雙向廣搜”專題時(shí)我就知道事情沒那么簡(jiǎn)單。果不其然用樸素的單向BFS一提交直接TLE超時(shí)。問題出在哪在于搜索空間會(huì)隨著步數(shù)呈指數(shù)級(jí)膨脹。假設(shè)每條規(guī)則平均能在當(dāng)前字符串中匹配到2個(gè)位置有6條規(guī)則那么每一步分支因子可能就是12。搜索10步狀態(tài)數(shù)就可能達(dá)到12^10這個(gè)天文數(shù)字單向BFS的隊(duì)列根本撐不住。這時(shí)“雙向廣搜”就登場(chǎng)了。它不是一個(gè)全新的算法而是對(duì)經(jīng)典BFS的一次精妙優(yōu)化。其核心思想是“兩頭堵”不僅從起點(diǎn)A開始正向搜索同時(shí)也從終點(diǎn)B開始反向搜索。兩邊的搜索“波浪”在中間某處相遇時(shí)路徑就找到了。這樣做能極大減少需要探索的狀態(tài)總數(shù)。為什么因?yàn)樗阉鳂涞墓?jié)點(diǎn)數(shù)量是隨著深度指數(shù)級(jí)增長(zhǎng)的。從起點(diǎn)和終點(diǎn)同時(shí)搜索相當(dāng)于將巨大的指數(shù)爆炸“攔腰截?cái)唷?。假設(shè)最優(yōu)解需要10步單向BFS需要探索深度為10的整棵樹而雙向BFS每邊只需要探索深度大約為5的樹兩棵深度為5的樹節(jié)點(diǎn)數(shù)之和遠(yuǎn)小于一棵深度為10的樹。這個(gè)優(yōu)化在狀態(tài)空間龐大的問題中效果是顛覆性的。接下來我們就從最基礎(chǔ)的單向BFS實(shí)現(xiàn)開始一步步拆解如何將其升級(jí)為高效的雙向BFS并搞定AcWing 190這道經(jīng)典題目。2. 核心思路與數(shù)據(jù)結(jié)構(gòu)選型2.1 問題建模與搜索狀態(tài)定義首先我們必須把問題抽象成一個(gè)清晰的圖論模型。在這個(gè)問題里節(jié)點(diǎn)State每一個(gè)可能的字符串就是一個(gè)狀態(tài)節(jié)點(diǎn)。邊Transition應(yīng)用一條可用的替換規(guī)則將當(dāng)前字符串變?yōu)橐粋€(gè)新字符串這個(gè)過程就構(gòu)成了一條有向邊。由于規(guī)則可以正向使用a-b表示把子串a(chǎn)替換為b在雙向BFS中也需要反向使用即把子串b替換回a所以邊實(shí)際上是雙向可通的我們把它視為無向邊來處理搜索。目標(biāo)找到從節(jié)點(diǎn)A到節(jié)點(diǎn)B的最短路徑最少應(yīng)用規(guī)則的次數(shù)。搜索的核心就是狀態(tài)擴(kuò)展。給定一個(gè)字符串s我們需要遍歷所有規(guī)則。對(duì)于每條規(guī)則(src, dst)我們需要在s中找出所有可以匹配src子串的位置并在每個(gè)位置進(jìn)行替換從而生成一系列新字符串。這個(gè)過程需要用到字符串的find函數(shù)并且要注意find的起始位置要不斷后移以找到所有匹配。2.2 單向BFS的框架與瓶頸我們先回顧單向BFS的標(biāo)準(zhǔn)寫法這是理解一切的基礎(chǔ)。#include iostream #include queue #include unordered_map #include string using namespace std; int bfs_one_way(string A, string B, vectorpairstring, string rules) { if (A B) return 0; queuestring q; unordered_mapstring, int dist; // 記錄到達(dá)每個(gè)狀態(tài)的最短步數(shù) q.push(A); dist[A] 0; while (!q.empty()) { string t q.front(); q.pop(); int current_dist dist[t]; // 擴(kuò)展當(dāng)前狀態(tài)t for (auto rule : rules) { string src rule.first, dst rule.second; // 在t中尋找所有src出現(xiàn)的位置 for (int pos t.find(src); pos ! -1; pos t.find(src, pos 1)) { // 生成新狀態(tài) string next t.substr(0, pos) dst t.substr(pos src.size()); // 如果新狀態(tài)超過長(zhǎng)度限制或已訪問過則跳過 if (next.size() B.size() || dist.count(next)) continue; if (next B) return current_dist 1; // 找到目標(biāo) dist[next] current_dist 1; q.push(next); } } } return -1; // 未找到 }這個(gè)框架清晰明了但它有一個(gè)致命弱點(diǎn)搜索是盲目的、對(duì)稱的。它從起點(diǎn)開始像水波一樣一圈圈向外擴(kuò)散直到碰到終點(diǎn)。在狀態(tài)空間巨大時(shí)這個(gè)“圓圈”會(huì)變得非常大消耗大量時(shí)間和內(nèi)存。這就是我們需要雙向BFS的根本原因。2.3 雙向BFS的工作原理與優(yōu)勢(shì)雙向BFS建立兩個(gè)搜索隊(duì)列和兩個(gè)距離字典q_a,dist_a: 從起點(diǎn)A開始的正向搜索。q_b,dist_b: 從終點(diǎn)B開始的反向搜索。每一輪迭代我們選擇當(dāng)前節(jié)點(diǎn)數(shù)較少的那一邊進(jìn)行擴(kuò)展這是一種常見的優(yōu)化旨在平衡兩邊的搜索進(jìn)度。擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)生成所有可能的下一個(gè)狀態(tài)。關(guān)鍵來了當(dāng)從一個(gè)方向生成的新狀態(tài)next在另一個(gè)方向的dist字典中已經(jīng)存在時(shí)說明兩條搜索路徑相遇了。此時(shí)總步數(shù)就是dist_a[current] 1 dist_b[next]。這個(gè)“相遇檢查”是雙向BFS的靈魂。它把尋找“到達(dá)終點(diǎn)”這個(gè)目標(biāo)轉(zhuǎn)化為了尋找“狀態(tài)在兩邊都被訪問”這個(gè)條件從而將搜索深度減半。數(shù)據(jù)結(jié)構(gòu)選型心得queuestring用于BFS是標(biāo)準(zhǔn)操作先進(jìn)先出保證最短路徑。unordered_mapstring, int這是本題性能的關(guān)鍵。我們需要快速查詢一個(gè)字符串狀態(tài)是否被訪問過以及其對(duì)應(yīng)的步數(shù)。unordered_map基于哈希表平均O(1)的查找和插入復(fù)雜度遠(yuǎn)優(yōu)于map的O(log n)。考慮到狀態(tài)數(shù)可能很多且字符串作為鍵哈希表的性能優(yōu)勢(shì)非常明顯。這里有一個(gè)重要細(xì)節(jié)在C中標(biāo)準(zhǔn)庫已經(jīng)為std::string提供了特化的哈希函數(shù)可以直接使用。如果你自己定義的結(jié)構(gòu)體作為鍵就需要手動(dòng)定義哈希函數(shù)。3. 雙向BFS的詳細(xì)實(shí)現(xiàn)與代碼解析理解了原理我們來看AcWing 190. 字串變換的具體實(shí)現(xiàn)。題目有幾個(gè)關(guān)鍵約束最多10步字符串長(zhǎng)度不超過20規(guī)則最多6條。這直接提示我們超過10步就算不可達(dá)雙向BFS每邊最多擴(kuò)展5層。3.1 算法流程與步驟拆解初始化讀入起始串A、目標(biāo)串B和所有規(guī)則。為正向和反向搜索分別初始化隊(duì)列和距離字典。將A加入q_adist_a[A]0將B加入q_bdist_b[B]0。循環(huán)擴(kuò)展只要兩個(gè)隊(duì)列都不空且總步數(shù)未超限例如10步就繼續(xù)。選擇擴(kuò)展方向比較q_a和q_b的當(dāng)前大小選擇節(jié)點(diǎn)數(shù)少的那一邊進(jìn)行擴(kuò)展。這是為了平衡兩邊的搜索廣度避免一邊搜得太深而另一邊還沒動(dòng)這是一種有效的啟發(fā)式優(yōu)化。單層擴(kuò)展對(duì)選中的隊(duì)列處理其當(dāng)前層的所有節(jié)點(diǎn)注意是“一層”而不是一個(gè)這保證了步數(shù)的準(zhǔn)確性。對(duì)于隊(duì)列中的每個(gè)節(jié)點(diǎn)t遍歷所有規(guī)則正向搜索用原規(guī)則反向搜索需要用反向規(guī)則。在字符串t中尋找規(guī)則源子串的所有出現(xiàn)位置。在每個(gè)位置進(jìn)行替換生成新字符串next。剪枝如果next長(zhǎng)度超過目標(biāo)串B的長(zhǎng)度題目隱含約束變換中字符串長(zhǎng)度可能增長(zhǎng)則跳過。相遇檢查如果next在對(duì)方的距離字典中存在則找到最短路徑。路徑長(zhǎng)度為dist_當(dāng)前[t] 1 dist_對(duì)方[next]。如果next在己方的距離字典中已存在說明已以更短步數(shù)訪問過跳過BFS特性保證第一次訪問是最短的。否則記錄距離將next加入當(dāng)前隊(duì)列。返回結(jié)果如果相遇返回步數(shù)如果循環(huán)結(jié)束仍未相遇返回不可達(dá)。3.2 核心代碼實(shí)現(xiàn)與注釋以下是結(jié)合了上述思路的C實(shí)現(xiàn)。代碼中包含了正向擴(kuò)展和反向擴(kuò)展的統(tǒng)一處理函數(shù)。#include iostream #include algorithm #include queue #include unordered_map #include string using namespace std; const int N 6; int n; // 規(guī)則數(shù) string A, B; string a[N], b[N]; // 規(guī)則數(shù)組a[i]-b[i] // 擴(kuò)展函數(shù)對(duì)隊(duì)列q進(jìn)行一層擴(kuò)展距離字典是da另一個(gè)距離字典是db // 使用規(guī)則數(shù)組ra和rb (對(duì)于正向擴(kuò)展raa, rbb; 對(duì)于反向擴(kuò)展rab, rba) int extend(queuestring q, unordered_mapstring, int da, unordered_mapstring, int db, string ra[], string rb[]) { // 取出當(dāng)前層的所有元素進(jìn)行擴(kuò)展 int d da[q.front()]; // 當(dāng)前層的距離 while (q.size() da[q.front()] d) { auto t q.front(); q.pop(); // 枚舉所有規(guī)則 for (int i 0; i n; i) { // 在字符串t中尋找所有可以應(yīng)用規(guī)則的位置 for (int pos 0; pos t.size(); pos) { // 檢查從pos開始是否能匹配規(guī)則源子串ra[i] if (t.substr(pos, ra[i].size()) ! ra[i]) continue; // 生成新狀態(tài) string next t.substr(0, pos) rb[i] t.substr(pos ra[i].size()); // 剪枝字符串長(zhǎng)度限制根據(jù)題意目標(biāo)串B的長(zhǎng)度是一個(gè)參考上限 if (next.size() B.size()) continue; // 如果新狀態(tài)在另一個(gè)方向已被訪問則相遇 if (db.count(next)) return da[t] 1 db[next]; // 如果新狀態(tài)在本方向已訪問跳過 if (da.count(next)) continue; // 記錄距離加入隊(duì)列 da[next] da[t] 1; q.push(next); } } } return -1; // 本次擴(kuò)展未相遇 } int bfs() { if (A B) return 0; queuestring qa, qb; unordered_mapstring, int da, db; qa.push(A); da[A] 0; qb.push(B); db[B] 0; int step 0; // 限制總步數(shù)題目要求最多10步 while (qa.size() qb.size() step 10) { int t; // 優(yōu)先擴(kuò)展節(jié)點(diǎn)數(shù)少的一邊以平衡搜索 if (qa.size() qb.size()) { t extend(qa, da, db, a, b); // 正向擴(kuò)展 } else { t extend(qb, db, da, b, a); // 反向擴(kuò)展注意參數(shù)順序 } if (t ! -1) return t; // 相遇則返回總步數(shù) step; } return -1; } int main() { cin A B; while (cin a[n] b[n]) n; int ans bfs(); if (ans -1) puts(NO ANSWER!); else cout ans endl; return 0; }3.3 關(guān)鍵細(xì)節(jié)與避坑指南一層擴(kuò)展 vs 單個(gè)節(jié)點(diǎn)擴(kuò)展extend函數(shù)中的while循環(huán)da[q.front()] d是精髓。它保證了每次調(diào)用只擴(kuò)展當(dāng)前距離的所有節(jié)點(diǎn)即“一層”。這是計(jì)算正確步數(shù)的基礎(chǔ)。如果改成每次只彈出一個(gè)節(jié)點(diǎn)就返回步數(shù)邏輯會(huì)混亂。規(guī)則的方向性在extend函數(shù)中參數(shù)ra[]和rb[]代表本次擴(kuò)展所使用的規(guī)則。對(duì)于從A出發(fā)的正向擴(kuò)展規(guī)則是a-b所以傳入a, b。對(duì)于從B出發(fā)的反向擴(kuò)展規(guī)則應(yīng)該是b-a即反向替換所以傳入b, a。這個(gè)對(duì)應(yīng)關(guān)系千萬不能錯(cuò)。相遇判斷的邏輯if (db.count(next)) return da[t] 1 db[next];這行代碼是雙向BFS的核心。da[t]是當(dāng)前狀態(tài)t在己方的步數(shù)1是走到新狀態(tài)next的這一步db[next]是next狀態(tài)在對(duì)方早已被訪問時(shí)的步數(shù)。三者之和就是總路徑長(zhǎng)。剪枝優(yōu)化if (next.size() B.size()) continue;這是一個(gè)非常有效的可行性剪枝。因?yàn)槲覀兊哪繕?biāo)串是B如果變換過程中產(chǎn)生的字符串長(zhǎng)度已經(jīng)超過了B的長(zhǎng)度那么它無論如何也不可能通過縮短變換變成B規(guī)則是替換可能變長(zhǎng)也可能變短但題目數(shù)據(jù)中通常無意義的增長(zhǎng)會(huì)導(dǎo)致搜索爆炸。這是一個(gè)基于題目特征的優(yōu)化。步數(shù)限制題目要求最多10步所以在主循環(huán)中加入了step 10的條件。注意這里的step可以理解為兩邊擴(kuò)展的“輪數(shù)”的一個(gè)上界估算更精確的約束需要在擴(kuò)展函數(shù)內(nèi)部判斷da[t]或db[t]是否超過5。4. 性能對(duì)比與擴(kuò)展思考為了直觀感受雙向BFS的威力我們可以做一個(gè)簡(jiǎn)單的理論對(duì)比。假設(shè)每個(gè)狀態(tài)平均有b個(gè)分支分支因子最短路徑長(zhǎng)度為d。單向BFS需要探索的節(jié)點(diǎn)總數(shù)約為O(b^d)。當(dāng)d10,b6時(shí)這個(gè)數(shù)字是6^10約6000萬實(shí)際由于字符串匹配和剪枝會(huì)少很多但依然龐大。雙向BFS每邊只需要探索深度約為d/2。需要探索的節(jié)點(diǎn)總數(shù)約為O(2 * b^(d/2))。同樣條件下約為2 * 6^5 2 * 7776 ≈ 15552。兩者相差了四個(gè)數(shù)量級(jí)這就是為什么單向BFS超時(shí)而雙向BFS能輕松通過的原因。關(guān)于unordered_map的進(jìn)一步優(yōu)化 在極端情況下字符串?dāng)?shù)量很多unordered_map的哈希沖突可能會(huì)影響性能。一個(gè)進(jìn)階優(yōu)化是使用雙端隊(duì)列deque配合自定義哈?；蛘呤褂瞄_放尋址法的哈希數(shù)組來模擬dist字典。但對(duì)于本題的數(shù)據(jù)范圍unordered_map已經(jīng)完全足夠。這里分享一個(gè)心得在競(jìng)賽中unordered_map的默認(rèn)哈希函數(shù)對(duì)于字符串有時(shí)可能不夠快如果遇到卡?？梢試L試傳入自定義哈希函數(shù)例如使用std::hashstd::string_view或者簡(jiǎn)單的BKDR哈希。struct StringHash { size_t operator()(const string s) const { size_t hash 0; for (char c : s) { hash hash * 131 c; // BKDR哈希常數(shù) } return hash; } }; // 使用unordered_mapstring, int, StringHash da, db;雙向BFS的適用場(chǎng)景 并不是所有BFS問題都適合雙向。它適用于知道明確的起點(diǎn)和終點(diǎn)。狀態(tài)空間巨大單向搜索容易超時(shí)或超內(nèi)存。狀態(tài)轉(zhuǎn)移是可逆的或者可以定義明確的反向轉(zhuǎn)移規(guī)則如本題。 常見的應(yīng)用場(chǎng)景包括八數(shù)碼問題如果可解、單詞接龍、某些狀態(tài)壓縮的最短路問題。最后這道題給我的最大啟示是優(yōu)化算法有時(shí)不是去發(fā)明新東西而是改變看待問題的角度。從起點(diǎn)單向搜索到起點(diǎn)終點(diǎn)雙向?qū)λ堰@個(gè)思維的轉(zhuǎn)變帶來的性能提升是質(zhì)的飛躍。在遇到搜索“爆炸”的問題時(shí)不妨多問一句“終點(diǎn)明確嗎能反向搜嗎”