局部搜尋

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

基礎[編輯]

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

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

做法[編輯]

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

(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})

步驟：

隨機噉設定啲變數嘅數值（隨機試一個可能嘅答案），例如設做
$x_{4}=0,x_{1}=x_{2}=x_{3}=1$
試下第 1 步產生嗰個答案係咪啱用；
$(1\lor 0\lor 0)\land (0\lor 0\lor 0)\land (0\lor 0\lor 0)=0$ （唔啱用）
如果啱用（研究者已經指定咗乜嘢算係啱用），將手上嗰個答案畀出嚟做最終答案；
如果唔啱用，就將其中一個變數「反轉」，例如變做
$x_{1}=x_{4}=0,x_{2}=x_{3}=1$ （ $x_{1}$ 「反轉」咗）
返去步驟 2，直至搵到一個啱用嘅答案或者時限過咗為止（對個答案做細幅度嘅修改然後再試）。