Алгоритм решения задачи динамического программирования

Чтобы лучше понять суть метода решим задачу о распределении каналов (простейшую).

Пусть имеется K каналов, которые необходимо распределить между m средствами связи. Каждое из средств, при выдаче ему каналов имеет какую-то эффективность функционирования, выражаемую функцией f_i (x). Все функции f_i (x) (i =1, m) заданы. Пусть они выражают количество информации, которое может передать каждое средство. Как нужно распределить каналы, чтобы количество передаваемой информации было max?

Хотя задача и не содержит упоминания о времени, можно все же всю операцию поделить мысленно на шаги, считая за первый шаг выделение каналов средству 1, затем 2 и т.д. Управляемая система в данном случае - средства или ресурсы, которые распределяются. Состояние системы перед каждым шагом характеризуется одним числом S - количеством еще не распределенных каналов. В этой задаче «шаговыми управлениями» являются каналы x ₁, x ₂,..., x_m, выделяемые каждому средству связи. Требуется найти оптимальное управление т.е. такую совокупность чисел x ₁, x ₂,..., x_m, при которой суммарный объем информации максимален

Задачу решаем в формульном виде. Начнем оптимизацию с последнего m -го шага. Пусть мы подошли к этому шагу с остатком каналов равным S. Что делать? Очевидно, выделить их все средству C_m. Поэтому на последнем шаге условное оптимальное управление:

X_m (S) = S,

а условная оптимальная эффективность

Wm (S) = fm (S).

(4.9)

Задаваясь целой гаммой значений S (от 1 до К), мы для каждого значения S будем знать X_m (S) и W_m (S). Последний шаг оптимизирован.

(m -1)-й шаг. Пусть мы подошли к нему с запасом каналов S. Обозначим W_{m -1}(S) условную оптимальную эффективность на двух последних шагах(m -1)-м и m -м (который уже оптимизирован).

Если мы выделим на(m -1)-м шаге средству(m -1) x каналов, то последний шаг останется S-x 0 и эффективность за два последних шага будет

Wm -1(S) = fm -1(x) + Wm (S-x)

(4.10)

и нужно такое x, при котором эта эффективность максимальна:

(4.11)

Далее оптимизируем(m -2)-й шаг и т.д. Вообще для любого i -го шага мы будем находить условную оптимальную эффективность по формуле

(4.12)

Продолжая таким образом, дойдем наконец до 1-го шага (выделение каналов первому средству связи). Здесь не нужно будет варьировать значения S перед первым шагом их количество мы точно знаем - K. Тогда эффективность всех средств

(4.13)

Итак max эффективности найден. Теперь прочтем рекомендации. То значение x, при котором достигается max (10) и есть оптимальное управление x ₁^* на первом шаге. После выделения этого количества каналов первому средству их останется K-x ₁^*, т.е. S ₂= K-x ₁^*. Но для этого запаса каналов у нас уже есть оптимальное x ₂^*= x ₂(S) и так до конца.

Такие ультрапростые задачи не часто встречаются на практике. Если же состояние системы на каждом шаге описывается многими параметрами и число возможных состояний каждого параметра велико, то становится трудно (иногда невозможно) перебрать все их варианты и для каждого найти условное оптимальное управление. По меткому выражению родоначальника метода ДП - Беллмана - над нами повисает «проклятие многомерности». Бич, кстати, вообще всех методов оптимизации.

Принцип оптимальности.

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

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

2. Расчленить операцию на этапы (шаги).

3. Выяснить набор шаговых управлений x_i для каждого шага и налагаемые на них ограничения.

4. Определить, какой выигрыш приносит на i -м шаге управление x_i, если перед этим система была в состоянии S, т.е. записать «функцию выигрыша»:

wi = fi (S, xi)

(4.14)

5. Определить как меняется состояние S системы под влиянием управления x_i на i -м шаге:

S ' = fi (S, xi)

(4.15)

это нужно для обратного движения (при чтении рекомендаций).

6. Произвести условную оптимизацию по формулам (4.9)-(4.13) всех шагов, начиная от m -го до 1-го и для каждого из шагов указать условное управление x_i (S), при котором достигается max эффективности.

7. Произвести безусловную оптимизацию решения, зная состояние системы перед первым шагом S ₀. Взять найденное оптимальное управление на первом шаге x ₁^*= x ₁(S ₀); изменить по формуле (4.15) состояние системы перед вторым шагом. Для вновь найденного состояния найти оптимальное управление на втором шаге x ₂^* и т.д. до последнего шага.

 

ГЛАВА 5. СЕТЕВЫЕ ЗАДАЧИ

Введение в теорию графов

5.1.1. Основные понятия и определения теории графов

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

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

Определим основные понятия, которыми будем манипулировать в дальнейшем.

Граф G - это совокупность двух конечных множеств: множества V, содержащего n вершин (точек) и множества W, содержащего m неупорядоченных пар вершин.

Каждую пару x = { n,m } вершин в W называют ребром графа G и говорят, что х соединяет n и m.

Ребра, имеющие одинаковые концевые вершины, называются параллельными.

Вершина и ребро называются инцидентными друг другу, если вершина является для этого ребра концевой точкой. На рис. 1. вершина n₃ и ребро m₃ инцидентны друг другу, а ребра m ₄ и m ₅ параллельны.

 

Рис. 5.1

Две вершины, являющиеся концевыми для некоторого ребра, называются смежными вершинами. Два ребра, инцидентных одной и той же вершине, называются смежными ребрами. На рис. 5.1 n _1, n ₂ - смежные вершины, а m ₁, m ₄ - смежные ребра.

Степенью вершины называется число ребер, инцидентных ей. Вершина степени 1 называется висячей. Вершина степени 0 называется изолированной. На рис. 5.1 степень вершины n ₁ равна трем, n ₄ - висячая вершина, n ₅ - изолированная.

Путем в графе называется такая последовательность ребер, ведущая от некоторой начальной вершины n₁ в конечную вершину n_n, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза. Например, в графе, изображенном на рис. 5.1, последовательность ребер (m ₁, m ₂, m ₃, m _4, m ₅, m ₆) образует путь, ведущий от вершины n ₁ к вершине n ₄.

Циклом называется путь, начальная и конечная вершины которого совпадают.

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

Следует различать два типа графов - ориентированные и неориентированные. В ориентированных графах на ребрах задано направление движения потока, то есть у ребра фиксируется начало и конец. Такие ребра называются дугами. В неориентированных графах поток может проходить в обоих направлениях по любой ветви. Изобразим ориентированный (рис. 5.2) и неориентированный граф (рис. 5.3).

Цепью в ориентированном графе называется такая последователь­ность дуг, ведущих от вершины n ₁ к вершине n_n, в которой каждые две соседних дуги имеют общую вершину и никакая дуга не встречается более одного раза. Если направление цепи совпадает с направлением всех принадлежащих ей дуг, то цепь называется путем.

Рис. 5.2

Рис. 5.3

Взвешенным называется граф, в котором вершинам и ребрам поставлены в соответствие некоторые числа, называемые весами. Такой граф также называется сетью.

Рассмотрим некоторые типичные задачи, которые решаются аппаратом теории графов. Очевидно, что наиболее целесообразно использование графов при решении задачи связности. При решении задачи анализа для заданной сети графа нас может интересовать, например, может ли информация доставляться в любую точку сети, то есть существует ли по крайней мере хотя бы один путь из одной вершины в другую. Решается также вопрос и о количестве информации передаваемой по сети - задача определения максимального значения потока между двумя точками известна как «задача о максимальном потоке». Если рассматривать обратную задачу, то исходя из заданного множества узлов сети и требований к максимальным потокам информации между парами узлов с помощью аппарата теории графов возможно построить сеть, например, минимальной стоимости, удовлетворяющую данным требованиям, то есть решить задачу синтеза.

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

Как прямая, так и обратная задачи могут быть детерминированными или вероятностными. В последнем случае могут определяться вероятностные характеристики сети - среднее время доставки информации, среднее время ожидания информации в очереди и т.п.

Описание графа.

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

Выбор соответствующей структуры данных для представления графов имеет принципиальное влияние на эффективность алгоритмов, поэтому машинное представление графов заслуживает специального рассмотрения. Будем рассматривать, как ориентированные, так и неориентированные графы. Обозначать мы их будем G = (V,W), где V - множество вершин графа, а W - множество ребер. | V | = n, | W | = m.

В теории графов классическим способом представления графа являются матрица инциденций. Это матрицы с n строками и m столбцами. Для ориентированного графа столбец, соответствующий ориентированной ветви (x,y) содержит -1 в строке, соответствующей вершине x, 1 - в строке соответствующей вершине y и 0 в остальных строках.

Для неориентированного графа, столбец, соответствующий ветви (x,y) содержит 1 в строках, соответствующих вершинам x и y, и 0 в остальных строках.

Изобразим неориентированный и ориентированный графы и составим их матрицы инциденций.

	1,2	1,3	2,3	2,4	2,5	3,4	4,5
	-1	-1
					-1
			-1			-1

Рис. 5.4

По этой матрице можно видеть, где начинается и заканчивается соответствующая ориентированная ветвь, или каким узлам инцидентна ненаправленная ветвь.

	1,2	1,3	2,3	2,4	2,5	3,4	4,5

Рис.5.5

С алгоритмической точки зрения и с точки зрения использования памяти ЭВМ матрица инциденций является видимо самым худшим способом представления графа, который можно только себе представить. Во-первых он требует n x m ячеек памяти, причем большинство ячеек занято нулями. Неудобен также доступ к информации. Например, ответ на вопрос «существует ли дуга (x,y)» требует в худшем случае m шагов программы (т.е. перебора всех столбцов). Лучшим способом представления графа является матрица смежности (связности), определяемая как матрица B = [ b_i,j ] размера n x n, где b_i,j = 1 если существует ребро, ведущее из вершины i в вершину j и b_i,j = 0 в противном случае.

 

 

Рис. 5.6

Матрицы смежности для графов (рис.5.4, рис.5.5) приведены на рис. 5.6. Заметим, что матрица смежности нериентированного графа симметрична.

Основным преимуществом матрицы смежности является тот факт, что за один шаг можно узнать, существует ли ребро, связывающее узел x с узлом y. Недостатком же является то, что независимо от числа ребер объем занимаемой памяти равен n ² ячеек.

Более экономным в смысле расхода памяти является метод представления графа с помощью списка пар вершин, соответствующим его ребрам. Для графа на рис. 5.5 список будет иметь следующий вид (рис. 5.7):

 

 

Рис. 5.7 Рис. 5.8

В случае ориентированного графа необходимо либо помещать слева узлы отправители и справа - узлы получатели, либо (для смешанного графа) иметь три колонки, где третья колонка указывает, какая ветвь неориентирована (на рис. 5.8 такие ветви для графа рис. 5.4 помечены 0).

Во многих случаях лучшим способом описания графов является структура данных, называемая списком инцидентности. Она содержит для каждой вершины, помеченной признаком «начало», список вершин, инцидентных данной вершине. Каждый список вершин заканчивается признаком «конец». Размерность такой структуры m+n для ориентированного графа и n +2 m для неориентированного графа. На рис.5.9 приведен список инцидентности для графа рис. 5.4, а на рис. 5.10 - для графа рис. 5.5

нач. 1 - 2 - 3 кон. нач. 1 - 2 - 3 кон.

нач. 2 - 4 - 5 кон. нач. 2 - 1 - 3 - 4 - 5 кон.

нач. 3 - 2 - 4 кон. нач. 3 - 1 - 2 - 4 кон.

нач. 4 - 2 - 5 кон. нач. 4 - 3 - 2 - 5 кон.

нач. 5 - 4 кон нач. 5 - 2 - 4 кон.

Рис. 5.9 Рис. 5.10

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