修改了星寻路启发式设计 [英] Modified a-star pathfinding heuristic design

问题描述

第一， 理想的路径是（按重要性排序）：

FIRST, The ideal path was (in order of importance):

1. shortest

我的启发（F）为：

My heuristic (f) was:

manhattan distance (h) + path length (g)

这是越野车，因为它推崇，改变了方向朝向目标的路径，然后蜿蜒回来。

This was buggy because it favored paths which veered towards the target then snaked back.

第二， 理想的路径是：

SECOND, The ideal path was:

1. shortest
2. approaches the destination from the same y coordinate (if of equal length)

我的启发保持不变。我在最后检查第二个标准，在达到目标之后。启发式被做稍微低效（修复于水火之中的问题），这也导致了总是被搜索的必要相邻的坐标。

My heuristic stayed the same. I checked for the second criteria at the end, after reaching the target. The heuristic was made slightly inefficient (to fix the veering problem) which also resulted in the necessary adjacent coordinates always being searched.

三， 理想的路径：

1. shortest
2. approaches the destination from the same y coordinate (if of equal length)
3. takes the least number of turns

现在我试图使启发式（F）：

Now I tried making the heuristic (f):

manhattan distance (h) + path length (g) * number of turns (t)

这当然适用于标准的＃1和＃3，和内在修复于水火之中的问题。不幸的是它现在如此有效，以至于测试条件＃2的端部不工作，因为一组节点的探索是没有大到足以重建的最优解。

This of course works for criteria #1 and #3, and fixes the veering problem inherently. Unfortunately it's now so efficient that testing for criteria #2 at the end is not working because the set of nodes explored is not large enough to reconstruct the optimal solution.

谁能告诉我如何符合标准的＃2到我的启发（F），或要不然怎么解决这个问题？

Can anyone advise me how to fit criteria #2 into my heuristic (f), or how else to tackle this problem?

准则2例如：如果目标是（4,6）和所述路径（3,6）和（4,5）是相同的长度，那么理想的解决方案应通过（3,6），因为它从Y平面接近的（4,5），其来源于X平面代替。但是，如果长度是不相同的，则该最短路径必须不管它接近在什么平面青睐。

CRITERIA 2 example: If the goal is (4,6) and the paths to (3,6) and (4,5) are of identical length, then the ideal solution should go through (3,6) because it approaches from the Y plane instead, of (4,5) which comes from the X plane. However if the length is not identical, then the shortest path must be favored regardless of what plane it approaches in.

推荐答案

您似乎混淆了A *启发式，什么的拉塞尔和放大器;诺维格调用的 ^ h 的，与部分路径开销的先按g 的。总之，这些构成了优先级的 F = 先按g + ^ h 的。

You seem to be confusing the A* heuristic, what Russell & Norvig call h, with the partial path cost g. Together, these constitute the priority f = g + h.

启发式应该是多少成本，从当前点达到目标的一个乐观的估计。曼哈顿距离是适合的 ^ h 的，如果步骤上，下，左，右，走至少单位成本。

The heuristic should be an optimistic estimate of how much it costs to reach the goal from the current point. Manhattan distance is appropriate for h if steps go up, down, left and right and take at least unit cost.

您的标准2，但是，应该在的路径开销的先按g 的，而不是在 ^ h 的。我不知道究竟你的意思的方法，从相同的Y目标坐标，但可以禁止/通过给所有其他惩罚进入目标节点接近无限大或非常高的路径开销。有严格不需要修改启发式的 ^ h 的。

Your criterion 2, however, should go in the path cost g, not in h. I'm not sure what exactly you mean by "approaches the destination from the same y coordinate", but you can forbid/penalize entry into the goal node by giving all other approaches an infinite or very high path cost. There's strictly no need to modify the heuristic h.

目前为止所采取的匝数也应该在部分路径开销的先按g 的。您可能希望在包含的 ^ h 的多少变成有留下来取，如果你能计算出这样的人物便宜。一个（乐观）估计

The number of turns taken so far should also go in the partial path cost g. You may want to include in h an (optimistic) estimate of how many turns there are left to take, if you can compute such a figure cheaply.

这篇关于修改了星寻路启发式设计的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！