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

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 (Реализует)

позволяет программе использовать полиморфизм без использования обобщенных

Страницы: 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