2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 
Сообщение08.04.2009, 18:35 
Аватара пользователя
Serge_BN в сообщении #203055 писал(а):
Что такое g(x) и что такое h(x)? Что должны вычислять эти функции?

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

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

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group