(54.224.247.42) 您好!臺灣時間:2018/10/19 05:53
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
本論文永久網址: 
line
研究生:王怡人
論文名稱:LightUp遊戲一致性問題之研究
論文名稱(外文):On the study of light up consistency problem
指導教授:林順喜林順喜引用關係
學位類別:碩士
校院名稱:國立臺灣師範大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文出版年:2007
畢業學年度:95
語文別:中文
論文頁數:39
中文關鍵詞:Light Up一致性問題
相關次數:
  • 被引用被引用:0
  • 點閱點閱:359
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
  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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔