Please use this identifier to cite or link to this item: http://rportal.lib.ntnu.edu.tw:80/handle/20.500.12235/106669
Title: Light Up遊戲一致性問題之研究
Authors: 林順喜
王怡人
Keywords: Light Up
一致性問題
Issue Date: 2007
Abstract:   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。
URI: http://etds.lib.ntnu.edu.tw/cgi-bin/gs32/gsweb.cgi?o=dstdcdr&s=%22http://etds.lib.ntnu.edu.tw/cgi-bin/gs32/gsweb.cgi?o=dstdcdr&s=id=%22GN0694470170%22.&%22.id.&
http://rportal.lib.ntnu.edu.tw:80/handle/20.500.12235/106669
Other Identifiers: GN0694470170
Appears in Collections:學位論文

Files in This Item:
File Description SizeFormat 
n069447017001.pdf370.19 kBAdobe PDFView/Open
n069447017002.pdf218.12 kBAdobe PDFView/Open
n069447017003.pdf244.08 kBAdobe PDFView/Open
n069447017004.pdf284.36 kBAdobe PDFView/Open
n069447017005.pdf88.62 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.