Light Up遊戲一致性問題之研究

dc.contributor 林順喜 zh_TW
dc.contributor.author 王怡人 zh_TW
dc.date.accessioned 2019-09-05T11:25:56Z
dc.date.available 2012-7-23
dc.date.available 2019-09-05T11:25:56Z
dc.date.issued 2007
dc.description.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。 zh_TW
dc.description.sponsorship 資訊工程學系 zh_TW
dc.identifier GN0694470170
dc.identifier.uri http://etds.lib.ntnu.edu.tw/cgi-bin/gs32/gsweb.cgi?o=dstdcdr&s=id=%22GN0694470170%22.&%22.id.&
dc.identifier.uri http://rportal.lib.ntnu.edu.tw:80/handle/20.500.12235/106669
dc.language 中文
dc.subject Light Up zh_TW
dc.subject 一致性問題 zh_TW
dc.title Light Up遊戲一致性問題之研究 zh_TW
Files
Original bundle
Now showing 1 - 5 of 5
No Thumbnail Available
Name:
n069447017001.pdf
Size:
370.19 KB
Format:
Adobe Portable Document Format
Description:
No Thumbnail Available
Name:
n069447017002.pdf
Size:
218.12 KB
Format:
Adobe Portable Document Format
Description:
No Thumbnail Available
Name:
n069447017003.pdf
Size:
244.08 KB
Format:
Adobe Portable Document Format
Description:
No Thumbnail Available
Name:
n069447017004.pdf
Size:
284.36 KB
Format:
Adobe Portable Document Format
Description:
No Thumbnail Available
Name:
n069447017005.pdf
Size:
88.63 KB
Format:
Adobe Portable Document Format
Description:
Collections