Jserv's blog

落花水面皆文章 -- 談踩地雷遊戲與 NP Complete

宋末的翁森在〈四時讀書樂〉這麼寫道：「好鳥枝頭亦朋友，落花水面皆文章。」，很多理論都是值得我們去探究的，但這些學問不見得一定要在厚厚的教科書或者論文集才讀得到，很多時候，玩遊戲反而是相當有效率的啟發，這話怎麼說？

剛剛閱讀 Uwe Hermann 的 blog [Minesweeper is NP-complete]，提到了 Richard Kaye 對於經典的踩地雷遊戲 (Minesweeper) 作分析，證明解題過程是 NP Complete 的，推薦您可先閱讀 Richard Kaye 在 [ASE meeting 2003 的簡報]。

首先，Richard 從踩地雷過程中的猜想，逐步引導我們試著從臆測中找到規則，又引入 logic gate 的觀念，最後從經典的 Travelling salesman 問題看 NP Complete，然後我們就身陷 "P=NP" 了 :-)

這份簡報實在是相見恨晚，電腦科學的演算法其實相當有趣，只是教科書與學程常常弄得很死板，讓學生喪失學習與思考的興趣，而經典的踩地雷遊戲竟然可以推導 NP Complete，實在有意思，的確，「落花水面皆文章」。
由 jserv 發表於 July 3, 2005 10:41 PM