局部搜尋

局部搜尋（粵拼：guk6 bou6 sau2 cam4；英文：local search）係一種數學最佳化技術，起始嗰陣隨機噉試一個可能嘅答案，個答案多數唔啱用，但係跟住個程式就對個答案做細幅度嘅修改然後再試，一路重複直到搵到個啱用嘅答案，或者過咗時限為止。呢種做法通常搵唔到「最佳」嘅答案，但係就可以响「可能答案數量好多」嘅情況下搵返個「有返咁上下好」嘅答案。

基礎

内文：數學最佳化

局部搜尋係數學最佳化嘅一種做法，能夠响特定嘅情況下將手上嗰個函數嘅 output 整到有咁大得咁大（最大化）或者有咁細得咁細（最小化）。

局部搜尋呢種做法，本質上就有不確定性响度：例如可能手上嗰條問題其實係有正確答案嘅，但係部電腦咁啱唔好彩撞唔中（撞中之前時間到）；又或者條問題實際上有多過一個答案，但係部電腦只係搵到其中一個。

做法

用布林可滿足度問題（SAT）做例子。用局部搜尋嚟解 SAT 問題，可以想像以下噉嘅步驟。而家想像要評估呢條布林表達式：

$(x_{1}\lor \neg x_{2}\lor \neg x_{3})\land (\neg x_{1}\lor \neg x_{3}\lor x_{4})\land (\neg x_{1}\lor \neg x_{2}\lor x_{4})$

步驟：

1. 隨機噉設定啲變數嘅數值（隨機試一個可能嘅答案），例如設做

   $x_{4}=0,x_{1}=x_{2}=x_{3}=1$

2. 試下第 1 步產生嗰個答案係咪啱用；

   $(1\lor 0\lor 0)\land (0\lor 0\lor 0)\land (0\lor 0\lor 0)=0$（唔啱用）

3. 如果啱用（研究者已經指定咗乜嘢算係啱用），將手上嗰個答案畀出嚟做最終答案；
4. 如果唔啱用，就將其中一個變數「反轉」，例如變做

   $x_{1}=x_{4}=0,x_{2}=x_{3}=1$（$x_{1}$「反轉」咗）

5. 返去步驟 2，直至搵到一個啱用嘅答案或者時限過咗為止（對個答案做細幅度嘅修改然後再試）。

有關實際應用上會用嘅局部搜尋做法，可以睇睇爬山演算法同埋模擬退火。

睇埋

• 窮舉搜尋
• 搜尋演算法