Функция оценки Best-First Search

Question

Я реализую алгоритм поиска Best-First в C#. Это консольное приложение.

Структура данных, которую я использую - это дерево. Функцией оценки, которую я видел в этом алгоритме, было прямолинейное расстояние между двумя узлами (например, городами). Расстояние было вектором (длиной) на сетке в графическом приложении. Мое приложение находится в консоли, поэтому я не могу рассчитать векторы между узлами.

Как я могу рассчитать функцию оценки на моем пути реализации этого алгоритма?

РЕДАКТИРОВАТЬ (основываясь на идее Эндрю)

Я нарисовал дерево на листе бумаги и назначил координаты узлам. Начальная точка 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*)) не находится на прямой линии между требуемыми точками (городами)