模擬退火方法04課件

1、二、模擬退火（Simulated Annealing ）方法（一）、組合優(yōu)化（二）、P/NP 問(wèn)題（三）、 Metropolis算法（五）、The Traveling Salesman Problem （六）、應(yīng)用 （四）、模擬退火（Simulated Annealing ）方法（七）掃雷掃成百萬(wàn)富翁（一）、組合優(yōu)化組合優(yōu)化（multivariate or combinatorial optimization）復(fù)蓋計(jì)算機(jī)和工程學(xué)科的一些核心課題。該領(lǐng)域的研究在于發(fā)展高效率地尋找具有若干獨(dú)立變量的多元函數(shù)極值的技巧。旅行推銷員這一經(jīng)典優(yōu)化問(wèn)題（尋找旅行推銷員依次不重復(fù)地訪問(wèn)N個(gè)城市的最短循環(huán)路線

2、）; 在例如為使包容在微型硅片上數(shù)十萬(wàn)計(jì)電路元件之間干攏達(dá)到極小的最優(yōu)排布復(fù)雜設(shè)計(jì)問(wèn)題。組合優(yōu)化就是尋求多元函數(shù)的極大或極小值，此函數(shù)稱作評(píng)估函數(shù)或目標(biāo)函數(shù)（cost function or objective function）。函數(shù)的形式取決于所研究的問(wèn)題，它所依賴的獨(dú)立變量與系統(tǒng)的自由度相對(duì)應(yīng)；函數(shù)值涉及系統(tǒng)組態(tài)的細(xì)節(jié)，構(gòu)成復(fù)雜系統(tǒng)某種意義下“質(zhì)量因數(shù)”的定量描述。為達(dá)到優(yōu)化的目的，要進(jìn)行大量的數(shù)字運(yùn)算。例如對(duì)旅行推銷員這類通稱的 NP完全問(wèn)題（non-deterministic Polynomial time complete Problems），實(shí)踐顯示，獲得精確解的計(jì)算工作量與參量

3、數(shù)目 N是指數(shù)關(guān)系。正因?yàn)槿绱?，?yán)格求解的努力只達(dá)到涉及N較小的規(guī)模。試探法（heuristic methods）已被用于解決 NP完全問(wèn)題，其計(jì)算工作量為 N的較小冪次的規(guī)模。 試探法有以下兩種基本方略： （1）分區(qū)攻克（divideandconquer）：把待研究的問(wèn)題分割成尺度較小而可以處理的子問(wèn)題，在解決了子問(wèn)題之后，再把它們組裝復(fù)原。這類方略適合于對(duì)子問(wèn)題已有強(qiáng)有力的解決手段，而子問(wèn)題之間原本關(guān)聯(lián)松散，把它們裝配起來(lái)對(duì)問(wèn)題的總體解決不會(huì)引入很大誤差的情況。 （2）迭代改善（iterative improvement）:（2）迭代改善（iterative improvement）: 以

4、系統(tǒng)的某一已知組態(tài)作為起始，用一種固定規(guī)則的局域重排操作對(duì)起始組態(tài)進(jìn)行試探：如果經(jīng)這一局域重排形成新組態(tài)的評(píng)估函數(shù)值相對(duì)原組態(tài)發(fā)生的是不利變化，則放棄這一重排企圖。這種試探一次次地在起始組態(tài)各個(gè)部位進(jìn)行，直到經(jīng)判斷發(fā)現(xiàn)某一次試探將使新組態(tài)的評(píng)估函數(shù)值相對(duì)原組態(tài)發(fā)生有利變化為止。起始組態(tài)接受這一有利的局域重排后形成一個(gè)新的組態(tài)，用它對(duì)系統(tǒng)作描述在“質(zhì)量因素”上有所改善。這個(gè)新組態(tài)又作為起始，對(duì)其進(jìn)行下一輪局域重排試探搜索。以求取得下一步改善。這種既定的選代手續(xù)一輪輪繼續(xù)下去，直到不能再有進(jìn)一步改善為止。 Estates但這種只接受評(píng)估函數(shù)值相對(duì)原組態(tài)發(fā)生有利變化新組態(tài)的單調(diào)手續(xù)，有容易使過(guò)程陷入

5、局域優(yōu)化陷院的缺點(diǎn)。（二）、P/NP 問(wèn)題誰(shuí)希望當(dāng)百萬(wàn)富翁？馬薩諸塞州坎布里奇的一家非贏利教育基金會(huì)Clay數(shù)學(xué)研究所懸賞百萬(wàn)美元，征求對(duì)7個(gè)至今尚未解決的著名數(shù)學(xué)問(wèn)題的解答。其中一個(gè)便是令人望而生畏的PNP問(wèn)題。盡管這個(gè)問(wèn)題難得出奇，但一位聰明的業(yè)余數(shù)學(xué)家或許能在“掃雷者”一種可在大多數(shù)電腦上玩的時(shí)髦游戲的協(xié)助下破解這個(gè)難題。我們說(shuō)這類問(wèn)題具有非確定性的多項(xiàng)式運(yùn)行時(shí)間，因而把它稱為NP類(non-deterministic Polynomial time complete Problems) 。 NP類與非P類不是一回事。對(duì)于一個(gè)問(wèn)題，如果你能夠在多項(xiàng)式時(shí)間內(nèi)核查某一推薦的解答是否正確，那么

6、這個(gè)問(wèn)題就屬于NP類。這個(gè)要求比在多項(xiàng)式時(shí)間內(nèi)真正找到答案的要求寬松得多（至少是似乎寬松得多）。解決NP問(wèn)題可能非常困難，但如果某人聲稱已經(jīng)解決了它，那么通常只需要幾秒鐘的時(shí)間就能核查他的答案是否正確。結(jié)果證明，許多NP問(wèn)題的運(yùn)行時(shí)間是等價(jià)的。具體地說(shuō)就是，對(duì)于某個(gè)NP問(wèn)題，如果它存在一種多項(xiàng)式時(shí)間解法，就意味著所有NP問(wèn)題都有多項(xiàng)式時(shí)間解法，我們就說(shuō)這個(gè)問(wèn)題是NP完備的。因而，如果你能夠在多項(xiàng)式時(shí)間內(nèi)解決一個(gè)NP完備問(wèn)題，你也就在多項(xiàng)式時(shí)間內(nèi)解決所有NP問(wèn)題。PNP問(wèn)題探討的就是P類與NP類問(wèn)題是否相同，盡管所有跡象都表明情況正好相反。這個(gè)問(wèn)題預(yù)期的答案應(yīng)該是否定的。但是，如果任何一個(gè)NP完

7、備問(wèn)題被證明具有一個(gè)多項(xiàng)式時(shí)間解答，那么NP問(wèn)題必定等價(jià)于P問(wèn)題。在我們引入了“掃雷者游戲自洽性問(wèn)題”（Mine sweeper Consistency Problem）后，前面所談的東西便與計(jì)算機(jī)游戲聯(lián)系起來(lái)了。這里我們面臨的挑戰(zhàn)不是要找出地雷，而是要確定該游戲的某一給定棋局是否在邏輯上無(wú)矛盾。例如，如果在游戲進(jìn)行的過(guò)程中你遇到了如下所述的棋局，那么你馬上就知道程序編制有錯(cuò)誤：無(wú)論把地雷怎么布置，也不可能同方格中顯示的數(shù)字相吻合。關(guān)鍵在于，如果對(duì)于某一給定棋局，你能夠在多項(xiàng)式時(shí)間內(nèi)解決掃雷者游戲自洽性問(wèn)題，那么你也就在多項(xiàng)式時(shí)間內(nèi)解決了等價(jià)布爾電路的SAT問(wèn)題。換言之，掃雷者游戲問(wèn)題是NP完

8、備的。在Metropolis Monte Carlo 模擬中（1）產(chǎn)生系統(tǒng)的一個(gè)組態(tài)（configuration）.(2)通過(guò)對(duì)已有組態(tài)的某種方式的操作來(lái)產(chǎn)生新組態(tài)。使用勢(shì)能函數(shù)可計(jì)算新組態(tài)的能量。如果新組態(tài)的能量比原組態(tài)的能量低，接受新組態(tài)。如果新組態(tài)的能量比原組態(tài)的能量高，則計(jì)算能量差的Boltzmann因子（三）、 Metropolis算法產(chǎn)生0，1之間的一個(gè)隨機(jī)數(shù)，如果此隨機(jī)數(shù)比能量差的Boltzmann因子大，則不接受新組態(tài)。否則則接受新組態(tài)。計(jì)算物理量的值（3） 重復(fù)（2） 直至N足夠大，計(jì)算物理量的值（四）、模擬退火（Simulated Annealing ）方法Simulate

9、d Annealing is based on the observation that a careful annealing of a physical system brings them closer to equilibrium than a quenching process. This is well known and widely used in the preparation of single crystals or in the manufacturing of telescope mirrors.由于快速降溫往往不能使系統(tǒng)達(dá)到穩(wěn)定的平衡態(tài)，而是停留在具有較高能量的亞穩(wěn)

10、態(tài)上；出現(xiàn)多晶、晶體缺陷、甚至沒(méi)有晶序的無(wú)定形態(tài)。因此實(shí)驗(yàn)中為了使系統(tǒng)達(dá)到或接近平衡態(tài)，要緩慢地降溫退火；使凝聚體在一系列遞降的溫度上有足夠的時(shí)間通過(guò)擴(kuò)散過(guò)程，在微觀尺度上進(jìn)行結(jié)構(gòu)合理調(diào)整。 在低溫下，具有不可忽略概率權(quán)重的系統(tǒng)組態(tài)都具有接近基態(tài)的能量，也就是較高的優(yōu)化“質(zhì)量因數(shù)”。它們?cè)谙到y(tǒng)所有可能的組態(tài)所構(gòu)成的整個(gè)相空間中只占極小的一部分。所以與溫度有等效意義的參量T的降低，意味著非零概率相空間的收縮。通過(guò)模擬退火手續(xù)，把對(duì)系統(tǒng)的組態(tài)抽樣凍結(jié)到相空間的這個(gè)有效部位，就大大地提高了數(shù)字模擬的效率。由上面的討論可知，模擬退火方法擴(kuò)展了試探優(yōu)化技術(shù)中的兩個(gè)重要方面。由上面的討論可知，模擬退火方法

11、擴(kuò)展了試探優(yōu)化技術(shù)中的兩個(gè)重要方面。首先模擬退火包含了分區(qū)戰(zhàn)勝的思想。溫度區(qū)分了系統(tǒng)重排的任務(wù)，那些使目標(biāo)函數(shù)值引起大變化的重排在高溫時(shí)出現(xiàn)，而那些使目標(biāo)函數(shù)值發(fā)生小變化的重排被推遲到低溫出現(xiàn)。這也是分區(qū)戰(zhàn)勝的一種類型：先在高溫進(jìn)行的重排，使系統(tǒng)在總體上初具凝聚特征; 而后在低溫進(jìn)行的重排，勾畫系統(tǒng)凝聚狀態(tài)的細(xì)節(jié)。Estates其次模擬退火包含了迭代改善，或者說(shuō)，迭代改善是模擬退火的一個(gè)特例。迭代改善方法本身的限制決定了它只能使系統(tǒng)達(dá)到局域最優(yōu)；而模擬退是有限溫度的選代改善，而且它使用 Metropolis法則代替迭代改善中的只改善（improve only），因而模擬退火法可使系統(tǒng)達(dá)到全局最

12、優(yōu)。 在對(duì)有限溫度下多體系統(tǒng)行為作數(shù)學(xué)描述時(shí)，Metropolis計(jì)算法則（Metropolis algorithm）很自然地成為把統(tǒng)計(jì)力學(xué)的宗旨實(shí)施于解決優(yōu)化問(wèn)題的有力工具。模擬退火（simulated annealing）是一種實(shí)現(xiàn)全局優(yōu)化的途徑，因其可與多體系統(tǒng)從高溫緩慢冷卻過(guò)程作形象的類比而得名。組合優(yōu)化和統(tǒng)計(jì)力學(xué)二者的中心思想有許多類似。這個(gè)統(tǒng)計(jì)力學(xué)思想啟示我們，對(duì)于一個(gè)即使沒(méi)有物理溫度意義的研究對(duì)象，在把系統(tǒng)的評(píng)估函數(shù)與能量作類比之后，也可以在其優(yōu)化的意義下進(jìn)一步引入等價(jià)溫度。組合優(yōu)化問(wèn)題就與統(tǒng)計(jì)力學(xué)中論證最可幾組態(tài)建立了深刻的理論聯(lián)系. 模擬退火首先在所謂旅行推銷員這一經(jīng)典優(yōu)化問(wèn)

13、題（尋找旅行推銷員依次不重復(fù)地訪問(wèn)N個(gè)城市的最短循環(huán)路線）的考核上顯示了它在處理特大型多變量系統(tǒng)問(wèn)題的能力。也在例如為使包容在微型硅片上數(shù)十萬(wàn)計(jì)電路元件之間干攏達(dá)到極小的最優(yōu)排布復(fù)雜設(shè)計(jì)問(wèn)題上得到成功的實(shí)際應(yīng)用。實(shí)踐表明，使用模擬退火方法解決旅行推銷員等問(wèn)題時(shí)，所用計(jì)算時(shí)間隨 N或N的較小冪次增長(zhǎng)。這種計(jì)算機(jī)時(shí)隨N較慢增長(zhǎng)和適用性強(qiáng)的優(yōu)點(diǎn)決定了模擬退火是一種具有廣泛應(yīng)用的優(yōu)化技術(shù)。使用模擬退火方法解決組合優(yōu)化問(wèn)題非常簡(jiǎn)單方便，而且能獲得全局最優(yōu)解。模擬退火這種全局優(yōu)化方法已滲透到許多領(lǐng)域，而且只要能提供以下四項(xiàng)基本要素，它可以用于任何系統(tǒng)：1）對(duì)系統(tǒng)的組態(tài)進(jìn)行簡(jiǎn)單的描述；2）使組態(tài)中元素進(jìn)行重

14、排的隨機(jī)生成函數(shù)，這些重排是提供給系統(tǒng)的“選擇”；3）目標(biāo)函數(shù)E（類似于能量），其極小化過(guò)程的目的；4）控制參數(shù)T（類似于溫度）和退火計(jì)劃。 （五）、The Traveling Salesman ProblemThe salesperson visits N cities with given positions (xi, yi), returning finally to his or her city of origin. Each city is to be visited once, and the route is to be made as short as possible. T

15、he problem belongs to a class known as NP-complete problems, whose computation time for an exact solution increase with N as exp(const. x N), becoming rapidly prohibitive in cost as N increases.As a problem in simulated annealing, the traveling salesman problem is handled as follows:1）對(duì)系統(tǒng)的組態(tài)進(jìn)行簡(jiǎn)單的描述；

16、2）使組態(tài)中元素進(jìn)行重排的隨機(jī)生成函數(shù)，這些重排是提供給系統(tǒng)的“選擇”；3）目標(biāo)函數(shù)E（類似于能量），其極小化過(guò)程的目的；4）控制參數(shù)T（類似于溫度）和退火計(jì)劃。iI+ i+6ii+1i+2i+3i+4i+5i+7i+6i+8ii+6i+5i+4i+3i+1i+2iii+8i+7i+8i+2i+3i+4i+7ii+1i+2i+3i+4i+5i+7i+6i+8i+8i+2i+3i+4i+7iI+i+1i+2i+3i+4I+ i+5i+7i+8I+iI+ i+8I+ i+2I+ i+3I+ i+4I+ i+7 (3)目標(biāo)函數(shù)(Objective function) E. in the simple

17、st form of the problem, E is taken just as the total length of journey.With the convention that point N+1 is identified with point 1. To illustrate the flexibility of the method, however we can add the following additional wrinkle: suppose that the salesman has an irrational fear of flying over the

18、Mississippi River.In that case, we would assign each city a parameter I, equal to +1 if it is east of the Mississippi, -1 if it is west, and take the Objective function to be.（4) Annealing schedule. This requires experimentation. We first generate some random rearrangementsChoosing a starting value

19、for the parameter T which is considerably larger than the largest E normally encountered, we proceed downward in multiplicative steps each amounting to a 10 percent decrease in T. we hold each new value of T constant for, say, 100N reconfigurations, or for 10N successful reconfigurations, whichever

20、comes first. Annealing scheduleLinear: T(t)=T0-cons*tExponential: T(t)=T0*cons*tAdaptive Annealing scheduleSet an initial T0.Perform m Monte Carlo step per ensemble member with the ensemble. We will call this MC sweep.Let j be the ensemble average after the jth MC sweep. If j j-1 then goto ii), else

21、 goto iv).Reset the temperature Tj+1 =cTj with c1.If the maximum number of MC sweep has not been reached then goto ii), else end of annealing run.（六）、應(yīng)用1. 一般函數(shù) f(x1, x2, xn-1, xn)的優(yōu)化2. 構(gòu)像優(yōu)化3. 與Monte Carlo的比較 4. 與一般優(yōu)化方法的比較局域極小(local minima)絕對(duì)極小(Global minimum)誰(shuí)希望當(dāng)百萬(wàn)富翁？馬薩諸塞州坎布里奇的一家非贏利教育基金會(huì)Clay數(shù)學(xué)研究所懸賞百

22、萬(wàn)美元，征求對(duì)7個(gè)至今尚未解決的著名數(shù)學(xué)問(wèn)題的解答。其中一個(gè)便是令人望而生畏的PNP問(wèn)題。盡管這個(gè)問(wèn)題難得出奇，但一位聰明的業(yè)余數(shù)學(xué)家或許能在“掃雷者”（Mine sweeper，一種可在大多數(shù)電腦上玩的時(shí)髦游戲）的協(xié)助下破解這個(gè)難題。（七）、掃雷掃成百萬(wàn)富翁 英國(guó)伯明翰大學(xué)的RIChard Kaye最近在數(shù)學(xué)報(bào)導(dǎo)（Mathematical Intelligencer， 2000年春22卷第2期）雜志上發(fā)表了一篇文章，題為“掃雷者游戲是NP完備的”。在該文中他指出了掃雷者游戲與 PNP問(wèn)題之間的聯(lián)系。首先我們來(lái)看看“掃雷者”這個(gè)游戲是如何玩法的。開(kāi)始時(shí)計(jì)算機(jī)屏幕上顯示出一個(gè)空白方格網(wǎng)，其中一部

23、分方格埋有地雷。你的任務(wù)就是探出哪些方格中埋有地雷，但不要把它們弄爆。游戲的第一步是選擇方格網(wǎng)中的任一方格并把它挖開(kāi)。如果此方格下埋有地雷，那你真是太不走運(yùn)了，地雷將爆炸，你就輸了。然而，如果這個(gè)方格中沒(méi)有埋地雷，計(jì)算機(jī)就將在此方格中顯示一個(gè)數(shù)字，告訴你與它相鄰的8個(gè)方格中埋有多少地雷。然后，如果你推斷出某一方格中有顆地雷，你就在該方格中插L一面小旗作為標(biāo)志。只要探出了方格網(wǎng)中埋藏的全部地雷，你就贏了?，F(xiàn)在我們回到PNP這個(gè)難題上。讀者應(yīng)當(dāng)記得，算法就是在計(jì)算機(jī)L按步就班地運(yùn)行下去以解決一個(gè)問(wèn)題的程序。計(jì)算數(shù)學(xué)的中心問(wèn)題之一是，一個(gè)算法解決某一給定問(wèn)題的效率有多高？換言之，運(yùn)行時(shí)間即得出答案所

24、需要的計(jì)算次數(shù)是如伺隨初始數(shù)據(jù)而變的？從這一角度來(lái)看計(jì)算問(wèn)題主要可分為兩類，一是P類（P代表多項(xiàng)式時(shí)間），一是非P類。使用一個(gè)算法來(lái)解某一問(wèn)題時(shí)，如果計(jì)算機(jī)所需要的運(yùn)行時(shí)間的增長(zhǎng)速度不高于確定該問(wèn)題初始數(shù)據(jù)所需要的符號(hào)數(shù)目的某一固定次冪，則這個(gè)問(wèn)題就屬于P類。如果一個(gè)問(wèn)題不可能用這種方式求解，那它就屬于非P類。P類問(wèn)題可以用計(jì)算機(jī)高效求解，而非P類問(wèn)題則沒(méi)有實(shí)際可行的解法，因?yàn)椴还苡檬裁此惴▉?lái)解這類問(wèn)題，得出解答所需要的時(shí)間都會(huì)長(zhǎng)得無(wú)法忍受。 對(duì)于一個(gè)問(wèn)題，你只要找到一個(gè)算法能在多項(xiàng)式時(shí)間內(nèi)解決它，那這問(wèn)題就屬于P類。例如，把一組數(shù)字按由小到大或由大到小的次序排列是一個(gè)P類問(wèn)題，因此，商業(yè)數(shù)據(jù)

25、庫(kù)程序可以高效地解決非常多的一批數(shù)字的排序問(wèn)題。相反，旅行推銷員問(wèn)題找出推銷員走遍其推銷路線b所有城市的最短路徑則已被公認(rèn)為非P問(wèn)題。不過(guò)這一點(diǎn)尚未被證明。找出某一整數(shù)的素因子也被認(rèn)為是一個(gè)非P問(wèn)題，但這一點(diǎn)也還沒(méi)有得到證明。 為何證明某一問(wèn)題屬非P類如此之難？這是因?yàn)槟悴荒芡ㄟ^(guò)分析某一特定的算法來(lái)證明它。你必須考慮所有可能的算法，并證明沒(méi)有一個(gè)算法能夠在多項(xiàng)式時(shí)間內(nèi)解決這個(gè)問(wèn)題。這是一件令人非常傷腦筋的任務(wù)。已經(jīng)得到的最好結(jié)果就是證明了一大類可能的非P問(wèn)題全都屬于同一級(jí)別：如果其中任何一個(gè)問(wèn)題能在多項(xiàng)式時(shí)間內(nèi)解決，那么其余所有問(wèn)題也都能在多項(xiàng)式時(shí)間內(nèi)解決。我們說(shuō)這類問(wèn)題具有非確定性的多項(xiàng)式運(yùn)

26、行時(shí)間，因而把它稱為NP類。 NP類與非P類不是一回事。對(duì)于一個(gè)問(wèn)題，如果你能夠在多項(xiàng)式時(shí)間內(nèi)核查某一推薦的解答是否正確，那么這個(gè)問(wèn)題就屬于NP類。這個(gè)要求比在多項(xiàng)式時(shí)間內(nèi)真正找到答案的要求寬松得多（至少是似乎寬松得多）。我喜愛(ài)的一個(gè)例子是拼板游戲。解決拼板問(wèn)題可能非常困難，但如果某人聲稱已經(jīng)解決了它，那么通常只需要幾秒鐘的時(shí)間就能核查他的答案是否正確。只要看看每塊拼板，檢查它能否同相鄰拼板合在一起就行了。完成這一檢查所需時(shí)間大致與拼板的數(shù)目成正比，因此檢查可在多項(xiàng)式時(shí)間內(nèi)完成。但是你無(wú)法在多項(xiàng)式時(shí)間內(nèi)構(gòu)造出拼板。如果你想通過(guò)嘗試所有可能的解法并逐一檢查每一個(gè)解法來(lái)解決這個(gè)問(wèn)題，那么將需要極其

27、大量的運(yùn)行時(shí)間，岡為潛在解法的個(gè)數(shù)的增長(zhǎng)速度比拼塊數(shù)目的任一次冪的增長(zhǎng)速度要快得多。 結(jié)果證明，許多NP問(wèn)題的運(yùn)行時(shí)間是等價(jià)的。具體地說(shuō)就是，對(duì)于某個(gè)NP問(wèn)題，如果它存在一種多項(xiàng)式時(shí)間解法，就意味著所有NP問(wèn)題都有多項(xiàng)式時(shí)間解法，我們就說(shuō)這個(gè)問(wèn)題是NP完備的。因而，如果你能夠在多項(xiàng)義時(shí)間內(nèi)解決一個(gè)NP完備問(wèn)題，你也就在多項(xiàng)式時(shí)間內(nèi)解決r所有NP問(wèn)題。PNP問(wèn)題探討的就是P類與NP類問(wèn)題是否相同，盡管所有跡象都表明情況正好相反。這個(gè)問(wèn)題預(yù)期的答案應(yīng)該是否定的。但是，如果任何一個(gè)NP完備問(wèn)題被證明具有一個(gè)多項(xiàng)式時(shí)間解答，那么NP問(wèn)題必定等價(jià)于P問(wèn)題。已知許多問(wèn)題是NP完備的。最簡(jiǎn)單的問(wèn)題之一稱為S

28、AT問(wèn)題，它涉及所謂布爾電路。這類電路由名叫與” “（AND）、“或”（OR）及“非”（NOT）之類的邏輯門構(gòu)成。電路的輸入為“久叮）或“假”（F）。每個(gè)門按規(guī)定的方式把輸入組合起來(lái)，得出該組合的結(jié)果作為邏輯門的輸出。例如，非門把T輸入變?yōu)镕輸出，而把F輸入變?yōu)門輸出?！癝AT問(wèn)題”問(wèn)的是，對(duì)于某一給定的布爾電路，是否可以選擇一組輸入，使該電路產(chǎn)生的輸出為T。對(duì)于較簡(jiǎn)單的電路，這個(gè)問(wèn)題純屬幾戲，不費(fèi)吹灰之力就能解決，但當(dāng)電路中有大量的門和輸入時(shí)，這個(gè)問(wèn)題就變得異常棘手了。在我們引入了“掃雷者游戲自洽性問(wèn)題”（Mine sweeper Consistency Problem）后，前面所談的東西便與計(jì)算機(jī)游戲聯(lián)系起來(lái)了。這里我們面臨的挑戰(zhàn)不是要找出地雷，而是要確定該游戲的某一給定棋局是否在邏輯上無(wú)矛盾。