Предыдущая страница реферата | 35  36  37  38  39  40  41  42  43  44  45 | Следующая страница реферата

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

В некоторых приложениях может потребоваться быстро найти кратчайший маршрут между всеми парами узлов в сети. Если нужно вычислить большую часть из N2 возможных путей, может быть быстрее вычислить все возможные пути вместо того, чтобы находить только те, которые нужны.
Можно записать кратчайшие маршруты, используя два двумерных массива, Dist и
InLinks. В ячейке Dist(I, J) находится кратчайший маршрут из узла I в узел
J, а в ячейке InLinks(I, J) — связь, которая ведет к узлу J в кратчайшем пути из узла I в узел J. Эти значения аналогичны значениям Dist и InLink в классе узла в предыдущем алгоритме.
Один из способов найти все кратчайшие маршруты заключается в том, чтобы построить деревья кратчайшего маршрута с корнем в каждом из узлов сети при помощи одного из предыдущих алгоритмов, и затем сохранить результаты в массивах Dists и InLinks.

========335

Другой метод вычисления всех кратчайших маршрутов последовательно строит пути, используя все больше и больше узлов. Вначале алгоритм находит все кратчайшие маршруты, которые используют только первый узел и узлы на концах пути. Другими словами, для узлов J и K алгоритм находит кратчайший маршрут между этими узлами, который использует только узел с номером 1 и узлы J и
K, если такой путь существует
Затем алгоритм находит все кратчайшие маршруты, которые используют только два первых узла. Затем он строит пути, используя первые три узла, первые четыре узла, и так далее до тех пор, пока не будут построены все кратчайшие маршруты, используя все узлы. В этот момент, поскольку кратчайшие маршруты могут использовать любой узел, алгоритм найдет все кратчайшие маршруты в сети.
Заметьте, что кратчайший маршрут между узлами J и K, использующий только первые I узлов, включает узел I, только если Dist(J, K) > Dist(J, I) +
Dist(I, K). Иначе кратчайшим маршрутом будет предыдущий кратчайший маршрут, который использовал только первые I - 1 узлов. Это означает, что когда алгоритм рассматривает узел I, требуется только проверить выполнение условия Dist(J, K) > Dist(J, I) + Dist(I, K). Если это условие выполняется, алгоритм обновляет кратчайший маршрут из узла J в узел K. Иначе старый кратчайший маршрут между этими двумя узлами остался бы таковым.

Штрафы за повороты

В некоторых сетях, в особенности сетях улиц, бывает полезно добавить штраф и запреты на повороты (turn penalties) В сети улиц автомобиль должен замедлить движение перед тем, как выполнить поворот. Поворот налево может занимать больше времени, чем поворот направо или движение прямо. Некоторые повороты могут быть запрещены или невозможны из-за наличия разделительной полосы. Эти аспекты можно учесть, вводя в сеть штрафы за повороты.

Небольшое число штрафов за повороты

Часто важны только некоторые штрафы за повороты. Может понадобиться предотвратить выполнение запрещенных или невозможных поворотов и присвоить штрафы за повороты лишь на нескольких ключевых перекрестках, не определяя штрафы для всех перекрестков в сети. В этом случае можно разбить каждый узел, для которого заданы штрафы, на несколько узлов, которые будут неявно учитывать штрафы.
Предположим, что требуется добавить один штраф за поворот на перекрестке налево и другой штраф за поворот направо. На рис. 12.12 показан перекресток, на котором требуется применить эти штрафы. Число рядом с каждой связью соответствует ее цене. Требуется применить штрафы за вход в узел A по связи L1, и затем выход из него по связям L2 или L3.
Для применения штрафов к узлу A, разобьем этот узел на два узла, по одному для каждой из покидающих его связей. В данном примере, из узла A выходят две связи, поэтому узел A разбивается на два узла A1 и A2, и связи, выходящие из узла A, заменяются соответствующими связями, выходящими из полученных узлов. Можно представить, что каждый из двух образовавшихся узлов соответствует входу в узел A и повороту в сторону соответствующей связи.

======336

@Рис. 12.12. Перекресток

Затем связь L1, входящая в узел A, заменяется на две связи, входящие в каждый из двух узлов A1 и A2. Цена этих связей равна цене исходной связи L1 плюс штрафу за поворот в соответствующем направлении. На рис. 12.13 показан перекресток, на котором введены штрафы за поворот. На этом рисунке штраф за поворот налево из узла A равен 5, а за поворот направо —2.
Помещая информацию о штрафах непосредственно в конфигурацию сети, мы избегаем необходимости модифицировать алгоритмы поиска кратчайшего маршрута. Эти алгоритмы будут находить правильные кратчайшие маршруты с учетом штрафов за повороты.
При этом придется все же слегка изменить программы, чтобы учесть разбиение узлов на несколько частей. Предположим, что требуется найти кратчайший маршрут между узлами I и J, но узел I оказался разбит на несколько узлов.
Полагая, что можно покинуть узел I по любой связи, можно создать ложный узел и использовать его в качестве корня дерева кратчайшего маршрута.
Соединим этот узел связями с нулевой ценой с каждым из узлов, получившихся после разбиения узла I. Тогда, если построить дерево кратчайшего маршрута с корнем в ложном узле, то при этом будут найдены все кратчайшие маршруты, содержащие любой из этих узлов. На рис. 12.14 показан перекресток с рис.
12.13, связанный с ложным корневым узлом.

@Рис. 12.13. Перекресток со штрафами за повороты

=======337

@Рис. 12.14. Перекресток, связанный с ложным корнем

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

Большое число штрафов за повороты

Предыдущий метод будет не слишком эффективным, если вы хотите ввести штрафы за повороты для большинства узлов в сети. Лучше будет создать совершенно новую сеть, которая будет включать информацию о штрафах.
. Для каждой связи между узлами A и B в исходной сети в новой сети создается узел AB;
. Если в исходной сети соответствующие связи были соединены, то полученные узлы также соединяются между собой. Например, предположим, что в исходной сети одна связь соединяла узлы A и B, а другая — узлы B и C.

Тогда в новой сети нужно создать связь, соединяющую узел AB с узлом BC;
. Цена новой связи складывается из цены второй связи в исходной сети и штрафа за поворот. В этом примере цена связи между узлом AB и узлом BC будет равна цене связи, соединяющей узлы B и C в исходной сети плюс штрафу за поворот при движении из узла A в узел B и затем в узел C.
На рис. 12.15 изображена небольшая сеть и соответствующая новая сеть, представляющая штрафы за повороты. Штраф за поворот налево равен 3, за поворот направо — 2, а за «поворот» прямо — нулю. Например, так как поворот из узла B в узел E — это левый поворот в исходной сети, штраф для связи между узлами BE и EF в новой сети равен 3. Цена связи, соединяющей узлы E и
F в исходной сети, равна 3, поэтому полная цена новой связи равна 3 + 3 =
6.

=======338

@Рис. 12.15. Сеть и соответствующая ей сеть со штрафами за повороты

Предположим теперь, что требуется найти для исходной сети дерево кратчайшего маршрута с корнем в узле D. Чтобы сделать это, создадим в новой сети ложный корневой узел, затем построим связи, соединяющие этот узел со всеми связями, которые покидают узел D в исходной сети. Присвоим этим связям ту же цену, которую имеют соответствующие связи в исходной сети. На рис. 12.16 показана новая сеть с рис. 12.15 с ложным корневым узлом, соответствующим узлу D. Дерево кратчайшего маршрута в этой сети нарисовано жирной линией.
Чтобы найти кратчайший маршрут из узла D в узел C, необходимо проверить все узлы в новой сети, которые соответствуют связям, заканчивающимся в узле 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

Else

Set to_node = link.Node1

End If id2 = to_node.Id

' Проверить, что residual > 0, и этот узел

' никогда не был в списке.

If Residual(id1, id2) > 0 And _ to_node.NodeStatus = NOT_IN_LIST _

Then

' Добавить узел в список. candidates.Add to_node to_node.NodeStatus = NOW_IN_LIST

Set to_node.InLink = link

End If

Next link

' Остановиться, если помечен узел-сток.

If Not (SinkNode.InLink Is Nothing) Then _

Exit Do

Loop

' Остановиться, если расширяющий путь не найден.

If SinkNode.InLink Is Nothing Then Exit Do

' Найти наименьшую остаточную пропускную способность

' вдоль расширяющего пути. min_residual = INFINITY

Set node = SinkNode

Do

If node Is SourceNode Then Exit Do id2 = node.Id

Set link = node.InLink

If link.Node1 Is node Then

Set from_node = link.Node2

Else

Set from_node = link.Node1

End If id1 = from_node.Id

If min_residual > Residual(id1, id2) Then _ min_residual = Residual(id1, id2)

Set node = from_node

Loop

' Обновить остаточные пропускные способности,

' используя расширяющий путь.

Set node = SinkNode

Do

If node Is SourceNode Then Exit Do id2 = node.Id

Set link = node.InLink

If link.Node1 Is node Then

Set from_node = link.Node2

Else

Set from_node = link.Node1

End If id1 = from_node.Id

Residual(id1, id2) = Residual(id1, id2) _

- min_residual

Residual(id2, id1) = Residual(id2, id1) _

+ min_residual

Set node = from_node

Loop

Loop ' Повторять, пока больше не останется расширяющих путей.

' Вычислить потоки в остаточной сети.

For Each link In Links id1 = link.Node1.Id id2 = link.Node2.Id

If link.Capacity > Residual(id1, id2) Then link.Flow = link.Capacity - Residual(id1, id2)

Else

' Отрицательные значения соответствуют

' обратному направлению движения. link.Flow = Residual(id2, id1) - link.Capacity

End If

Next link

' Найти полный поток.

TotalFlow = 0

For Each link In SourceNode.Links

TotalFlow = TotalFlow + Abs(link.Flow)

Next link
End Sub

=======348-350

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

Приложения максимального потока

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

Непересекающиеся пути

Большие сети связи должны обладать избыточностью (redundancy). Для заданной сети, например такой, как на рис. 12.27, может потребоваться найти число непересекающихся путей из источника к стоку. При этом, если между двумя узлами сети есть множество непересекающихся путей, все связи в которых различны, то соединение между этими узлами останется, даже если несколько связей в сети будут разорваны.
Можно определить число различных путей, используя метод вычисления максимального потока. Создадим сеть с узлами и связями, соответствующими узлам и связям в коммуникационной сети. Присвоим каждой связи единичную пропускную способность.

@Рис. 12.26. Программа Flow

=====351

@Рис. 12.27. Сеть коммуникаций

Затем вычислим максимальный поток в сети. Максимальный поток будет равен числу различных путей от источника к стоку. Так как каждая связь может нести единичный поток, то ни один из путей, использованных при вычислении максимального потока, не может иметь общей связи.
При более строгом определении избыточности можно потребовать, чтобы различные пути не имели ни общих связей, ни общих узлов. Немного изменив предыдущую сеть, можно использовать вычисление максимального потока для решения и этой задачи.
Разделим каждый узел за исключением источника и стока на два узла, соединенных связью единичной пропускной способности. Соединим первый из полученных узлов со всеми связями, входящими в исходный узел. Все связи, выходящие из исходного узла, присоединим ко второму полученному после разбиения узлу. На рис. 12.28 показана сеть с рис. 12.27, узлы на которой разбиты таким образом. Теперь найдем максимальный поток для этой сети.
Если путь, использованный для вычисления максимального потока, проходит через узел, то он может использовать связь, которая соединяет два получившихся после разбиения узла. Так как эта связь имеет единичную пропускную способность, никакие два пути, полученные при вычислении максимального потока, не могут пройти по этой связи между узлами, поэтому в исходной сети никакие два пути не могут использовать один и тот же узел.

@Рис. 12.28. Коммуникационная сеть после преобразования

======352

@Рис. 12.29. Сеть распределения работы

Распределение работы

Предположим, что имеется группа сотрудников, каждый из которых обладает определенными навыками. Предположим также, что существует ряд заданий, которые требуют привлечения сотрудника, обладающего заданным набором навыков. Задача распределения работы (work assignment) состоит в том, чтобы распределить работу между сотрудниками так, чтобы каждое задание выполнял сотрудник, имеющий соответствующие навыки.
Чтобы свести эту задачу к вычислению максимального потока, создадим сеть с двумя столбцами узлов. Каждый узел в левом столбце представляет одного сотрудника. Каждый узел в правом столбце представляет одно задание.
Затем сравним навыки каждого сотрудника с навыками, необходимыми для выполнения каждого из заданий. Создадим связь между каждым сотрудником и каждым заданием, которое он способен выполнить, и присвоим всем связям единичную пропускную способность.
Создадим узел-источник и соединим его с каждым из сотрудников связью единичной пропускной способности. Затем создадим узел-сток и соединим с ним каждое задание, снова при помощи связей с единичной пропускной способностью. На рис. 12.29 показана соответствующая сеть для задачи распределения работы с четырьмя сотрудниками и четырьмя заданиями.
Теперь найдем максимальный поток из источника в сток. Каждая единица потока должна пройти через один узел сотрудника и один узел задания. Этот поток представляет распределение работы для этого сотрудника.

@Рис. 12.30. Программа Work

=======353

Если сотрудники обладают соответствующими навыками для выполнения всех заданий, то вычисления максимального потока распределят их все. Если невозможно выполнить все задания, то в процессе вычисления максимального потока работа будет распределена так, чтобы было выполнено максимально возможное число заданий.
Программа Work использует этот алгоритм для распределения работы между сотрудниками. Введите фамилии сотрудников и их навыки в текстовом поле слева, а задания, которые требуется выполнить и требующиеся для них навыки в текстовом поле посередине. После того, как вы нажмете на кнопку Go
(Начать), программа распределит работу между сотрудниками, используя для этого сеть максимального потока. На рис. 12.30 показано окно программы с полученным распределением работы.

Резюме

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

======354

Глава 13. Объектно-ориентированные методы

Использование функций и подпрограмм позволяет программисту разбить код большой программы на части. Массивы и определенные пользователем типы данных позволяют сгруппировать элементы данных так, чтобы упросить работу с ними.
Классы, которые впервые появились в 4-й версии Visual Basic, позволяют программисту по-новому сгруппировать данные и логику работы программы.
Класс позволяет объединить в одном объекте данные и методы работы с ними.
Этот новый подход к управлению сложностью программ позволяет взглянуть на алгоритмы с другой точки зрения.
В этой главе рассматриваются вопросы объектно-ориентированного программирования, возникающие при применении классов Visual Basic. В ней описаны преимущества объектно-ориентированного программирования (ООП) и показано, какую выгоду можно получить от их применения в программах на языке Visual Basic. Затем в главе рассматривается набор полезных объектно- ориентированных примеров, которые вы можете использовать для управления сложностью ваших приложений.

Преимущества ООП

К традиционным преимуществам объектно-ориентированного программирования относятся инкапсуляция или скрытие (encapsulation), полиморфизм
(polymorphism) и повторное использование (reuse). Реализация их в классах
Visual Basic несколько отличается от того, как они реализованы в других объектно-ориентированных языках. В следующих разделах рассматриваются эти преимущества ООП и то, как можно ими воспользоваться в программах на Visual
Basic.

Инкапсуляция

Объект, определенный при помощи класса, заключает в себе данные, которые он содержит. Другие части программы могут использовать объект для оперирования его данными, не зная о том, как хранятся или изменяются значения данных.
Объект предоставляет открытые (public) процедуры, функции, и процедуры изменения свойств, которые позволяют программе косвенно манипулировать или просматривать данные. Так как при этом данные являются абстрактными с точки зрения программы, это также называется абстракцией данных (data abstraction).
Инкапсуляция позволяет программе использовать объекты как «черные ящики».
Программа может использовать открытые методы объекта для проверки и изменения значений без необходимости разбираться в том, что происходит внутри черного ящика.

=========355

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

Обеспечение инкапсуляции

Для обеспечения инкапсуляции класс должен предотвращать непосредственный доступ к своим данным. Если переменная в классе объявлена как открытая, то другие части программы смогут напрямую изменять и считывать данные из нее.
Если позднее представление данных изменится, то любые части программы, которые непосредственно взаимодействуют с данными, также должны будут измениться. При этом теряется преимущество инкапсуляции.
Чтобы обеспечить доступ к данным, класс должен использовать процедуры для работы со свойствами. Например, следующие процедуры позволяют другим частям программы просматривать и изменять значение DegreesF объекта Temperature.

Private m_DegreesF As Single ' Градусы Фаренгейта.

Public Property Get DegreesF() As Single

DegreesF = m_DegreesF
End Property

Public Property Let DegreesF(new_DegreesF As Single) m_DegreesF = new_DegreesF
End Property

Различия между этими процедурами и определением m_DegreesF как открытой переменной пока невелики. Тем не менее, использование этих процедур позволяет легко изменять класс в дальнейшем. Например, предположим, что вы решите измерять температуру в градусах Кельвина, а не Фаренгейта. При этом можно изменить класс, не затрагивая остальных частей программы, в которых используются процедуры свойства DegreesF. Можно также добавить код для проверки ошибок, чтобы убедиться, что программа не попытается передать объекту недопустимые значения.

Private m_DegreesK As Single ' Градусы Кельвина.

Public Property Get DegreesF() As Single

DegreesF = (m_DegreesK - 273.15) * 1.8
End Property

Public Property Let DegreesF(ByVal new_DegreesF As Single)
Dim new_value As Single

new_value = (new_DegreesF / 1.8) + 273.15

If new_value < 0 Then

' Сообщить об ошибке - недопустимое значении.

Error.Raise 380, "Temperature", _

"Температура должна быть неотрицательной."

Else m_DegreesK = new_value

End If
End Property

======357

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

Полиморфизм

Второе преимущество объектно-ориентированного программирования — это полиморфизм (polymorphism), что означает «имеющий множество форм». В Visual
Basic это означает, что один объект может иметь различный формы в зависимости от ситуации. Например, следующий код представляет собой подпрограмму, которая может принимать в качестве параметра любой объект.
Объект obj может быть формой, элементом управления, или объектом определенного вами класса.

Private Sub ShowName(obj As Object)

MsgBox TypeName(obj)
End Sub

Полиморфизм позволяет создавать процедуры, которые могут работать буквально со всеми типами объектов. Но за эту гибкость приходится платить. Если определить обобщенный (generic) объект, как в этом примере, то Visual Basic не сможет определить, какие типы действий сможет выполнять объект, до запуска программы.

========357

Если Visual Basic заранее знает, с объектом какого типа он будет иметь дело, он может выполнить предварительные действия для того, чтобы более эффективно использовать объект. Если используется обобщенный (generic) объект, то программа не может выполнить подготовки, и в результате этого потеряет в производительности.
Программа Generic демонстрирует разницу в производительности между объявлением объектов как принадлежащих к определенному типу или как обобщенных объектов. Тест выполняется одинаково, за исключением того, что в одном из случаев объект определяется, как имеющий тип Object, а не тип
SpecificClass. При этом установка значения данных объекта с использованием обобщенного объекта выполняется в 200 раз медленнее.

Private Sub TestSpecific()
Const REPS = 1000000 ' Выполнить миллион повторений.

Dim obj As SpecificClass
Dim i As Long
Dim start_time As Single
Dim stop_time As Single

Set obj = New SpecificClass start_time = Timer

For i = 1 To REPS obj.Value = I

Next i stop_time = Timer

SpecificLabel.Caption = _

Format$(1000 * (stop_time - start_time) / REPS, "0.0000")
End Sub

Зарезервированное слово Implements

В 5-й версии Visual Basic зарезервированное слово Implements (Реализует) позволяет программе использовать полиморфизм без использования обобщенных объектов. Например, программа может определить интерфейс Vehicle (Средство передвижения), Если классы Car (Автомобиль) и Truck (Грузовик) оба реализуют интерфейс Vehicle, то программа может использовать для выполнения функций интерфейса Vehicle объекты любого из двух классов.
Создадим вначале класс интерфейса, в котором определим открытые переменные, которые он будет поддерживать. В нем также должны быть определены прототипы открытых процедур для всех методов, которые он будет поддерживать.
Например, следующий код демонстрирует, как класс Vehicle может определить переменную Speed (Скорость) и метод Drive (Вести машину):

Public Speed Long

Public Sub Drive()

End Sub

=======358

Теперь создадим класс, который реализует интерфейс. После оператора Option
Explicit в секции Declares добавляется оператор Implements определяющий имя класса интерфейса. Этот класс должен также определять все необходимые для работы локальные переменные.
Класс Car реализует интерфейс Vehicle. Следующий код демонстрирует, как в нем определяется интерфейс и закрытая (private) переменная m_Speed:

Option Explicit

Implements Vehicle

Private m_Speed As Long

Когда к классу добавляется оператор Implements, Visual Basic считывает интерфейс, определенный указанным классом, а затем создает соответствующие заглушки в коде класса. В этом примере Visual Basic добавит новую секцию
Vehicle в исходный код класса Car, и определит процедуры let и get свойства
Vehicle_Speed для представления переменной Speed, определенной в интерфейсе
Vehicle. В процедуре let Visual Basic использует переменную RHS, которая является сокращением от Right Hand Side (С правой стороны), в которой задается новое значение переменной.
Также определяется процедура Vehicle_Drive. Чтобы реализовать функции этих процедур, нужно написать код для них. Следующий код демонстрирует, как класс Car может определять процедуры Speed и Drive.

Private Property Let Vehicle_Speed(ByVal RHS As Long) m_Speed = RHS
End Property

Private Property Get Vehicle_Speed() As Long

Vehicle_Speed = m_Speed
End Property

Private Sub Get Vehicle_Drive()

' Выполнить какие-то действия.

:
End Property

После того, как интерфейс определен и реализован в одном или нескольких классах, программа может полиморфно использовать элементы в этих классах.
Например, допустим, что программа определила классы Car и Track, которые оба реализуют интерфейс Vehicle. Следующий код демонстрирует, как программа может проинициализировать значения переменной Speed для объекта Car и объекта Truck.

Dim obj As Vehicle

Set obj = New Car obj.Speed = 55

Set obj = New Truck obj .Speed =45

==========359

Ссылка obj может указывать либо на объект Car, либо на объект Truck. Так как в обоих этих объектах реализован интерфейс Vehicle, то программа может оперировать свойством obj.Speed независимо от того, указывает ли ссылка obj на Car или Truck.
Так как ссылка obj указывает на объект, который реализует интерфейс
Vehicle, то Visual Basic знает, что этот объект имеет процедуры, работающие со свойством Speed. Это означает, что он может выполнять вызовы процедур свойства Speed более эффективно, чем это было бы в случае, если бы obj была ссылкой на обобщенный объект.
Программа Implem является доработанной версией программы описанной выше программы Generic. Она сравнивает скорость установки значений с использованием обобщенных объектов, определенных объектов и объектов, которые реализуют интерфейс. В одном из тестов на компьютере с процессором
Pentium с тактовой частотой 166 МГц, программе потребовалось 0,0007 секунды для установки значений при использовании определенного типа объекта. Для установки значений при использовании объекта, реализующего интерфейс, потребовалось 0,0028 секунды (в 4 раза больше). Для установки значений при использовании обобщенного объекта потребовалось 0,0508 секунды (в 72 раза больше). Использование интерфейса является не таким быстрым, как использование ссылки на определенный объект, но намного быстрее, чем использование обобщенных объектов.

Наследование и повторное использование

Процедуры и функции поддерживают повторное использование (reuse). Вместо того, чтобы каждый раз писать код заново, можно поместить его в подпрограмму, тогда вместо блока кода можно просто подставить вызов подпрограммы.
Аналогично, определение процедуры в классе делает ее доступной во всей программе. Программа может использовать эту процедуру, используя объект, который является экземпляром класса.
В среде программистов, использующих объектно-ориентированный подход, под повторным использованием обычно подразумевается нечто большее, а именно наследование (inheritance). В объектно-ориентированных языках, таких как
C++ или Delphi, один класс может порождать (derive) другой. При этом второй класс наследует (inherits) всю функциональность первого класса. После этого можно добавлять, изменять или убирать какие-либо функции из класса- наследника. Это также является формой повторного использования кода, поскольку при этом программисту не нужно заново реализовать функции родительского класса, для того, чтобы использовать их в классе-наследнике.
Хотя Visual Basic и не поддерживает наследование непосредственно, можно добиться примерно тех же результатов, используя ограничение (containment) или делегирование (delegation). При делегировании объект из одного класса содержит экземпляр класса из другого объекта, и затем передает часть своих обязанностей заключенному в нем объекту.
Например, предположим, что имеется класс Employee, который представляет данные о сотрудниках, такие как фамилия, идентификационный номер в системе социального страхования и зарплата. Предположим, что нам теперь нужен класс
Manager, который делает то же самое, что и класс Employee, но имеет еще одно свойство secretary (секретарь).
Для использования делегирования, класс Manager должен включать в себя закрытый объект типа Employee с именем m_Employee. Вместо прямого вычисления значений, процедуры работы со свойствами фамилии, номера социального страхования и зарплаты передают соответствующие вызовы объекту m_Employee. Следующий код демонстрирует, как класс Manager может оперировать процедурами свойства name (фамилия):

==========360

Private m_Employee As New Employee

Property Get Name() As String

Name = m_Employee.Name
End Property

Property Let Name (New_Name As String) m_Employee.Name = New_Name
End Property

Рекомендуем скачать другие рефераты по теме: доклад по химии, конспект зима.





Предыдущая страница реферата | 35  36  37  38  39  40  41  42  43  44  45 | Следующая страница реферата