使用 A* 算法解决逻辑游戏 Lights Out
我有一些问题，想使用 A* 算法来解决名为 Lights Out 的逻辑游戏。目前，我使用的是 A* 算法的一种实现方式，其中我将整个灯的矩阵作为算法中的一个节点（其中 1 表示灯亮，0 表示灯灭），连同要切换的当前节点的坐标一起考虑。在我从开放列表中选择具有最低 f 分数的节点之后，我会将其切换并获取其 8 个相邻邻居，然后将它们附加到开放列表上并重复此过程，直到找到一个节点，使得所有灯的总和等于 0 （所有灯都灭了）。
对于计算每个节点的 f 分数，我简单地计算了它们的局部矩阵中所有灯的总和，因此每次选择具有灯最少的矩阵的节点。
我知道算法的性能不会太好，即使与“追光”方法相比，但我不知道如何告诉算法选择哪个下一个节点，因此要使用哪个 f 评分函数，因为考虑矩阵中的灯总和最终导致算法每次循环相同的 3/4 个节点。
此外，我想要一些关于如何为算法表示节点的建议，因为我不知道如何在矩阵内使用一般用于路径优化的算法，在这种情况下，您将整个矩阵视为节点，您的目标不是到达特定节点，而仅是检查其总和是否为 0。
我使用的语言是 Lua。
谢谢。
编辑 5/27/19 由于我是 Lua 的新手，我将我的错误和编写代码的能力以及我对算法的理解归咎于我不能找到解决方案的事实。 我不擅长解释我所遇到的问题，因此我试图从我收到的评论中尽可能获取最佳，并且现在我将发布修改后的代码，以便各位可以更好地理解（代码>字哈哈）。
注意：我基于这篇文章编写了算法 [A* 算法]（https://medium.com/@nicholas.w.swift/easy-a-star-pathfinding-7e6689c7f7b2）
[Lua 源代码]（https://github.com/VincenzoNucci/lights-out-lua/blob/master/progetto.lua）
作者:
用户8405245
- Lua 虚拟机加密load(string.dump(function)) 后执行失败问题如何解决
- 我想创建一个 Nginx 规则，禁止访问
- 如何将两个不同的lua文件合成一个 东西有点长 大佬请耐心看完 我是小白研究几天了都没搞定
- 如何在roblox studio中1：1导入真实世界的地形？
- 求解，lua_resume的第二次调用继续执行协程问题。
- 【上海普陀区】内向猫网络招募【Skynet游戏框架Lua后端程序员】
- SF爱好求教：如何用lua实现游戏内调用数据库函数实现账号密码注册？
- Lua实现网站后台开发
- LUA错误显式返回，社区常见的规约是怎么样的
- lua5.3下载库失败
- 请问如何实现文本框内容和某个网页搜索框内容连接，并把网页输出来的结果反馈到另外一个文本框上
- lua lanes多线程使用
- 一个kv数据库
- openresty 有没有比较轻量的 docker 镜像
- 想问一下，有大佬用过luacurl吗
- 在Lua执行过程中使用Load函数出现问题
- 为什么 neovim 里没有显示一些特殊字符?
- Lua比较两个表的值（不考虑键的顺序）
- 有个lua简单的项目，外包，有意者加微信 liuheng600456详谈，最好在成都
- 如何在 Visual Studio 2022 中运行 Lua 代码？
不确定你要找什么。
首先，简单观察：你想要切换的游戏棋盘中的每个字段最多只能切换一次（切换一个字段两次不会做任何事情）。
你可以采用非常糟糕的方法，创建 2^n 个游戏状态（你的图中的节点），其中 n 是游戏棋盘中的字段数量。为什么这是可怕的？至少需要 O(2^n) 的时间和空间来创建整个图。在 O(2^n) 的时间内，你可以检查所有可能的移动（因为你想切换每个棋盘一次），并立即告诉结果，而不是运行额外的 A*。
更好的想法（？）：让我们不要物理上创建整个图。你不想访问一个节点两次，所以你应该将已访问的节点存储在某个地方（可能是一些位掩码集，其中你可以快速检查一个节点是否已经在集合中）。然后，当你在某个节点时，你检查所有相邻的节点——在切换一个字段后的游戏状态。如果它们已经被访问过了，请忽略它们，否则将它们添加到你的优先队列中。然后从优先队列中取出第一个节点，将其移除并“进入”它所代表的游戏状态。
正如我所说，你可以将游戏状态表示为尺寸为 n 的位掩码——如果第 i 个字段没有被切换，则在第 i 个位置上为 0，否则为 1。
这会比朴素方法更好吗？这取决于你的启发式函数。我不知道哪一个更好，你必须尝试一些并检查结果。在最坏的情况下，你的 A* 将检查每个节点，使复杂度比简单的暴力更糟糕。如果你运气好，它可能会显著加速。