是否有一种可接受的启发式方法可以在具有循环的有向图上执行 A*（A 星）搜索？
我正在开展一个学校项目，该项目要求我们生成带有加权边的随机有向图，并执行多种图遍历技术，以从起始节点（标记为红色）找到目标节点之一（标记为绿色）。示例图如下所示： 随机生成的有向图
我已经成功实现了所请求的无信息图搜索算法（深度优先搜索、广度优先搜索、迭代深化搜索和统一成本搜索）。然而，我们还被要求在此图上执行 A*（A 星）搜索，并且我正在努力寻找可接受的启发式方法，因为曼哈顿或欧几里得距离需要位置数据。
是否存在可以使用的有效启发式方法，或者是否存在没有足够信息的情况？
I am working on a school project which requires us to generate a random digraph with weighted edges and perform a number of graph traversal techniques to find one of the target nodes (marked in green) from the starting node (marked in red). A sample graph can be seen below:
Randomly Generated Digraph
I've managed to implement the requested uninformed graph search algorithms (Depth-First Search, Breadth-First Search, Iterative Deepening Search and Uniform Cost Search). However, we were also asked to perform A* (A-star) search on this graph and I am struggling to find an admissable heuristic since positional data is required for the Manhattan or Euclidian distances.
Is there a valid heuristic which can be used or is it the case of not having enough information?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
可以接受的启发式方法是成本是一定的 - 例如0。
这将使搜索变成统一的成本搜索。
An acceptable heuristic is that the cost is some constant - such as 0.
This will turn A* search into Uniform Cost Search.