使用 A 星查找路径的启发式函数
我正在尝试为以下问题找到最佳解决方案 
- 每个节点内表示的数字表示为
(x,y)。 - 一个节点的相邻节点的 y 值始终为（当前节点 y 值 +1）。
- 当我们从一个节点到其相邻节点时，
x值发生变化的成本为 1 - 如果 x 的值没有变化，则从节点到其相邻节点没有成本
x。 - 没有 2 个具有相同 y 值的节点被视为相邻。
最佳解决方案是成本最低的解决方案，我正在考虑使用 A* 路径查找算法来寻找最佳解决方案。
我的问题是，对于此类问题，A* 是一个不错的选择吗？或者我应该考虑其他算法，而且我也在考虑使用递归方法来计算启发式成本，但我感觉它不是一个好主意。
这是我认为启发式函数将像这样的
- 示例 节点的启发式权重 = Min(其子节点的启发式权重)
- 子节点也是如此。
但据我所知，启发式是一个近似值，所以我认为就启发式函数而言我走错了方向
I am trying to find a optimal solution for the following problem
- The numbers denoted inside each node are represented as
(x,y). - The adjacent nodes to a node always have a
yvalue that is (current nodes y value +1). - There is a cost of 1 for a change in the
xvalue when we go from one node to its adjacent - There is no cost for going from node to its adjacent, if there is no change in the value of
x. - No 2 nodes with the same
yvalue are considered adjacent.
The optimal solution is the one with the lowest cost, I'm thinking of using A* path finding algorithm for finding an optimal solution.
My question, Is A* a good choice for the this kind of problems, or should i look at any other algorithm, and also i was thinking of using recursive method to calculate the Heuristic cost, but i get the feeling that it is not a good idea.
This is the example of how I'm thinking the heuristic function will be like this
- The heuristic weight of a node = Min(heuristic weight of it's child nodes)
- The same goes for the child nodes too.
But as far as my knowledge goes, heuristic is meant to be an approximate, so I think I'm going in the wrong direction as far as the heuristic function is concerned
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果您使用适当的启发式方法，A* 保证在图中找到具有非负边路径成本的最低成本路径。是什么使得启发式函数合适？
首先，它必须是可接受的，即对于任何节点，它应该对从该节点到任何目标节点的最便宜路径的成本产生低估或正确的估计。这意味着启发式永远不应该高估从节点到目标的成本。
请注意，如果您的启发式计算每个节点的估计成本为 0，则 A* 只是变成广度优先穷举搜索。因此 h(n)=0 仍然是一种可接受的启发式，只是最坏的可能。因此，在所有可接受的启发法中，对实现目标的成本估计得越严格越好。
其次，计算成本必须低廉。它当然应该是 O(1)，并且最好应该单独查看当前节点。按照您的建议递归地评估成本将使您的搜索速度明显减慢，而不是更快！
因此，A* 适用性的问题是您是否能够提出一个相当好的启发式。从您的问题描述来看，尚不清楚您是否可以轻松提出一个。
根据问题领域，如果放宽要求，A* 可能非常有用。如果启发式变得不可接受，那么您就失去了找到最佳路径的保证。然而，根据距离高估的程度，解决方案可能仍然足够好（对于“足够好”的问题特定定义）。优点是有时您可以更快地计算出“足够好”的路径。在某些情况下，启发式的概率估计效果很好（它可以有额外的约束以保持在可接受的范围内）。
因此，一般来说，您可以对可处理的问题进行广度优先搜索，接下来更快地通过可接受的启发式对可处理的问题进行 A* 搜索。如果你的问题对于广度优先的穷举搜索来说是棘手的并且不允许启发式，那么你唯一的选择就是满足于“足够好”的次优解决方案。同样，A* 在这里可能仍然适用于不可接受的启发式，或者您应该考虑集束搜索变体。不同之处在于，集束搜索对当前正在探索图的方式的数量有限制，而 A* 通过选择成本较低的一些子集来间接限制它们。当不同搜索路径之间的成本差异很小时，即使放宽可受理性，也存在 A* 无法解决的实际情况。波束搜索对路径数量有硬性限制，在此类问题中可以更有效地工作。
A* guarantees to find the lowest cost path in a graph with nonnegative edge path costs, provided that you use an appropriate heuristic. What makes a heuristic function appropriate?
First, it must be admissible, i. e. it should, for any node, produce either an underestimate or a correct estimate for the cost of the cheapest path from that node to any of goal nodes. This means the heuristic should never overestimate the cost to get from the node to the goal.
Note that if your heuristic computes the estimate cost of 0 for every node, then A* just turns into breadth-first exhaustive search. So h(n)=0 is still an admissible heuristic, only the worst possible one. So, of all admissible heuristics, the tighter one estimates the cost to the goal, the better it is.
Second, it must be cheap to compute. It should be certainly O(1), and should preferably look at the current node alone. Recursively evaluating the cost as you propose will make your search significantly slower, not faster!
The question of A* applicability is thus whether you can come up with a reasonably good heuristic. From your problem description, it is not clear whether you can easily come up with one.
Depending on the problem domain, A* may be very useful if requirements are relaxed. If heuristic becomes inadmissible, then you lose the guarantee of finding the best path. Depending on the degree of overestimation of the distance, hovewer, the solution might still be good enough (for problem specific definition of "good enough"). The advantage is that sometimes you can compute that "good enough" path much faster. In some cases, probabilistic estimate of heuristics works good (it can have additional constraints on it to stay in the admissible range).
So, in general, you have breadth-first search for tractable problems, next faster you have A* for tractable problems with admissible heuristic. If your problem is intractable for breadth-first exhaustive search and does not admit a heuristic, then your only option is to settle for a "good enough" suboptimal solution. Again, A* may still work with inadmissible heuristic here, or you should look at beam search varieties. The difference is that beam searches have a limit on the number of ways the graph is currently being explored, while A* limits them indirectly by choosing some subset of less costly ones. There are practical cases not solvable by A* even with relaxed admissbility, when difference in cost among different search path is slight. Beam search with its hard limit on the number of paths works more efficiently in such problems.
当 Dijkstra 之类的东西可以工作时，使用 A* 似乎有点过分了。 Dijkstra 只适用于非负成本转换，这在本例中似乎是正确的。如果你可以实现负成本转换，那么贝尔曼福特法也应该有效。
Seems like an overkill to use A* when something like Dijkstra's would work. Dijkstra's will only work on non-negative cost transitions which seems true in this example. If you can have negative cost transitions then Bellman-Ford should also work.