簡易檢索 / 詳目顯示

回結果列表
研究生： 王怡人
論文名稱： Light Up遊戲一致性問題之研究
指導教授： 林順喜
學位類別： 碩士
Master
系所名稱： 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年： 2007
畢業學年度： 95
語文別： 中文
論文頁數： 39
中文關鍵詞： Light Up 、一致性問題
論文種類： 學術論文
相關次數： 點閱：146  下載：7 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • Light Up（點燈遊戲）是一個從日本發跡並已推廣至世界各地，造成相當流行的一種“paper-and-pencil puzzles”類型的遊戲，在2005年時由Brandon McPhail證明了Light Up一致性問題 -- 「給定一個Light Up的盤面，判定此盤面是否存在合理的解？」的難度是NP-complete。目前探討本議題的相關論文並不多，因此在本論文中，首先提出了將盤面縮小至一維的盤面，並發現一維的Light Up盤面能夠在線性時間內以一個決定性的有限狀態機（DFA）判斷出盤面是否一致，即1×n Light Up一致性問題複雜度為P。

    　　接著我們將Light Up盤面限定為一個2×n的盤面，即一個二維的盤面但其中一個維度限制為2，發現這個問題同樣地能被克服。我們設計了一個有限狀態機，同樣能在線性時間內判斷出一個2×n Light Up盤面是否一致，即2×n Light Up一致性問題複雜度亦為P。

    摘要......................................................II Abstract.................................................III 第一章　緒論................................................1 第一節 前言.................................................1 第二節 問題定義.............................................3 第三節 文獻探討.............................................9 第四節 論文組織.............................................9 第二章　相關研究探討........................................10 第一節 Light Up 一致性問題..................................10 第二節 Light Up 一致性問題為NP-complete.....................11 第三節 1×n與2×n LCP........................................14 第三章　1×n 的Light Up一致性問題............................17 第一節 符號定義............................................17 第二節 1×n LCP之DFA........................................17 第四章　2×n 的Light Up一致性問題............................23 第一節 符號定義............................................23 第二節 2×n LCP之NFA狀態介紹.................................25 第三節 2×n LCP之NFA狀態轉換表...............................31 第四節 簡化2×n LCP之NFA狀態轉換表............................36 第五節 2×n LCP屬於P........................................36 第五章　結論...............................................38 第一節 結論................................................38 第二節 未來方向............................................38 參考著作...................................................40

    [1] M. A. Arbib, Theories of Abstract Automata, Prentice-Hall, Englewood Cliffs, N. J., 1969.
    [2] M. R. Garey and D. S. Johnson, Computers and Intractability, A Guide to Theory of NP-Completeness, W. H. Freeman and Co., San Francisco, 1979.
    [3] B. P. McPhail, “The complexity of puzzles: NP-completeness results for Nurikabe and Minesweeper,” Undergraduate Thesis, Reed College, 2003.
    [4] B. P. McPhail, “Light Up is NP-complete,” The Division of Mathematics and Natural Sciences, Technical report, Reed College, 2005.
    [5] M. L. Minsky, Computation-Finite and Infinite Machines, Prentice Hall, Englewood Cliffs, New Jersey, 1967.
    [6] M. Sipser, Introduction to the Theory of Computation, Second Edition, Course Technology, 2005.
    [7] S. Takahiro, The Complexities of Puzzles, Cross Sum, and their Another Solution Problems (ASP), Undergraduate Thesis, The University of Tokyo, 2001.
    [8] N. Ueda and T. Nagao, “NP-completeness results for NONOGRAM via parsimonious reductions,” Technical report, Tokyo Institute of Technology, 1996.
    [9] T. Yato, “On the NP-completeness of the Slither Link Puzzle,” In IPSJ SIGNotes ALgorithms, pages 25–32, 2000.
    [10] T. Yato, Complexity and Completeness of Finding Another Solution and its Application to Puzzles, Master’s thesis, The University of Tokyo, 2003.
    [11] The Light Up Puzzle website, http://www.puzzle-light-up.com/.
    [12] The Wikipedia website, http://en.wikipedia.org/wiki/Light_Up.

    QR CODE