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

陳昱璇(Yu-Xuan Chen)

指導教授 ： 林順喜

國立臺灣師範大學/理學院/資訊工程研究所/碩士(2006年)

摘要

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

關鍵字

全一問題 ； 最小全一問題 ； 支配集 ； 點燈遊戲

參考文獻

[2] 許介彥, 巴斯卡三角形的幾個性質, 科學教育, 275期, 頁20-28, 2004

[3] D. W. Bolton, “The multinomial theorem”, The Mathematical Gazette, Vol.52-382, pp.336-342, 1968

[5] G.. Kallos, “A generalization of Pascal's triangle using powers of base numbers”, Annales Mathematiques Blaise Pascal, Vol.13, pp.681-682, 2006

[6] H. Eriksson, K. Eriksson and J. Sjostrand, “Note on the lamp lighting problem”, Advances in Applied Mathematics, Vol.27, pp.357-366, 2001

[8] J. F. Putz, “The Pascal polytope: an extension of Pascal's triangle to N-dimensions”, The College Mathematics Journal, Vol.17-2, pp.144-155, 1986