这是一项作业。我必须使用以下回溯描述来设计和点亮游戏。
游戏由5 x 5的网格灯组成;游戏开始时,其中的一组指示灯(随机或一组已存储的拼图图案中的一个)会打开。按下其中一个灯将打开和关闭它旁边的四个灯。(对角邻居不会受到影响。)该游戏提供了一个难题:给定一些初始配置,其中一些指示灯点亮,而另一些指示灯熄灭,目标是关闭所有指示灯,最好是尽可能少地按下按钮。
我的方法是从1转到25,并检查所有灯是否熄灭。如果没有,那么我将检查1到24,依此类推,直到达到1或找到解决方案。否,如果没有解决方案,那么我将从2开始到24,然后按照上述过程进行操作,直到达到2或找到解决方案为止。
但是通过这个我没有得到结果吗?例如(0,0)(1,1)(2,2)(3,3)(4,4)处的灯是否点亮?
如果有人需要代码,我可以将其发布。
有人能告诉我使用回溯解决此游戏的正确方法吗?
谢谢。
有一个基于GF(2)的高斯消除的标准算法可以解决此问题。这个想法是建立一个代表按钮的矩阵,该矩阵按下代表灯的列向量,然后使用标准矩阵简化技术确定要按下的按钮。它以多项式时间运行,不需要任何回溯。
我有一个执行这个算法,包括它是如何工作可在我的个人网站的数学描述。希望对你有帮助!
编辑 :如果您被迫使用回溯,则可以使用以下事实来做到这一点:
使用这种方法,您可以使用简单的递归算法通过回溯来解决此问题,该算法可以跟踪电路板的当前状态以及您已经做出以下决定的按钮:
这将探索大小为2 25的搜索空间,大约为3200万。那很大,但并非无法克服。
希望这可以帮助!