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

их двумя новым, так чтобы маршрут при этом оставался замкнутым. На рис.

8.10 показано как изменяется маршрут, если отрезки X1 и X2 заменить

отрезками Y1 и Y2. Аналогичные стратегии последовательных приближений

рассматривают замену трех или более отрезков пути одновременно.

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

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

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

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

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

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

Задача о пожарных депо

Задача о пожарных депо (firehouse problem) формулируется так: если задана

сеть, некоторое число F, и расстояние D, то существует ли способ размесить

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

чем на расстоянии D от ближайшего пожарного депо?

@Рис. 8.10. Последовательное приближение при решении задачи коммивояжера

========221

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

ветвь определяет местоположение соответствующего пожарного депо в сети.

Корневой узел будет иметь N ветвей, соответствующих размещению первого

пожарного депо в одном из N узлов сети. Узлы на следующем уровне дерева

будут иметь N – 1 ветвей, соответствующих размещению второго пожарного депо

в одном из оставшихся N – 1 узлов. Если всего существует F пожарных депо,

то высота дерева решений будет равна F, и оно будет содержать порядка O(NF)

узлов. В дереве будет N * (N – 1) * … * (N – F) листьев, соответствующих

разным вариантам размещения пожарных депо в сети.

Так же, как и в задачах о выполнимости, разбиении, и поиске Гамильтонова

пути, в этой задаче нужно дать положительный или отрицательный ответ на

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

частичные или приближенные решения.

Можно, тем не менее, использовать разновидность метода ветвей и границ,

если на ранних этапах решения определить, какие из вариантов размещения

пожарных депо не приводят к решению. Например, бессмысленно помещать

очередное депо между двумя другими, расположенными рядом. Если все узлы на

расстоянии D от нового пожарного депо уже находятся в пределах этого

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

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

достаточно много времени, и задача все еще остается очень сложной.

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

обобщенный случай задачи о пожарных депо. В обобщенном случае задача

формулируется так: если задана сеть и некоторое число F, в каких узлах сети

нужно поместить F пожарных депо, чтобы наибольшее расстояние от любого узла

до пожарного депо было минимальным?

Так же, как и обобщенных случаях других задач, для поиска частичного и

приближенного решений этой задачи можно использовать метод ветвей и границ

и эвристический подход. Это несколько упрощает проверку дерева решений.

Хотя дерево решений все еще остается огромным, можно по крайней мере найти

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

Краткая характеристика сложных задач

Во время чтения предыдущих параграфов вы могли заметить, что существует два

варианта многих сложных задач. Первый вариант задачи задает вопрос:

«Существует ли решение задачи, удовлетворяющее определенным условиям?».

Второй, более общий случай дает ответ на вопрос: «Какое решение задачи

будет наилучшим?»

Обе задачи при этом имеют одинаковое дерево решений. В первом случае дерево

решений просматривается до тех пор, пока не будет найдено какое-либо

решение. Так как для этих задач не существует частичного или приближенного

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

эвристический подход или метод ветвей и границ. Обычно всего лишь несколько

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

трудоемкий процесс.

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

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

наилучшего решения задачи, поэтому не поможет получить точное решение для

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

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

==========222

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

Обычно вопрос о существовании Гамильтонова пути возникает, если сеть

разрежена, и сложно сказать, существует ли такой путь. Вопрос о кратчайшем

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

существует множество таких путей. В этом случае легко найти частичные

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

Резюме

Можно использовать деревья решений для моделирования различных задач. Поиск

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

дереве. К сожалению, деревья решений для многих интересных задач имеют

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

только для очень небольших задач.

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

деревьях решений, что позволяет получать точное решение для задач гораздо

большего размера.

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

границ не может помочь. В этом случае, для получения приблизительного

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

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

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

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

==========223

Глава 9. Сортировка

Сортировка — одна из наиболее активно изучаемых тем в компьютерных

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

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

нести больше смысла, если его отсортировать каким-либо образом. Часто

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

Во-вторых, многие алгоритмы сортировки являются интересными примерами

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

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

массиве.

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

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

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

составляет порядка O(N * log(N)). Некоторые алгоритмы достигают

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

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

сравнений, которые выполняются быстрее, чем за время порядка O(N * log(N)).

Общие соображения

В этой главе описаны некоторые алгоритмы сортировки, которые ведут себя по-

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

опережает быструю сортировку по скорости работы, если сортируемые элементы

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

расположены хаотично.

Особенности каждого алгоритма описаны в параграфе, в котором он

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

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

сортировки.

Таблицы указателей

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

подобие структуры данных. Этот процесс может быть быстрым или медленным в

зависимости от типа элементов. Перемещение целого числа на новое положение

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

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

список данных о сотруднике, содержащий тысячи байт информации, копирование

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

========225

Для повышения производительности при сортировке больших объектов можно

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

индексов. В этой таблице находятся ключи к записям и индексы элементов

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

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

определяемый следующей структурой:

Type Emloyee

ID As Integer

LastName As String

FirstName As String

End Type

‘ Выделить память под записи.

Dim EmloyeeData(1 To 10000)

Чтобы отсортировать сотрудников по идентификационному номеру, нужно создать

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

Индекс элемента показывает, какая запись в массиве EmployeeData содержит

соответствующие данные.

Type IdIndex

ID As Integer

Index As Integer

End Type

‘ Таблица индексов.

Dim IdIndexData(1 To 10000)

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

первую запись данных, второй — на вторую, и т.д.

For i = 1 To 10000

IdIndexData(i).ID = EmployeeData(i).ID

IdIndexData(i).Index = i

Next i

Затем, отсортируем таблицу индексов по идентификационному номеру ID. После

этого, поле Index в каждом элементе IdIndexData указывает на

соответствующую запись данных. Например, первая запись в отсортированном

списке — это EmployeeData(IdIndexData(1).Index). На рис. 9.1 показана

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

=======226

@Рисунок 9.1. Сортировка с помощью таблицы индексов

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

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

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

упорядочивающую сотрудников по фамилии. Подобно этому списки со ссылками

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

добавлении или удалении записи необходимо обновлять каждую таблицу индексов

независимо.

Помните, что таблицы индексов занимают дополнительную память. Если создать

по таблице индексов для каждого из полей данных, объем занимаемой памяти

более чем удвоится.

Объединение и сжатие ключей

Иногда можно хранить ключи списка в комбинированной или сжатой форме.

Например, можно было бы объединить (combine) в программе два поля,

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

ускорить сравнение. Обратите внимание на различия между двумя следующими

фрагментами кода, которые сравнивают две записи о сотрудниках:

‘ Используя разные ключи.

If emp1.LastName > emp2.LastName Or _

(emp1.LastName = emp2.LastName And _

And emp1.FirstName > emp2.FirstName) Then

DoSomething

‘ Используя объединенный ключ.

If emp1.CominedName > emp2.CombinedName Then

DoSomething

========227

Также иногда можно сжимать (compress) ключи. Сжатые ключи занимают меньше

места, уменьшая размер таблиц индексов. Это позволяет сортировать списки

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

списке, и часто также ускоряет сравнение элементов.

Одни из методов сжатия строк — кодирование их целыми числами или данными

другого числового формата. Числовые данные занимают меньше места, чем

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

быстрее, чем сравнение двух строк. Конечно, строковые операции неприменимы

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

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

заглавных латинских букв. Можно считать, что каждый символ — это число по

основанию 27. Необходимо использовать основание 27, чтобы представить 26

букв и еще одну цифру для обозначения конца слова. Без отметки конца слова,

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

цифры, а в строке B — одна.

Код по основанию 27 для строки из трех символов дает формула 272 * (первая

буква - A + 1) + 27 * (вторая буква - A + 1) + 27 * (третья буква - A + 1).

Если в строке меньше трех символов, вместо значения (третья буква - A + 1)

подставляется 0. Например, строка FOX кодируется так:

272 * (F - A + 1) + 27 * (O - A + 1) + (X - A +1) = 4803

Строка NO кодируется следующим образом:

272 * (N - A + 1) + 27 * (O - A + 1) + (0) = 10.611

Заметим, что 10.611 больше 4803, поскольку NO > FOX.

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

в формате long и строки из 10 букв — как число в формате double. Две

следующие процедуры конвертируют строки в числа в формате double и обратно:

Const STRING_BASE = 27

Const ASC_A = 65 ‘ ASCII код для символа "A".

‘ Преобразование строки с число в формате double.

‘

‘ full_len — полная длина, которую должна иметь строка.

‘ Нужна, если строка слишком короткая (например "AX" —

‘ это строка из трех символов).

Function StringToDbl (txt As String, full_len As Integer) As Double

Dim strlen As Integer

Dim i As Integer

Dim value As Double

Dim ch As String * 1

strlen = Len(txt)

If strlen > full_len Then strlen = full_len

value = 0#

For i = 1 To strlen

ch = Mid$(txt, i, 1)

value = value * STRING_BASE + Asc(ch) - ASC_A + 1

Next i

For i = strlen + 1 To full_len

value = value * STRING_BASE

Next i

End Function

‘ Обратное декодирование строки из формата double.

Function DblToString (ByVal value As Double) As String

Dim strlen As Integer

Dim i As Integer

Dim txt As String

Dim Power As Integer

Dim ch As Integer

Dim new_value As Double

txt = ""

Do While value > 0

new_value = Int(value / STRING_BASE)

ch = value - new_value * STRING_BASE

If ch <> 0 Then txt = Chr$(ch + ASC_A - 1) + txt

value = new_value

Loop

DblToString = txt

End Function

===========228

В табл. 9.1 приведено время выполнения программой Encode сортировки 2000

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

частотой 90 МГц. Заметим, что результаты похожи для каждого типа

кодирования. Сортировка 2000 чисел в формате double занимает примерно

одинаковое время независимо от того, представляют ли они строки из 3 или 10

символов.

========229

@Таблица 9.1. Время сортировки 2000 строк с использованием различных

кодировок в секундах

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

Строку из заглавных букв и цифр можно закодировать по основанию 37 вместо

27. Код буквы A будет равен 1, B — 2, … , Z — 26, код 0 будет 27, … , и 9 —

36. Строка AH7 будет кодироваться как 372 * 1 + 37 * 8 + 35 = 1700.

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

закодировать числом типа integer, long или double будет соответственно

короче. При основании равном 37, можно закодировать строку из 2 символов в

числе формата integer, из 5 символов в числе формата long, и 10 символов в

числе формата double.

Примеры программ

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

демонстрирует большинство алгоритмов, описанных в этой главе. Сортировка

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

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

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

формате long и сортирует его, используя выбранный алгоритм. Вначале

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

компьютер может выполнять операции сортировки. Это особенно важно для

медленных алгоритмов сортировки вставкой, сортировки вставкой с

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

сортировки.

Некоторые алгоритмы перемещают большие блоки памяти. Например, алгоритм

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

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

программе, написанной на Visual Basic, приходится использовать цикл For.

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

List(j) до List(max_sorted) для того, чтобы освободить место под новый

элемент в позиции List(j):

For k = max_sorted To j Step -1

List(k + 1) = List(k)

Next k

List(j) = next_num

==========230

Интерфейс прикладного программирования системы Windows включает две

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

памяти. Программы, скомпилированные 16-битной версией компилятора Visual

Basic 4, могут использовать функцию hmemcopy. Программы, скомпилированные

32-битными компиляторами Visual Basic 4 и 5, могут использовать функцию

RtlMoveMemory. Обе функции принимают в качестве параметров конечный и

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

код показывает, как объявлять эти функции в модуле .BAS:

#if Win16 Then

Declare Sub MemCopy Lib "Kernel" Alias _

"hmemcpy" (dest As Any, src As Any, _

ByVal numbytes As Long)

#Else

Declare Sub MemCopy Lib "Kernel32" Alias _

"RtlMoveMemory" (dest As Any, src As Any, _

ByVal numbytes As Long)

#EndIf

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

использовать эти функции для копирования блоков памяти. Этот код выполняет

те же действия, что и цикл For, приведенный выше, но делает это намного

быстрее:

If max_sorted >= j Then _

MemCopy List(j + 1), List(j), _

Len(next_num) * (max_sorted - j + 1)

List(j) = next_num

Программа FastSort аналогична программе Sort, но она использует функцию

MemCopy для ускорения работы некоторых алгоритмов. В программе FastSort

алгоритмы, использующие функцию MemCopy, выделены синим цветом.

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