什么是正确的启发式成本？为什么我的是错误的？在图上寻找最优路径

Question

我有一个简单的图表，我需要找到这个图表的启发式成本。

图是(矩阵表示)：

0 1 2 0 0 0 0
1 0 0 3 3 2 0
3 0 0 2 0 0 0
0 3 1 0 1 0 0
0 3 0 1 0 6 0
0 2 0 0 6 0 2
0 0 0 0 0 2 0

图片：

​

​

括号中的值表示当前目标顶点的顶点的启发式成本。

绿色顶点是开始，红色顶点是目标。

我创建了这个遗传成本矩阵：

0 2 6 3 1 9 5
9 0 2 4 6 4 1
1 3 0 5 2 9 4
3 1 5 0 1 7 8
0 6 2 1 0 10 14
2 1 6 3 7 0 5
1 4 3 2 1 3 0

我必须解释这一点。这个矩阵表示:例如，目标顶点是7；我们在矩阵中找到第7行；第一列中的值表示从1个顶点到7个顶点的启发式成本(7是目标)；第5列中的值表示从5个顶点到7个顶点的启发式成本(7是目标)；如果5是目标，我们将使用5行，依此类推。

这种基于零的启发式成本。我不知道如何找到好的启发式成本。那倒是一个问题。

总结一下：

首先，我的算法发现了错误的路径(可能是因为错误的启发式)。它找到了1-3-4-5 (长度为5)，但最好是1-2-5 (长度为4)。

而且，老师说，我的启发式成本阻止了算法找到好的路径，但对他没有帮助。我在将他说的话翻译成英语时遇到了问题，但他说了一些想法：“你的启发式方法不能高估最佳路径”。什么意思？

所以问题是:如何在我的案例中找到好的启发式成本？

Answer 1

我将把我的评论包装成一个答案。

首先，请注意，“高估最佳路径”意味着从某个节点v到目标的最短路径长度为k，但h(v)=k'为k'>k。在这种情况下，启发式方法高估了路径的长度。对于1个或多个节点执行的启发式算法被称为“不可接受的”，并且A*不能保证使用这样的启发式算法找到最短路径。

An admissible heuristic function (从不过高估计)保证为A*提供最优路径。对于所有v，最简单的允许启发式算法是h(v) =0。请注意，在这种情况下，A*的行为实际上类似于Dijsktra's Algorithm (它基本上是一个统一的A*)。

你可以找到更多的信息启发式算法，一个例子是首先对图进行预处理，并找到从每个节点到目标的最短未加权路径。这可以通过BFS高效地完成。将某些v到目标的未加权距离表示为uwd(v)。

现在，您可以创建一个启发式方法，即uwd(v) * MIN_WEIGHT，其中MIN_WEIGHT是图中最小的边权重。