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