Please use this identifier to cite or link to this item: http://rportal.lib.ntnu.edu.tw:80/handle/20.500.12235/106667
Title: 全一問題的改良演算法研究
Authors: 林順喜
陳昱璇
Keywords: 全一問題
最小全一問題
支配集
點燈遊戲
Issue Date: 2007
Abstract: 全一問題(All-Ones Problem)是由Klaus Sutner於1988年提出。這個問題假設有一個n×m大小的棋盤狀盤面,當我們點其中一格”燈泡”時,與它上、下、左、右相鄰的鄰居包含自己的狀態會由亮變暗或是由暗變亮,而最終目標是找出一組點燈法則使得整個盤面由全亮變成全暗。提出這個問題的Sutner於1989年利用Cellular Automata證明了任意n×m的盤面都必存在至少一組解法,進而提出了最小全一問題(Minimum All-Ones Problem)並証明其為一NP-Complete問題。另外Lossers也利用線性代數證明了任意大小盤面都有解的事實,其解法的時間複雜度甚高,為Ο(n3×m3)。本校蔡明原學長與林順喜教授提出了一種搜尋演算法能夠有效率的找出較小盤面的解法,並已找出20×20以下所有盤面的解答。本論文中將提出一種更有效率的演算法能夠更快速的找出任意大小盤面的解法,只需Ο(n×m+n3)的時間即可找出一組解答。
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=%22GN0694470156%22.&%22.id.&
http://rportal.lib.ntnu.edu.tw:80/handle/20.500.12235/106667
Other Identifiers: GN0694470156
Appears in Collections:學位論文

Files in This Item:
File Description SizeFormat 
n069447015601.pdf189.91 kBAdobe PDFView/Open
n069447015602.pdf176.21 kBAdobe PDFView/Open
n069447015603.pdf333.81 kBAdobe PDFView/Open
n069447015604.pdf98.75 kBAdobe PDFView/Open
n069447015605.pdf173.5 kBAdobe PDFView/Open


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