我可以为基于图形的（非网格）A*算法使用哪些启发式函数提供帮助？

Question

5

我正在学习A*路径寻找算法，而我发现的所有示例都是基于网格的。因此，他们所有的启发式函数都依赖于某种物理距离（如曼哈顿距离、对角线距离或欧几里得距离）。

但是，如果我们不是用网格，而是用自由形式的图形呢？比如下面的示例，其中S是起点，G是终点：

S---A
|   
|   G
|   |
B---C---D

在这种情况下，“直线距离”近似值并没有意义，因为这个图表等同于。

S---A
|   
B---C---D
    |
    G

那么在这种情况下，我可以使用什么样的启发式函数？

- David says Reinstate Monica

1

@Tuan333 使用BFS不会否定使用A*的目的吗？ - slider

1

启发式常常是基于搜索执行环境的估计值。您在使用这个自由形式图时，所处的上下文是什么？ - slider

@slider 但这是在无权树上的BFS。A将计算加权树上的实际成本。不过，我理解你的观点。启发式函数有时最好快速完成，BFS并不那么快。尽管如此，它肯定会产生一种启发式（运行一次BFS，然后在运行A时使用其结果）。 - TuanDT

@Tuan333 我已经假设所有成本都是1（因此没有权重）。问题是，我如何估计其余部分的距离？我不知道还剩下多少节点。 - David says Reinstate Monica

2

启发式算法是尝试利用额外的信息来更快地解决问题的一种方法。如果除了图形本身之外没有关于问题的任何信息，那么就没有有用的方法来整合启发式搜索。 - seaotternerd

显示剩余10条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Imran · Accepted Answer

在一般情况下，没有启发式方法可以改进Dijkstra算法的运行时间。

当特定问题具有额外的结构时，启发式方法是有用的。嵌入平面图正好具有这种结构：直线距离的概念可以作为启发式方法，就像您的示例一样。

考虑排序的类比。在一般情况下，我们知道对于长度为O（n）的数组，排序的时间复杂度是O（nlogn）。但是，如果我们的数据满足数组中的数字在0到k范围内，其中k<<n，则我们可以使用计数排序以O（n）的时间进行排序。

在您的示例中，您没有提供任何可用于改进Dijkstra算法一般情况下的运行时间的输入数据的其他结构，因此您将不会找到任何有用的启发式方法。