Programmirovanie_i_osnovyi_algo

Рис. 76. Разделение исходного сегмента на подсегменты

J. Примеры, Пример 1 для общего случая представлен на рис.

77.

Примеры 2, 3 и 4 (частные случаи) приведены на рис. 78. Их анализ предлагается выполнить самостоятельно.

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

это выгоднее начать с меньшего сегмента (см. обоснование ниже) Поэтому

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

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

261

в) Больший из полученных сегментов (левый) запоминаем в стеке для последующего разбиения. Работа с правым (меньшим) сегментом закончена, так как в нем один элемент. Извлекаем из стека и разбиваем очередной сегмент

left right

г) Извлекаем из стека и разбиваем очередной сегмент

элемент).

д) Извлекаем из стека и разбиваем очередной сегмент left right

Прод. рис. 77 •

Какой должна быть глубина стека М? Величина М зависит от порядка разбиения полученных сегментов. Н. Вирт показал, что ес­ ли в стек помещать более длинный из получившихся сегментов, а с коротким сегментом сразу "расправляться", то

М = \0g2isize),

где size - размер сортируемого массива.

262

, median=arr[(left+right)/2] Рис. 78. Частные случаи для сортировки Хоора

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

Л/ = 1 + \og2(size).

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

Прототипы функций для занесения границ сегментов в стек (Push) и извлечения границ сегментов из стека (Pop), определения функций и примеры их вызова даны в примере программы из подразд. 15.2. Эти функции являются служебными для нерекурсивной функции Quicksort. Подобные функции, как указывалось выше, на­ зывают неинтерфейсными функциями.

5.Нерекурсивная сортировка Хоора, Прототип функции Quicksort, ее определение и пример вызова даны в примере про­ граммы из подразд. 15.2. Эта функция является интерфейсной функ­ цией и может использоваться для сортировки массива.

6.Рекурсивная сортировка Хоора.

263

копии параметров рекурсивной функции, передаваемых по значению; адреса аргументов из вызова рекурсивной функции, соответст­

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

возвращаемое значение, если оно имеется.

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

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

С учетом этих особенностей и была спроектирована рекурсив­ ная сортировка Хоора. Прототип функции QuickSortl для рекурсив­ ной сортировки Хоора, ее определение и пример вызова даны в примере программы из подразд. 15.2. Эта функция является интер­ фейсной и предназначена для сортировки массивов. Для разделения исходного сегмента на подсегменты функция Quicksort 1 использует служебную рекурсивную функцию Split. Ее прототип, определение и пример вызова даны также в примере программы из подразд. 15.2. Функция Split является рекурсивной и именно при ее разработке бы­ ли учтены перечисленные выше важные особенности рекурсивных функций.

15.9. Сравнительные показатели производительности различных методов сортировки массивов

Приводимые ниже в табл. 29 данные получены для программы, написанной на языке Паскаль (ЭВМ SDS6400) для неупорядоченных массивов.

Из приведенных в таблице данных следует, в частности, что даже для массива относительно небольшого размера из 512 элемен­ тов:

1. Худшая по производительности из простых сортировок (простая сортировка обменом) работает в 35 раз медленнее быстрой сортировки Хоора.

2. Самая быстрая из простых сортировок (простая сортировка вставками) работает медленнее в 4,2 раза, чем самая худшая по про-

264

16. ГРАФЫТРАНСПОРТНАЯ ЗАДАЧА (ЗАДАЧА КОММИВОЯЖЕРА)

16,1. Терминология

Граф - это пара (К, /?), где V - конечное непустое множество вершин, а R -множество неупорядоченных пар <а, Ь> вершин из множества К, называемых ребрами. Говорят, что ребро г — <а, Ь> соединяет вершины "а" и "6". Ребро 'V" и вершина "<з", ребро 'V" и вершина "Z?" называются инцидентными. Вершины "а" и "6" являют­ ся смеэюными. Ребра, инцидентные одной и той же вершине, также называют смеэюными. Степень вершины равна числу ребер, инци­ дентных ей.

Для простоты будем ограничиваться классом графов без пе­ тель, т.е. без таких ребер <а, 6>, что а = Ь.

Пример графа._ Города и связывающие их дороги можно пред­ ставить с помощью графа, показанного на рис. 79.

Рис. 79. Пример графа, представляющего города и дороги между ними

В данном примере граф задает объекты (города) и отношения между объектами (дороги). В приведенном графе содержатся пять вершин и семь ребер. Степень вершин 1, 2, 3, 4 равна трем, а вершины 5 - двум.

В ориентированном или направленном графе каждое ребро имеет направление (например, дорога с односторонним движением, рис. 80 а). В направленном графе отношения не симметричны.

В неориентированном графе отсутствует ориентация ребер (рис. 80 б), т.е.

266

{a,b) G R тогда и только тогда, когда {Ь,а) е R

ptGpoM. Длина пути Vo,v,,...,v„ равна количеству его ребер, т.е. п. Для примера, показанного на рис. 76, путь 1-4-3-2 между вершинами 1 и 2 имеет длину 3.

Путь замкнут, если v^ =v„. Путь называется простым, если все его вершины различны. Замкнутый путь, в котором все ребра раз­ личны, называется циклом. Простой цикл - это замкнутый путь, все вершины которого, кроме вершин VQ И V„, попарно различны.

Расстояние между двумя вершинами - это длина кратчайшего пути, соединяющего эти вершины. Например, на рис. 79 расстояние

W = f{R), определяющая вес или длину ребра в графе. Обычно взве­ шенные графы являются неориентированными, а веса ребер - поло­ жительными. Пример взвешенного неориентированного графа при­ веден на рис. 81.

В этом примере в качестве веса ребра можно выбрать расстоя­ ние между городами. Из примера со всей очевидностью следует, что при поиске пути с суммарным минимальным весом не обязательно, что минимальный вес имеет путь с минимальным числом ребер (в примере лучшим путем от start ло finish является путь по трем доро­ гам 1-4-5-2 с суммарным весом 30.0).

267

10.0 Рис. 81. Пример взвешенного неориентированного графа

16.2. Формы задания графа

Используются две основные формы:

1. С помощью матрицы инциденций (соединений):

а) для неориентированного взвешенного графа (рис. 82 а) мггт- риц|^ инциденций имеет число строк и столбцов, равное числу вер­ шин, и симметрична;

б) для ориентированного взвешенного графа матрица соедине­ ний не симметрична (рис. 82 б).

};

268

Задание графа на основе списка ребер удобйо свести в одну структуру:

} ;

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

1. Использование матрицы соединений требует хранения в па­ мяти NumTop*NumTop элементов.

2.Использование списка ребер требует хранения в памяти Ъ"^NumArc элементов.

3.При Ъ'^NumArc < NumTop"^NumTop эффективнее использо­ вать задание графа с помощью списка ребер.

4.Использование списка ребер алгоритмичнее. Это означает, что алгоритмы решения задач с использованием графов, заданных списком ребер, проще и эффективнее.

Для примера, приведенного на рис. 81, информация для списка ребер имеет следующий вид:

Здесь в первой строке 1 и 2 - номера вершин, а 80.0 - вес соединяю­ щего их ребра.

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

в общем случае путей из вершины start до вершины finish мо­ жет быть несколько, но только один путь будет наилучшим (в част­ ном случае, путь может вообще не существовать, например, в несвя­ занном графе, или может быть несколько наилучших, эквивалент-

269