c# - 最佳优先搜索评价函数

Question

我正在用 C# 实现最佳优先搜索算法。这是控制台应用程序。

我使用的数据结构是一棵树。我在这个算法中看到的评估函数是两个节点(例如城市)之间的直线距离。在图形应用中，距离是网格上的一个矢量(长度)。我的应用程序在控制台中，所以我无法计算节点之间的向量。

在我实现这个算法的过程中如何计算评估函数？

编辑(基于@Andrew 的想法)

我在一张纸上画了一棵树，并将坐标分配给节点。起点是 A(根)。终点是L(用户在程序中选择目标)。距离由二维欧几里得公式计算:

d(p,q) = sqrt(pow((p1 - q1), 2) + pow((p2 - q2), 2)) 

看图:Best-First Search for Tree

这是个好主意吗？

Answer 1

对于评估函数，您需要有一个通过两点的直线方程:

通过两个不同点的直线方程 P_0 = ( x_0, y_0 ) 和 P_1 = (x_1, y_1) 可以写成

(y - y_0)(x_1 - x_0) = (y_1 - y_0)(x - x_0). 

在它旁边，你的节点应该属于这一行。

即坐标为(x*, y*)的节点应满足方程:

(y* - y_0)(x_1 - x_0) = (y_1 - y_0)(x* - x_0)

如果等式的两部分计算出不同的值，则您的节点(点(x*，y*))不在所需点(城市)之间的直线上