Теория принятия решений

В различных проблемах принятия решений возникают самые разнообразные задачи оптимизации. Целью решения такой задачи является нахождение варианта, обладающего наилучшими свойствами (наименьшая длина, минимальное затраченное время, минимальная стоимость и т.д.).

Для их решения применяются те или иные методы, точные или приближенные. Существует несколько методов решения задач оптимизации: динамическое программирование, вариационное исчисление, метод статистических решений, использование искусственного интеллекта, методы дискретной математики.

К дискретным моделям относятся графовые (потоковые и транспортные сети, направленные графы) - им на этом ресурсе уделено особое внимание, и алгебраические (логическая алгебра, искусственный интеллект, автоматическая лингвистка)

Алгоритмы поиска кратчайших путей

Каждой дуге (х, у) исходного графа G поставим в соответствие число а_х,у. Если в графе отсутствует некоторая дуга (х, у), положим а_х,у =∞. Будем называть число а_х,у длиной дуги (х, у), хотя а_х,у можно также интерпретировать как соответствующие затраты или соответствующий весовой коэффициент. Определим длину пути как сумму длин отдельных дуг, составляющих этот путь.

Для любых двух вершин s и t графа G могут существовать несколько путей, соединяющих вершину s с вершиной t. В теории графов рассматривается задача, цель которой определить такой путь, ведущий из вершины s в вершину t, который имеет минимально возможную длину. Этот путь называется кратчайшим путем между вершинами s и t.

Существует несколько методов поиска кратчайших путей в графе:

·   алгоритм Дейкстры (алгоритм поиска кратчайших путей от заданной вершины)

·   алгоритм Флойда (алгоритм поиска длин всех кратчайших путей в графе)

·   алгоритм Данцига

Алгоритм Дейкстры

Описываемый в данном разделе алгоритм позволяет находить в графе кратчайший путь между двумя выделенными вершинами s и t при положительных длинах дуг. Этот алгоритм, предложенный в 1959 г. Дейкстрой, считается одним из наиболее эффективных алгоритмов решения задачи.

Главная идея, лежащая в основе алгоритма Дейкстры, предельно проста. Предположим, что нам известны m вершин, ближайших к вершине s (близость любой вершины x к вершине s определяется длиной кратчайшего пути, ведущего из s в x). Пусть также известны сами кратчайшие пути, соединяющие вершину s с выделенными m вершинами). Покажем теперь, как может быть определена (m + 1) - я ближайшая к s вершина.

Окрасим вершину s и m ближайших к ней вершин. Построим для каждой неокрашенной вершины y пути, непосредственно соединяющие с помощью дуг (х, у) каждую окрашенную вершину х с у. Выберем из этих путей кратчайший, и будем считать его условно кратчайшим путем из вершины s в вершину y.

Какая же из неокрашенных вершин является (m + 1) - й ближайшей к s вершиной? Та, для которой условно кратчайший путь имеет наименьшую длину. Это обусловливается тем, что кратчайший путь из вершины s в (m +1) - ю ближайшую вершину при положительном значении длин всех дуг должен содержать в качестве промежуточных лишь окрашенные вершины, т.е. вершины, входящие в число m вершин, ближайших к вершине s.

Итак, если известны m ближайших к s вершин, то (m + 1) - я ближайшая к s вершина может быть найдена так, как это описано выше. Начиная с m = 0, описанная процедура может повторяться до тех пор, пока не будет получен кратчайший путь, ведущий из вершины s к вершине t.

Описание алгоритма

Каждой вершине X в ходе алгоритма присваивается число d(x), равное длине кратчайшего пути из вершины S в вершину X и включающем только окрашенные вершины. Положить d(s)=0 и d(x)=∞ для всех остальных вершин графа. Окрашиваем вершину S и полагаем y=S, где y - последняя окрашенная вершина.

Для каждой неокрашенной вершины X пересчитывается величина d(x) по следующей формуле:

d(x)=min {d(x); d(y)+ a_y,x} (1)

Если d(x)=∞ для всех неокрашенных вершин, то алгоритм заканчивается т.к. отсутствуют пути из вершины S в неокрашенные вершины. Иначе окрашивается та вершина, для которой величина d(x) является минимальной. Окрашивается и дуга, ведущая в эту вершину в соответствии с выражением (1) и полагаем y=x.

Если y=t, кратчайший путь из s в t найден. Иначе переходим к шагу 2.

Каждый раз окрашивается вершина и дуга, заходящая в эту вершину. Окрашенные дуги не могут образовывать цикл, а образуют в исходном графе дерево с корнем (началом) в вершине s. Это дерево называют ориентированным деревом кратчайших путей. Путь из s в t принадлежит этому дереву. При поиске одного кратчайшего пути процедура наращивания завершается при достижении конечной вершины этого пути. Нам же необходимо получить все кратчайшие пути начинающиеся в вершине №1. Для этого процедуру наращивания ориентированного дерева продолжается до тех пор, пока все вершины не будут включены. Таким образом, мы получаем ориентированное дерево кратчайших путей, которое является покрывающим деревом графа.

Иногда в графе имеются несколько кратчайших путей. Кратчайший путь будет единственным, если в алгоритме ни разу не возникает неоднозначность при окрашивании дуги.

Главным условием успешного применения алгоритма Дейкстры к задаче на графе является неотрицательность длин дуг этого графа.