1. 首頁 > 生活百科 > >

玩掃雷還有什么技巧？ 掃雷攻略( 二 )

資源網絡資源網


這個簡單的判斷還行，有時候會有一些比較隱晦的猜測 。
掃雷判斷問題
假設我們在掃雷過程中遇到這樣的模式，真的是欲哭無淚的事情 。如果你不知道怎么哭，你可以先準備好眼淚，邊肖會馬上告訴你為什么要哭 。。。從左邊開始，假設第一個空位有雷，那么第二個空位沒有雷，因為空位中間的1存在，第三個空位有雷，以此類推 。但是如果第一個空位沒有打雷，第二個空位有打雷，也是有道理的 。我要踩一個地雷，還有這么復雜的問題，至于嗎 。。。
別擔心，后面還有更復雜的事情 。這里的X和下面的*上是否有雷的情況總是一樣的，所以這個雷區就像一根傳輸信號的電線 。在掃雷地圖上，我們不僅可以制作這種簡單的信號傳輸線，還可以實現所有電子電路中邏輯門的操作 。[4,5]
非門電路
或門電路
這是兩個“簡單”的邏輯門，分別實現翻轉信號的“非”門和“或”運算兩個信號的“或”門 。在另一款知名沙盒游戲《《我的世界》》中，玩家也可以利用游戲中的素材——紅石(其實在此之前每年Windows 10操作系統的更新代碼都是以紅石命名的)來實現各種復雜的邏輯運算，還有一些玩家已經利用紅石在《我的世界》打造了一臺真正可操作的電腦 。。。
帶有完整寄存器、加法器和其他組件的紅石計算機[6]
算了，我無法想象掃雷會變成什么樣 。。。
很難判斷是否有解決辦法 。
找答案
回到文章的開頭，如果我們解決了一個掃雷問題，我們將很容易死去 。如果我們把這個問題交給計算機呢？遺憾的是，在正常情況下，計算機仍然無力解決掃雷問題 。。。
困難的
好在在我們平時玩的比較小的棋盤下，電腦也可以通過搜索得到答案 。
為了理解計算機在處理問題時的幾個困難程度，有必要先了解一個概念——多項式時間 。對于相同的算法，根據問題的大小，計算機一般需要不同的時間來計算 。用最直觀的例子，小明要去洗衣服 。他洗一件衣服需要2分鐘，洗五件衣服需要10分鐘，洗十件衣服需要20分鐘 。處理問題的時間隨著問題的規模線性變化，并且是線性多項式 ?，F在假設小明還得洗衣服，但是現在的衣服挺特別的 。他洗一件這種衣服需要2分鐘，但是洗五件的時間變成了32分鐘，洗十件的時間變成了1024分鐘 。這個時間是指數的而不是多項式的 。評價一個算法是一個非常重要的指標 。隨著問題規模的增大，如何增加計算時間 。
在計算機中，我們仍然認為多項式時間非?？?。如果把問題按照解決難度分類，P指的是多項式時間可以解決的問題，俗話說是可以快速解決的問題 。NP指的是一個計算起來不一定很快的問題，但是我們可以很快地檢查任何答案 。完全NP問題是一個比所有NP問題都難的NP問題 。雖然人們有一個奇妙的想法，他們總是認為計算會很快，他們應該能找到一種方法讓他快速計算，但這仍然是未知的 。。。[7]
不幸的是，解決掃雷游戲的解決方案恰好是一個NP完全問題——這是可以輕松驗證結果是否正確的問題中最困難的一個 。到目前為止，人們還沒有找到解決這類問題的多項式時間算法，通常只有指數甚至階乘搜索算法才能解決 。
顯示液晶數字的邏輯電路 。我們可以很容易地逐個嘗試，但反過來就很難了，尤其是邏輯電路很大的時候 。
掃雷游戲就是這樣一個難題，因為正如上一章所提到的，掃雷游戲可以看作是一個由邏輯資源網絡門進行運算的邏輯電路 。給定一個邏輯電路，當輸出結果已知時，能否確定每個輸入的值？這個問題叫做SAT問題，是世界上第一個被證明是NP完全的問題 。[8]這類問題很容易驗證 。你只需要把結果代入邏輯電路，就可以馬上知道是否符合要求 。但是反過來計算滿足結果的輸入是極其麻煩的 。
使用那些構造好的邏輯門來解決掃雷游戲的結果，就相當于解決了SAT問題 。[9]
掃雷也與滲透有關 。
預編碼
液體，圖片來自邁克爾·希靈堡的吉菲
事實上，我們發現玩掃雷游戲很難 。其實還有一個原因 。這個原因和物理學中的滲透有關 。
20世紀60年代，科學家[10]發現，當流體流經多孔介質時，空介質中的孔洞總是會被堵塞，有時會影響流體的流出 。奇怪的是，當這些多孔介質中隨機堵塞的孔隙比例逐漸增加到一定值時，開始時一直能夠流動的流體突然被完全堵塞 。當孔洞被隨機堵塞的概率發生變化時，液體的流速也會發生突變 。
這種現象被稱為預膨脹 。[11]

推薦閱讀