我正在尝试使用 A* 来解决搜索问题，其中我从矩阵的某种状态(例如所有零(开始，每一步我都可以在矩阵上执行几个转换中的一个，我想到达矩阵的另一个状态(例如所有状态(。搜索节点还存储一些其他辅助对象。
结果，
-
搜索节点相当大(每一步包含矩阵状态+其他对象(
-
由于搜索空间也很大，我没有"Graph"对象，我只是在每一步中动态生成新节点。
在 A* 中，我需要有一个从每个节点到其 gScore 的映射。通常，如果我搜索静态图形对象，我可以使用带有指针键的unordered_map，即
unordered_map<Node*, int> gScore;
但是由于我正在动态生成新节点，因此每个新节点都将具有一个新的内存地址。所以我可以有两个具有完全相同状态和不同地址的节点。
这也是优先级队列的问题
boost::heap::fibonacci_heap<Node*, boost::heap::compare<mycomp> > pq;
因为使用 reduce 键我再次遇到了上述问题 - 优先级队列总是认为新节点是不同的，因为它具有不同的内存地址。
我相信这个问题并不少见(即使用动态计算的大节点进行搜索(，那么人们通常如何处理它呢？
所以我可以有两个具有完全相同状态和不同地址的节点。
如果这就是你的问题，答案就是使用unordered_set<Node>而不仅仅是更新节点，并确保你的Node类有一个与之关联的适当哈希函数。这将负责删除您的节点。
下一个问题是：你期望遍历多少潜在的搜索空间？在纸面上，你总是有可能遇到一个退化的情况，你需要遍历的节点数超过了内存所能容纳的节点，这将是一个问题。
为了解决这个问题，有两种主要方法：
-
在放弃搜索之前，选择要打开的任意数量的节点/要消耗的内存，并将其视为实际上无法解决的情况。
-
实际上搜索该潜在搜索空间，直到找到解决方案。在这种情况下，A* 不会削减它，您需要一个更节省内存的算法，例如迭代深化 A*。