Из теории графов. Алгоритм А*

[Serge_BN]

Подскажите, плз,
Википедия сообщает:

Цитата:

Алгоритм А* ...
В начале работы просматриваются узлы, смежные с начальной; выбирается тот из них, который имеет минимальное значение f(x), после чего этот узел раскрывается. На каждом этапе алгоритм оперирует с множеством путей из начальной точки до всех ещё не раскрытых (листовых) вершин графа («множеством частных решений»), которое размещается в очереди с приоритетом. Приоритет пути определяется по значению f(x) = g(x) + h(x). Алгоритм продолжает свою работу до тех пор, пока значение f(x) целевой вершины не окажется меньшим, чем любое значение в очереди (либо пока всё дерево не будет просмотрено). Из множественных решений выбирается решение с наименьшей стоимостью.

Если дан граф из $N$ вершин и для каждой грани известна длина этой грани, то как правильно определить функцию $f(x)$ ?
Что такое $g(x)$ и что такое $h(x)$? Что должны вычислять эти функции?

[Лиля]

Serge_BN в сообщении #203055 писал(а):

Что такое g(x) и что такое h(x)? Что должны вычислять эти функции?

В той же статье из Вики:

Цитата:

Порядок обхода вершин определяется эвристической функцией «расстояние + стоимость» (обычно обозначаемой как $f(x)$). Эта функция — сумма двух других: функции стоимости достижения рассматриваемой вершины $(x)$ из начальной (обычно обозначается как $g(x)$ и может быть как эвристической, так и нет) и эвристической оценкой расстояния от рассматриваемой вершины к конечной (обозначается как $h(x)$).

Функция $h(x)$ должна быть допустимой эвристической оценкой, то есть не должна переоценивать расстояния к целевой вершине. Например, для задачи маршрутизации $h(x)$ может представлять собой расстояние до цели по прямой линии, так как это физически наименьшее возможное расстояние между двумя точками.