C++ 如何使用动态计算的新节点实现 A*？
C++ How to implement A* with new nodes calculated on the fly?
我正在尝试将 A* 用于搜索问题，我从矩阵的特定状态（例如全零）开始，每一步我都可以对矩阵执行几个转换之一，我想到达在矩阵的另一种状态（例如所有状态）。搜索节点还存储了一些其他辅助对象。
因此，
搜索节点相当大（每一步包含矩阵状态+其他对象）
由于搜索space也很大，我没有"Graph"对象，我只是在每一步中即时生成新节点。
在 A* 中，我需要有一个从每个节点到其 gScore 的映射。通常，如果我正在搜索静态图形对象，我可以只使用带有指针键的 unordered_map，即
unordered_map<Node*, int> gScore;
但是由于我正在动态生成新节点，每个新节点都会有一个新的内存地址。所以我可以有两个具有完全相同状态和不同地址的节点。
这也是优先队列的问题
boost::heap::fibonacci_heap<Node*, boost::heap::compare<mycomp> > pq;
因为使用 decrease-key 我又一次 运行 进入了上面的问题——优先级队列总是认为新节点是不同的，因为它有不同的内存地址。
我相信这个问题并不少见（即使用动态计算的大节点进行搜索），那么人们通常如何处理它？
So I could have two Nodes with the exact same state and different addresses.
如果这就是你的问题所在，那么答案就是使用 unordered_set<Node> 而不是仅仅更新节点，并确保你的 Node class 有与之关联的适当哈希函数。这将负责删除节点的重复数据。
下一个问题是：您希望遍历多少潜在搜索 space？在纸面上，您总是有可能遇到退化的情况，在这种情况下，您需要遍历的节点超过内存所能容纳的数量，这将是一个问题。
要解决这个问题，主要有两种方法：
在放弃搜索之前选择任意数量的节点打开/内存消耗，并将其视为有效无法解决的情况。
实际搜索潜在搜索 space，直到找到解决方案。在那种情况下，A* 不会削减它，您将需要一个内存效率更高的算法，例如 Iterative-deepening A*.
我正在尝试将 A* 用于搜索问题，我从矩阵的特定状态（例如全零）开始，每一步我都可以对矩阵执行几个转换之一，我想到达在矩阵的另一种状态（例如所有状态）。搜索节点还存储了一些其他辅助对象。
因此，
搜索节点相当大（每一步包含矩阵状态+其他对象）
由于搜索space也很大，我没有"Graph"对象，我只是在每一步中即时生成新节点。
在 A* 中，我需要有一个从每个节点到其 gScore 的映射。通常，如果我正在搜索静态图形对象，我可以只使用带有指针键的 unordered_map，即
unordered_map<Node*, int> gScore;
但是由于我正在动态生成新节点，每个新节点都会有一个新的内存地址。所以我可以有两个具有完全相同状态和不同地址的节点。
这也是优先队列的问题
boost::heap::fibonacci_heap<Node*, boost::heap::compare<mycomp> > pq;
因为使用 decrease-key 我又一次 运行 进入了上面的问题——优先级队列总是认为新节点是不同的，因为它有不同的内存地址。
我相信这个问题并不少见（即使用动态计算的大节点进行搜索），那么人们通常如何处理它？
So I could have two Nodes with the exact same state and different addresses.
如果这就是你的问题所在，那么答案就是使用 unordered_set<Node> 而不是仅仅更新节点，并确保你的 Node class 有与之关联的适当哈希函数。这将负责删除节点的重复数据。
下一个问题是：您希望遍历多少潜在搜索 space？在纸面上，您总是有可能遇到退化的情况，在这种情况下，您需要遍历的节点超过内存所能容纳的数量，这将是一个问题。
要解决这个问题，主要有两种方法：
在放弃搜索之前选择任意数量的节点打开/内存消耗，并将其视为有效无法解决的情况。
实际搜索潜在搜索 space，直到找到解决方案。在那种情况下，A* 不会削减它，您将需要一个内存效率更高的算法，例如 Iterative-deepening A*.