8Puzzle game with A* : 开放集的结构是什么？
8Puzzle game with A* : What structure for the open set?
我最近在 python 开发一个 8 拼图游戏解算器，我需要一些帮助
到目前为止，我已经完成了使用曼哈顿距离作为启发式函数的 A* 算法的编码。
求解器 运行s 并在不到 2 秒内找到 ~60% 的解决方案
但是，对于其他 ~40%，我的求解器最多可能需要 20-30 分钟，就像 运行ning 没有启发式一样。
我开始排查问题，似乎是我使用的 openset 导致了一些问题:
- 我的开集是一个数组
- 每次迭代，我循环遍历 openset 以找到最低的 f(n)（复杂度：O(n)）
我觉得 O(n) 对 运行 一个体面的 A* 算法来说太多了，所以我想知道我应该如何设法减少 openset "time eater"
感谢您的帮助！祝你有美好的一天
编辑：已修复
我解决了我的问题，这实际上是一个双重问题。
我尝试使用字典而不是数组，在数组中我通过节点的 f(n) 值存储节点，这让我可以 运行 求解器和游戏的 ~181000 种可能性几秒钟
第二个问题（因为第一个我不知道它），是我不知道益智游戏的可解性，当我随机化初始节点时，50% 的谜题不能得到解决。这就是为什么 openset 作为数组花了这么长时间的原因。
开集应该是优先队列。通常这些是使用 二进制堆 实现的，尽管存在其他实现。
数组列表和字典都不是有效的。
闭集应该是一个有效的集合，所以通常是散列table或二进制搜索树，具体取决于您的语言标准库的默认设置。
字典（又名 "map"）在技术上可行，但它在概念上是错误的数据结构，因为您没有映射到任何东西。数组列表效率不高。
我最近在 python 开发一个 8 拼图游戏解算器，我需要一些帮助 到目前为止，我已经完成了使用曼哈顿距离作为启发式函数的 A* 算法的编码。
求解器 运行s 并在不到 2 秒内找到 ~60% 的解决方案 但是，对于其他 ~40%，我的求解器最多可能需要 20-30 分钟，就像 运行ning 没有启发式一样。
我开始排查问题，似乎是我使用的 openset 导致了一些问题:
- 我的开集是一个数组
- 每次迭代，我循环遍历 openset 以找到最低的 f(n)（复杂度：O(n)）
我觉得 O(n) 对 运行 一个体面的 A* 算法来说太多了，所以我想知道我应该如何设法减少 openset "time eater"
感谢您的帮助！祝你有美好的一天
编辑：已修复
我解决了我的问题，这实际上是一个双重问题。
我尝试使用字典而不是数组，在数组中我通过节点的 f(n) 值存储节点，这让我可以 运行 求解器和游戏的 ~181000 种可能性几秒钟
第二个问题（因为第一个我不知道它），是我不知道益智游戏的可解性，当我随机化初始节点时，50% 的谜题不能得到解决。这就是为什么 openset 作为数组花了这么长时间的原因。
开集应该是优先队列。通常这些是使用 二进制堆 实现的，尽管存在其他实现。
数组列表和字典都不是有效的。
闭集应该是一个有效的集合，所以通常是散列table或二进制搜索树，具体取决于您的语言标准库的默认设置。
字典（又名 "map"）在技术上可行，但它在概念上是错误的数据结构，因为您没有映射到任何东西。数组列表效率不高。