可以說幾百年沒去練過的東西了。但事實證明還挺有用的。

Meet in the Middle

以前一直沒想通過雙向搜索是怎么優化復雜度的。

例題 1

我稱其為合法子集計數問題。

雙向搜索就是把集合劈成兩半，兩邊分別枚舉子集，然后再記兩兩匹配的合法關系。

當后者可以快速統計時，雙向搜索就優化了復雜度。

例題 2

三種狀態：-1,1,0 在第一個、在第二個和根本不在。

合法子集計數，考慮劈成兩半。于是任意兩邊可以獲得 pair，然后就做完了。

A*

又名“啟發式搜索”。

A* 理論其實蠻有意思的。

\(f_i=g_i+h_i\)

其中 \(g_i\) 表示從啟示狀態到來的實際代價，\(h_i\) 表示到達終止狀態的估價函數。

要求 \(h_i\le d_i\)，\(d_i\) 是到底終止狀態的實際代價。

每次選取 \(f_i\) 最小的轉移。

如果 \(h_i\) 滿足三角不等式，則狀態不會重復。

當 \(h_i=0\) 時，相當于做 dij。

\(h_i\) 的相對關系越接近 \(d_i\) 的相對關系，效率越高。

ID

又名“迭代加深搜索”。

其實就是設定深度以后 dfs 代替 bfs。

常用于空間不足時或是答案大概率存在于較淺深度時。

IDA*

將迭代加深的深度用 A* 的估價函數表示。

相較于 A* 的優勢是更好寫，且答案層數小的時候飛快。

例題 1

一個顯然的想法是設 \(h_i\) 為當前局面每個點到目標的曼哈頓距離。

容易證明 \(h_i\le d_i\)。

例題 2

\(h_i\) 表示有幾個騎士該動。