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

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

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

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

EDIT (на основе @ идеи Эндрю)

Я нарисовал дерево на листе бумаги, и я присвоены координаты узлов. Начальная точка A (корень). Конечная точка L (пользователь выбирает цель в программе). Расстояние вычисляется по формуле евклидова для двух размеров:

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

Посмотрите на картинке: Best-First Search for Tree

это хорошая идея?

источник

2014-12-10 raz

Я еще не пытался вычислить эту функцию eval, потому что у меня нет идеи для этого. Есть идеи? – raz

Вам не нужен интерфейс для вычисления расстояния. Сначала найдите математику (или готовый мир кода/библиотеки) (это называется усилием). Если у вас возникли трудности с кодом, у вас есть все основания просить о помощи здесь. Я могу найти математику через 3 секунды, вы? – Sinatr

Но мое представление дерева представляет собой матрицу nxn (матрица смежности). Я создаю дерево с помощью словаря, а затем применяю ключи и значения к матрице. Как я могу вычислить эту функцию? – raz

Для функции оценки необходимо иметь уравнение линии, которая проходит через две точки:

Уравнение прямой, проходящей через две различные точки 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).

Рядом с этим узел должен принадлежать этой линии.

То есть узел с координатами (х *, у *) должна удовлетворять уравнению:

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

Если обе части уравнения оценки для различных значений, ваш узел (точка (х *, у *)) не находится на прямой между требуемыми точками (городами)

источник

2014-12-10 15:47:53 Andrew

Я думаю, что TSP не связан с поиском Best-First Search. В B-F Search мы используем функцию оценки как эвристику. Btw. Я буду реализовывать позже Simulated Отжиг для проблемы TSP. Но сначала я должен сделать Best-First Search. – raz

ОК, если вопрос о оценочной функции, то вам нужна линия, которая проходит через ваш начальный и конечный узел. – Andrew

Хм, это имеет смысл. Итак, я должен добавить координаты местоположения для каждого узла, но как применять координаты для узла, если это консольное приложение? Мое представление представляет собой матрицу смежности для дерева. – raz

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

ответ

Смежные вопросы