Browsing by Author "Hu Shu-chiung"

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    2×n踩地雷一致性問題之研究
    (2006) 胡淑琼; Hu Shu-chiung
    踩地雷是微軟作業系統上非常流行的一套單人電腦遊戲，自從Richard Kaye在2000年證明了踩地雷問題是NP-complete之後，近年來有許多學者投入這方面的研究。Meredith Kadlac提出了一維的踩地雷遊戲，並証明了一維踩地雷一致性問題(One-dimensional Minesweeper Consistency Problem)是非常容易處理的，且可以用一個決定性的有限狀態機(DFA)來判斷一個一維踩地雷的盤面是否一致。我們將此一致性問題延伸至2×n踩地雷盤面上，2×n踩地雷是二維的，但其中一個維度被限定為2。我們發現這個問題也是可克服的，我們成功的設計了一個有限狀態機，其可在線性時間內解出2n踩地雷一致性問題，因此，我們證明了2×n踩地雷一致性問題的複雜度亦為P。