張進(jìn)興

組合搜索算法關(guān)注于解決NP難題，而一直以來NP難題總體上被看作是無法解決的，但實(shí)際中一些NP難問題是可以通過邏輯語言計(jì)算或推理得到有效解決的。組合搜索算法通過減少搜索空間的可行域和使用啟發(fā)式搜索方法搜索大的解空間進(jìn)行NP難題的求解。目前已經(jīng)有很多相關(guān)的數(shù)學(xué)模型，用以表達(dá)和解決組合優(yōu)化問題，如約束滿足性問題（CSP， the Constraint Satisfaction Problem）和命題可滿足性問題（SAT， the Propositional Satisfiability problem）。本書詳細(xì)地對能夠顯著提高約束求解器性能的組合搜索、產(chǎn)生與探究有意義的信息進(jìn)行了闡釋，即冗余約束、啟發(fā)式提示、性能測量及搜索過程等，對信息共享及性能共享兩種情況結(jié)合實(shí)例進(jìn)行了詳實(shí)地介紹。

全書由8章組成：1.導(dǎo)論。本章介紹了組合搜索的發(fā)展情況，解釋了幾個(gè)組合搜索算法中的相關(guān)術(shù)語，給出了本書的整體結(jié)構(gòu)，提出了知識共享與性能共享概念；2.增強(qiáng)分布式約束網(wǎng)絡(luò)。本章詳細(xì)地闡釋了組合風(fēng)險(xiǎn)中的隨機(jī)風(fēng)險(xiǎn)選擇問題，介紹了分布式CSP算法與知識共享的競爭、合作對于提高現(xiàn)有的分布式搜索技術(shù)的影響，討論了該方法的實(shí)現(xiàn)原理及過程；3.可滿足性并行樹搜索。介紹了組合搜索在并行命題可滿足性問題中的重要應(yīng)用，詳細(xì)地闡述了ManySAT算法原理，介紹了其知識共享概念，及分布式CSP算法基礎(chǔ)上建立的并行組合搜索算法；4.可滿足性并行局部搜索。本章討論了SAT中的并行局部搜索算法，概述了有效地局部搜索算法原理及特點(diǎn)，最后提出了幾個(gè)能夠提高局部搜索算法性能的聚類策略；5.學(xué)習(xí)變量間依賴關(guān)系。討論了變量功能依賴關(guān)系中弱依賴關(guān)系的簡化形式，介紹了依賴關(guān)系的原理性知識及相關(guān)工作，并給出了實(shí)例進(jìn)行詳細(xì)地分析；6.連續(xù)搜索。本章首先提出了連續(xù)搜索方法，隨后介紹了其兩種工作模式：開發(fā)模式和探索模式，闡述了兩種模式的工作原理及應(yīng)用，最后闡釋了連續(xù)搜索方法能夠自主地搜索系統(tǒng)性能并分析其性能以逐漸糾正其搜索策略；7.自主搜索。本章介紹了利用知識共享機(jī)制，構(gòu)建了一個(gè)統(tǒng)一的自主搜索框架，給出了其搜索過程，提出了一種基于計(jì)算特性的分類的搜索過程及其準(zhǔn)則；8.結(jié)論與展望。

本書適合從事計(jì)算機(jī)科學(xué)、計(jì)算機(jī)工程和組合搜索及優(yōu)化等專業(yè)的研究生閱讀和學(xué)習(xí)，亦可以作為對組合優(yōu)化、約束問題及NP難問題研究感興趣的其他專業(yè)學(xué)生的參考書。對于在組合優(yōu)化及組合搜索研究領(lǐng)域的很多專業(yè)人士和研究人員，本書也將提供較大的幫助。

（中國科學(xué)院空間科學(xué)與應(yīng)用研究中心）endprint