VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

В этом примере это узлы BC и FC. Ближайший к ложному корню узел

соответствует кратчайшему маршруту к узлу C в исходной сети. Узлы в

кратчайшем маршруте в новой сети соответствуют связям в кратчайшем маршруте

в исходной сети.

@Рис. 12.16. Дерево кратчайшего маршрута в сети со штрафами за повороты

========339

На рис. 12.16 кратчайший маршрут начинается с ложного корня, идет в узел

DE, затем узлы EF и FC и имеет полную цену 16. Этот путь соответствует пути

D, E, F, C в исходной сети. Прибавив один штраф за левый поворот E, F, C,

получим, что цена этого пути в исходной сети также равна 16.

Заметьте, что вы не нашли бы этот путь, если бы построили дерево

кратчайшего маршрута в исходной сети. Без учета штрафов за повороты,

кратчайшим маршрутом из узла D в узел C был бы путь D, E, B, C с полной

ценой 12. С учетом штрафов цена этого пути равна 17.

Применения метода поиска кратчайшего маршрута

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

Очевидным примером является поиск кратчайшего маршрута между двумя точками

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

кратчайшего маршрута менее очевидными способами. Следующие разделы

описывают некоторые из этих приложений.

Разбиение на районы

Предположим, что имеется карта города, на которую нанесены все пожарные

депо. Может потребоваться определить для каждой точки города ближайшее к

ней депо. На первый взгляд это кажется трудной задачей. Можно попытаться

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

найти, какое депо расположено ближе всего к каждому из узлов. Или можно

построить дерево кратчайшего маршрута с корнем в каждом из пожарных депо и

записать расстояние от каждого из узлов до каждого из депо. Но существует

намного более быстрый метод.

Создадим ложный корневой узел и соединим его с каждым из пожарных депо

связями с нулевой ценой. Затем найдем дерево кратчайшего маршрута с корнем

в этом ложном узле. Для каждой точки в сети кратчайший маршрут из ложного

корневого узла к этой точке пройдет через ближайшее к этой точке пожарное

депо. Чтобы найти ближайшее к точке пожарное депо, нужно просто

проследовать по кратчайшему маршруту от этой точки к корню, пока на пути не

встретится одно из депо. Построив всего одно дерево кратчайшего маршрута,

можно найти ближайшие пожарные депо для каждой точки в сети.

Программа District использует этот алгоритм для разбиения сети на районы.

Так же, как и программа PathC и другие программы, описанные в этой главе,

она позволяет загружать, редактировать и сохранять на диске ориентированные

сети с ценой связей. Если вы не добавляете и не удаляете узлы или связи, вы

можете выбрать депо для разделения на районы. Добавьте узлы к списку

пожарных депо щелчком левой кнопки мыши, затем щелкните правой кнопкой в

любом месте формы, и программа разобьет сеть на районы.

На рис. 12.17 показано окно программы, на котором изображена сеть с тремя

депо. Депо в узлах 3, 18 и 20 обведены жирными кружочками. Разбивающие сеть

на районы деревья кратчайшего маршрута изображены жирными линиями.

=====340

@Рис. 12.17. Программа District

Составление плана работ с использованием метода критического пути

Во многих задачах, в том числе в больших программных проектах, определенные

действия должны быть выполнены раньше других. Например, при строительстве

дома до установки фундамента нужно вырыть котлован, фундамент должен

застыть до того, как начнется возведение стен, каркас дома должен быть

собран прежде, чем можно будет выполнять проводку электричества,

водопровода и кровельные работы и так далее.

Некоторые из этих задач могут выполняться одновременно, другие должны

выполняться последовательно. Например, можно одновременно проводить

электричество и прокладывать водопровод.

Критическим путем (critical path) называется одна из самых длинных

последовательностей задач, которая должна быть выполнена для завершения

проекта. Важность задач, лежащих на критическом пути, определяется тем, что

сдвиг сроков выполнения этих задач приведет к изменению времени завершения

проекта в целом. Если заложить фундамент на неделю позже, то и здание будет

завершено на неделю позже. Для определения заданий, которые находятся на

критическом пути, можно использовать модифицированный алгоритм поиска

кратчайшего маршрута.

Вначале создадим сеть, которая представляет временные соотношения между

задачами проекта. Пусть каждой задаче соответствует узел. Нарисуем связь

между задачей I и задачей J, если задача I должна быть выполнена до начала

задачи J, и присвоим этой связи цену, равную времени выполнения задачи I.

После этого создадим два ложных узла, один из которых будет соответствовать

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

с нулевой ценой со всеми узлами в проекте, в которые не входит ни одна

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

начинать немедленно, не ожидая завершения других задач.

Затем создадим ложные связи нулевой длины, соединяющие все узлы, из которых

не выходит не одной связи, с конечным узлом. Эти узлы представляют задачи,

которые не тормозят выполнение других задач. После того, как все эти задачи

будут выполнены, проект будет завершен.

Найдя самый длинный маршрут между начальным и конечным узлами сети, мы

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

для выполнения проекта.

========341

@Таблица 12.1. Этапы сборки дождевальной установки

Рассмотрим, например, упрощенный проект сборки дождевальной установки,

состоящий из пяти задач. В табл. 12.1 приведены задачи и временные

соотношения между ними. Сеть для этого проекта показана на рис. 12.18.

В этом простом примере легко увидеть, что самый длинный маршрут в сети

выполняет следующую последовательность задач: выкопать канавы, смонтировать

трубы, закопать их. Это критические задачи, и если в выполнении какой-либо

из них наступит задержка, выполнение проекта также задержится.

Длина этого критического пути равна ожидаемому времени завершения проекта.

В данном случае, если все задачи будут выполнены вовремя, выполнение

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

возможно, несколько задач будут выполняться одновременно. Например, один

человек может копать канавы, пока другой будет закупать трубы.

В более значительном проекте, таком как строительство небоскреба или съемка

фильма, могут содержаться тысячи задач, и критические пути при этом могут

быть совсем не очевидны.

Планирование коллективной работы

Предположим, что требуется набрать несколько сотрудников для ответов на

телефонные звонки, при этом каждый из них будет занят не весь день. При

этом нужно, чтобы суммарная зарплата была наименьшей, и нанятый коллектив

сотрудников отвечал на звонки с 9 утра до 5 вечера. В табл. 12.2 приведены

рабочие часы сотрудников, и их почасовая оплата.

@Рис. 12.18. Сеть задач сборки дождевальной установки

======342

@Таблица 12.2. Рабочие часы сотрудников и их почасовая оплата

Для построения соответствующей сети, создадим один узел для каждого

рабочего часа. Соединим эти узлы связями, каждая из которых соответствует

рабочим часам какого-либо сотрудника. Если сотрудник может работать с 9 до

11, нарисуем связь между узлом 9:00 и узлом 11:00, и присвоим этой связи

цену, равную зарплате, получаемой данным сотрудником за соответствующее

время. Если сотрудник получает 6,5 долларов в час, и отрезок времени

составляет два часа, то цена связи равна 13 долларам. На рис. 12.19

показана сеть, соответствующая данным из табл. 12.2.

Кратчайший маршрут из первого узла в последний позволяет набрать коллектив

сотрудников с наименьшей суммарной зарплатой. Каждая связь в пути

соответствует работе сотрудника в определенный промежуток времени. В данном

случае кратчайший маршрут из узла 9:00 в узел 5:00 проходит через узлы

11:00, 12:00 и 3:00. Этому соответствует следующий график работы: сотрудник

A работает с 9:00 до 11:00, сотрудник D работает с 11:00 до 12:00, затем

сотрудник A снова работает с 12:00 до 3:00 и сотрудник E работает с 3:00 до

5:00. Полная зарплата всех сотрудников при таком графике составляет 52,15

доллара.

@Рис. 12.19. Сеть графика работы коллектива

======343

Максимальный поток

Во многих сетях связи имеют кроме цены, еще и пропускную способность

(capacity). Через каждый узел сети может проходить поток (flow), который не

превышает ее пропускной способности. Например, по улицам может проехать

только определенной число машин. Сеть с заданными пропускными способностями

ее связей называется нагруженной сетью (capacitated network). Если задана

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

наибольшего возможного потока через сеть из заданного источника (source) в

заданный сток (sink).

На рис. 12.20 показана небольшая нагруженная сеть. Числа рядом со связями в

этой сети — это не цена связи, а ее пропускная способность. В этом примере

максимальный поток, равный 4, получается, если две единицы потока

направляются по пути A, B, E,F и еще две — по пути A, C, D, F.

Описанный здесь алгоритм начинается с того, что поток во всех связях равен

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

найденное решение. Алгоритм завершает работу, если нельзя улучшить

имеющееся решение.

Для поиска путей способов увеличения полного потока, алгоритм проверяет

остаточную пропускную способность (residual capacity) связей. Остаточная

пропускная способность связи между узлами I и J равна максимальному

дополнительному потоку, который можно направить из узла I в узел J,

используя связь между I и J и связь между J и I. Этот суммарный поток может

включать дополнительный поток по связи I-J, если в этой связи есть резерв

пропускной способности, или исключать часть потока из связи J-I, если по

этой связи идет поток.

Например, предположим, что в сети, соединяющей узлы A и C на рис. 12.20,

существует поток, равный 2. Так как пропускная способность этой связи равна

3, то к этой связи можно добавить единицу потока, поэтому остаточная

пропускная способность этой связи равна 1. Хотя сеть, показанная на рис.

12.20 не имеет связи C-A, для этой связи существует остаточная пропускная

способность. В данном примере, так как по связи A-C идет поток, равный 2,

то можно удалить до двух единиц этого потока. При этом суммарный поток из

узла C в узел A увеличился бы на 2, поэтому остаточная пропускная

способность связи C-A равна 2.

@Рис. 12.20. Нагруженная сеть

========344

@Рис. 12.21. Потоки в сети

Сеть, состоящая из всех связей с положительной остаточной пропускной

способностью, называется остаточной сетью (residual network). На рис. 12.21

показана сеть с рис. 12.20, каждой связи в которой присвоен поток. Для

каждой связи, первое число равно потоку через связь, а второе — ее

пропускной способности. Надпись «1/2», например, означает, что поток через

связь равен 1, и ее пропускная способность равна 2. Связи, поток через

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

На рис. 12.22 показана остаточная сеть, соответствующая потокам на рис.

12.21. Нарисованы только связи, которые действительно могут иметь

остаточную пропускную способность. Например, между узлами A и D не

нарисовано ни одной связи. Исходная сеть не содержит связи A-D или D-A,

поэтому эти связи всегда будут иметь нулевую остаточную пропускную

способность.

Одно из свойств остаточных сетей состоит в том, что любой путь,

использующий связи с остаточной пропускной способностью больше нуля,

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

Так как этот путь дает способ увеличения или расширения потока в сети, он

называется расширяющим путем (augmenting path). На рис. 12.23 показана

остаточная сеть с рис. 12.22 с расширяющим путем, нарисованным жирной

линией.

Чтобы обновить решение, используя расширяющий путь, найдем наименьшую

остаточную пропускную способность в пути. Затем скорректируем потоки в пути

в соответствии с этим значением. Например, на рис. 12.23 наименьшая

остаточная пропускная способность сетей в расширяющем пути равна 2. Чтобы

обновить потоки в сети, к любой связи I-J на пути добавляется поток 2, а из

всех обратных им связей J-I вычитается поток 2.

@Рис. 12.22. Остаточная сеть

========345

@Рис. 12.23. Расширяющий путь через остаточную сеть

Вместо того, чтобы корректировать потоки, и затем перестраивать остаточную

сеть, проще просто скорректировать остаточную сеть. Затем после завершения

работы алгоритма можно использовать результат для вычисления потоков для

связей в исходной сети.

Чтобы скорректировать остаточную сеть в этом примере, проследуем по

расширяющему пути. Вычтем 2 из остаточной пропускной способности всех

связей I-J вдоль пути, и добавим 2 к остаточной пропускной способности

соответствующей связи J-I. На рис. 12.24 показана скорректированная

остаточная сеть для этого примера.

Если больше нельзя найти ни одного расширяющего пути, то можно использовать

остаточную сеть для вычисления потоков в исходной сети. Для каждой связи

между узлами I и J, если остаточный поток между узлами I и J меньше, чем

пропускная способность связи, то поток должен равняться пропускной

способности минус остаточный поток. В противном случае поток должен быть

равен нулю.

Например, на рис. 12.24 остаточный поток из узла A в узел C равен 1 и

пропускная способность связи A-C равна 3. Так как 1 меньше 3, то поток

через узел будет равен 3 - 1 = 2. На рис. 12.25 показаны потоки в сети,

соответствующие остаточной сети на рис. 12.24.

@Рис. 12.24. Скорректированная остаточная сеть

========346

@Рис. 12.25. Максимальные потоки

Полученный алгоритм еще не содержит метода для поиска расширяющих путей в

остаточной сети. Один из возможных методов аналогичен методу коррекции

меток для алгоритма кратчайшего маршрута. Вначале поместим узел-источник в

список возможных узлов. Затем, если список возможных узлов не пуст, будем

удалять из него по одному узлу. Проверим все соседние узлы, соединенные с

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

нуля. Если соседний узел еще не был помещен в список возможных узлов,

добавить его в список. Продолжить этот процесс до тех пор, пока список

возможных узлов не опустеет.

Этот метод имеет два отличия от метода поиска кратчайшего маршрута

коррекцией меток. Во-первых, этот метод не прослеживает связи с нулевой

остаточной пропускной способностью. Алгоритм же кратчайшего маршрута

проверяет все пути, независимо от их цены.

Во-вторых, этот алгоритм проверяет все узлы не больше одного раза. Алгоритм

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

помещать их снова в список возможных узлов, если он позднее найдет более

короткий путь от корня к этому узлу. При поиске расширяющего пути нет

необходимости проверять его длину, поэтому не нужно обновлять пути и

помещать узлы назад в список возможных узлов.

Следующий код демонстрирует, как можно вычислять максимальные потоки в

программе на Visual Basic. Этот код предназначен для работы с

неориентированными сетями, похожими на те, которые использовались в других

программах примеров, описанных в этой главе. После завершения работы

алгоритма он присваивает связи цену, равную потоку через нее, взятому со

знаком минус, если поток течет в обратном направлении. Другими словами,

если сеть содержит объект, представляющий связь I-J, а алгоритм определяет,

что поток должен течь в направлении связи J-I, то потоку через связь I-J

присваивается значение, равное потоку, который должен был бы течь через

связь J-I, взятому со знаком минус. Это позволяет программе определять

направление потока, используя существующую структуру узлов.

=======347

Private Sub FindMaxFlows()

Dim candidates As Collection

Dim Residual() As Integer

Dim num_nodes As Integer

Dim id1 As Integer

Dim id2 As Integer

Dim node As FlowNode

Dim to_node As FlowNode

Dim from_node As FlowNode

Dim link As FlowLink

Dim min_residual As Integer

If SourceNode Is Nothing Or SinkNode Is Nothing _

Then Exit Sub

' Задать размер массива остаточной пропускной способности.

num_nodes = Nodes.Count

ReDim Residual(1 To num_nodes, 1 To num_nodes)

' Первоначально значения остаточной пропускной способности

' равны значениям пропускной способности.

For Each node In Nodes

id1 = node.Id

For Each link In node.Links

If link.Node1 Is node Then

Set to_node = link.Node2

Else

Set to_node = link.Node1

End If

id2 = to_node.Id

Residual(id1, id2) = link.Capacity

Next link

Next node

' Повторять до тех пор, пока больше

' не найдется расширяющих путей.

Do

' Найти расширяющий путь в остаточной сети.

' Сбросить значения NodeStatus и InLink всех узлов.

For Each node In Nodes

node.NodeStatus = NOT_IN_LIST

Set node.InLink = Nothing

Next node

' Начать с пустого списка возможных узлов.

Set candidates = New Collection

' Поместить источник в список возможных узлов.

candidates.Add SourceNode

SourceNode.NodeStatus = NOW_IN_LIST

' Продолжать, пока список возможных узлов не опустеет.

Do While candidates.Count > 0

Set node = candidates(1)

candidates.Remove 1

node.NodeStatus = WAS_IN_LIST

id1 = node.Id

' Проверить выходящие из узла связи.

For Each link In node.Links

If link.Node1 Is node Then

Set to_node = link.Node2

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31