跳去內容

局部搜尋

出自維基百科,自由嘅百科全書

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

基礎

[編輯]

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

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

做法

[編輯]

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

步驟:

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

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

睇埋

[編輯]

引咗

[編輯]