任何目标双向a* pathfinding参考
（从cs.Stackexchange转发，因为我没有答案或评论）
我想解决从某个节点到任何的定向加权图上找到最短路径的问题一组指定的目标节点集（最好是最接近的目标节点，但这并不重要）。使用A*算法来实现此操作的标准（我相信）方法是使用距离距离目标启发式启发式（可允许），并在达到任何目标节点后立即退出。
但是，在我的情况下（如果那很重要的话，这是AI的游戏）可能是无法到达的（或全部）的；此外，可以从此类目标达到的一组节点通常很小（或者至少在这种情况下我要优化）。对于一个目标的情况，双向搜索听起来很有希望：反向搜索方向将迅速消耗所有可触及的节点，并得出结论没有路径。
我的问题是：有没有办法将这两种方法结合在一起，即执行双向A*以找到通往指定目标节点集的任何任何的路径？我不确定要为反向搜索方向选择什么启发式功能，停止条件等等。
(reposted from cs.stackexchange since I got no answers or comments)
I want to solve the problem of finding a shortest path on a directed weighted graph from a certain node to any of a specified set of destination nodes (preferably the closest one, but that's not that important). The standard (I believe) way to do this with the A* algorithm is to use a distance-to-closest-goal heuristic (which is admissable) and exit as soon as any of the goal nodes is reached.
However, in my scenario (which is game AI, if that matters) some (or all) of the goals might be unreachable; furthermore, the set of nodes reachable from such goals is typically quite small (or, at least, I want to optimize in that particular case). For the case of a single goal, bidirectional search sounds promising: the reverse search direction would quickly exhaust all reachable nodes and conclude that no path exists. These slides by Andrew Goldberg et al. describe the bidirectional A* algorithm with proper conditions on the heuristics, as well as stopping conditions.
My question is: is there a way to combine these two approaches, i.e. to perform bidirectional A* to find path to any of a specified set of goal nodes? I'm not sure what heuristic function to choose for the reverse search direction, what are the stopping conditions, etc. Googling for anything on this topic didn't get me anywhere either.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论