全一問題的改良演算法研究

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)的時間即可找出一組解答。