3.5. Оптимизационные задачи на графах

Большое количество практических задач формулируются как задачи поиска фрагментов графа или каких-то его характеристик, причем существует множество вариантов решения. Каждое решение оценивается числом, и среди множества решений нужно найти такое, для которого оценка имеет экстремальное значение - минимальное или максимальное. Чаще всего в качестве оценок используется сумма весов дуг или ребер, входящих в решение, - тогда оценка называется аддитивной, или произведение весов - тогда говорят омультипликативнойоценке. Наиболее часто ограничиваются случаем, когда веса дуг являются неотрицательными целыми числами.

3.5.1. Поиск путей в графе

Пусть в графе заданы две вершины a_н и a_к, названные соответственно начальной и конечной. Выделим несколько задач, связанных с поиском путей в графе:

- найти путь между начальной и конечной вершиной. Эта задача называется задачей поиска пути в лабиринте;

- найти минимальный путь между заданными вершинами;

- найти максимальный путь;

- найти цикл Эйлера.

3.5.1.1. Кратчайшие пути

Рассмотрим задачу поиска минимального пути между двумя заданными вершинами a_н и a_к в графе при условии, что каждой дуге (i,j) сопоставлен вес c_i,j-неотрицательное число и оценка аддитивна. Если веса обозначают длину дуги, то задача формулируется как задача нахождения кратчайшего пути между заданными вершинами.

Рассмотрим классический алгоритм решения этой задачи - алгоритм Дейкстры, в основе которого лежит следующий

тезис Дейкстры: если кратчайший путь проходит через вершину a_i, то длина части пути от a_н до a_i должна быть минимально возможной.

Алгоритм представим следующей последовательностью шагов.

1. Начальные присваивания. Каждой вершине, кроме начальной, сопоставим вес l(a_i), равный бесконечности, назовем этот вес временным. Начальной вершине сопоставим вес, равный нулю: l(a_н)=0, назовем этот вес постоянным, вершину a_н назовем текущей и обозначим как p .

2. Обновление весов. Всем вершинам, связанным с текущей по исходящим дугам и имеющим временные веса, изменим веса по правилу l(а_i)=min(l(а_i), l(p)+с_p,j)

3. Смена текущей вершины. Среди вершин с временной оценкой найдем вершину с минимальным весом и назовем ее текущей, а ее вес - постоянным. Если это есть вершина a_к, то перейдем к пункту 4, иначе - к пункту 2.

4. Выделение пути обратным ходом. Определим конечную вершину как текущую; для каждой вершины, связанной с ней по заходящим дугам, определим разность между весом текущей вершины и весом дуги. Вершину, вес которой совпадает с этой разностью, назовем текущей, а дугу отнесем к пути. То, что такая вершина всегда найдется, гарантируется способом построения весов вершин. Возможно, что таких вершин будет несколько, что говорит о существовании нескольких решений задачи. Выберем в этом случае любую из них. Повторим эту процедуру до тех пор, пока текущей не станет начальная вершина. В результате множество отнесенных к пути дуг дадут искомое решение.

Пример. Заданный граф приведен на рис. 3.4. Ход решения представим таблицей 3.2.

Выполняя шаг 4 алгоритма, выделим путь 12-9-6-3-2-1. Но существует еще один путь той же длины-12-9-8-5-4-1, так как для вершины 9 имеем два одинаковых по длине пути к началу, проходящих через вершины 8 и 6.

Легко видеть, что решением задачи по алгоритму Дейкстры всегда будет путь минимальной длины.