🗊Презентация Методы решения оптимизационных задач

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

Введение Примеры дискретных оптимизационных задач задача о кратчайшем пути: Пусть имеется несколько городов и известны попарные расстояния между соседними городами. При этом два города считаются соседними, если есть дорога, их соединяющая, и не проходящая через какой-либо другой город. Требуется найти кратчайший путь между некоторой парой городов; задача оптимального назначения: Пусть имеется n станков и n деталей, каждую деталь можно обрабатывать на любом станке, но время обработки детали на одном станке может отличаться от времени ее обработки на другом. Пусть эти времена для каждой пары «станок — деталь» заданы. Требуется так организовать производство деталей, т.е. разместить их по станкам, чтобы суммарное время работы было наименьшим ; задача коммивояжера Путешественник хочет объехать n городов, побывав в каждом ровно по одному разу, и вернуться в исходный, затратив при этом минимальную сумму на поездку. Затраты па поездку складываются из затрат на переезды между парами городов, а эти затраты заранее известны.

В каждой задаче имеется лишь конечное число вариантов, из которых требуется осуществить выбор (путей между городами, способов распределения деталей по станкам, маршрутов передвижения путешественника). В каждой задаче имеется лишь конечное число вариантов, из которых требуется осуществить выбор (путей между городами, способов распределения деталей по станкам, маршрутов передвижения путешественника). Каждому варианту выбора сопоставлена некоторая числовая характеристика (длина пути, суммарное время работы, стоимость поездки). Требуется выбрать вариант, числовая характеристика которого достигает экстремума. Методы решения подобных задач полный перебор (поочередно пересмотреть все варианты и выбрать требуемый); дискретная оптимизация.

Типы задач: массовые и индивидуальные задачи. Типы задач: массовые и индивидуальные задачи. Все вышеприведенные примеры дают образцы именно массовых задач. Индивидуальная задача получается из массовой путем фиксации набора условий. Например, индивидуальная задача коммивояжера получается из массовой, если зафиксировано число городов и определены затраты на переезды между всеми парами городов. С каждой конкретной массовой задачей (в дальнейшем просто задачей) будем связывать некоторое число (или несколько чисел), называемое ее размером, которое выражает меру количества входных данных. Например, размером задачи коммивояжера естественно считать число городов n, которые собирается посетить путешественник.

Говорят, что алгоритм решает некоторую массовую задачу, если он решает любую ее индивидуальную задачу. Говорят, что алгоритм решает некоторую массовую задачу, если он решает любую ее индивидуальную задачу. Для оценки качества алгоритмов имеется ряд критериев. Одним из важнейших таких критериев является понятие вычислительной сложности (или просто сложности) алгоритма. Неформально, под сложностью алгоритма решения массовой задачи будем понимать максимально возможное число шагов, выполняемых алгоритмом для решения любой из индивидуальных задач, вычисленное как функция размерности задачи. Под шагом алгоритма будем понимать выполнение "простой" операции, обычно аппаратно реализованной на любой ЭВМ, а именно любой арифметической операции, операции сравнения, пересылки, косвенной адресации и т.п. При этом будем рассматривать асимптотическую сложность алгоритма, (а не точную сложность, зависящую от конкретного вида машинных команд), т.е. порядок роста числа шагов алгоритма при неограниченном росте размерности задачи. При сравнении скорости роста двух неотрицательных функций f(n) и g(n) будем использовать следующие понятия.

При сравнении скорости роста двух неотрицательных функций f(n) и g(n) будем использовать следующие понятия. При сравнении скорости роста двух неотрицательных функций f(n) и g(n) будем использовать следующие понятия. Будем говорить, что функция f(n) имеет порядок роста не более чем g(n) (запись: f(n) = О(g(n))), если существуют константы с, N > 0 такие, что f(n) < c·g(n) для всех n > N. Говорят, что функция f(n) имеет порядок роста не менее чем g(n) (запись: f(n) = Ω (g(n)) ), если существуют константы с, N > 0 такие, что f(n) ≥ c g(n) для всех n > N.

Например, справедливы следующие соотношения: Например, справедливы следующие соотношения: log2n = О(n); n2 = О(2n); n = Ω (log2n): На практике алгоритм решения некоторой задачи считается достаточно хорошим, если сложность этого алгоритма есть O(n·p) при некотором р > 0. В этом случае говорят, что задача полиномиально разрешима, или, что то же самое, задача может быть решена за полиномиальное время. Важность понятия сложности алгоритма хорошо иллюстрируют следующие таблицы.

Пусть для решения некоторой задачи имеется алгоритм сложности n3. Тогда, как это следует из таблицы 1.2, десятикратное увеличение скорости быстродействия ЭВМ позволит увеличить размер задачи, решаемой за 1 минуту в 2,15 раз. Однако замена этого алгоритма другим, имеющим сложность n2, позволит решать задачу в 6 раз большего размера (см. таблицу 1.1). Если в качестве единицы взять 1 час, то сравнение будет еще более впечатляющим. Пусть для решения некоторой задачи имеется алгоритм сложности n3. Тогда, как это следует из таблицы 1.2, десятикратное увеличение скорости быстродействия ЭВМ позволит увеличить размер задачи, решаемой за 1 минуту в 2,15 раз. Однако замена этого алгоритма другим, имеющим сложность n2, позволит решать задачу в 6 раз большего размера (см. таблицу 1.1). Если в качестве единицы взять 1 час, то сравнение будет еще более впечатляющим.

Алгоритмы будем записывать на некотором специальном языке, который назовем упрощенным Паскалем. Алгоритмы будем записывать на некотором специальном языке, который назовем упрощенным Паскалем. В этом языке возможно использование любого типа данных: тип данных какой-либо переменной и ее область действия должны быть ясны либо по ее названию, либо по контексту. В упрощенном Паскале применяются традиционные конструкции математики и языков программирования такие, как выражения, условия, операторы и процедуры. Операторы языка Паскаль используются, как правило, в соответствии с правилами языка Паскаль, но иногда будут применяться неформальные конструкции такие, как, например, 1) циклы for х ϵ X do Р, т.е. выполнять оператор Р для всех элементов х множества X в произвольной последовательности; 2) x[i] ↔ x[j] — переставить i-ый и j-ый элементы массива; или описание типа: "пусть х — наименьший элемент множества X". 3) Будем также предполагать, что все операторы, записанные в одной строке алгоритма, образуют один составной оператор. Поэтому ключевые слова begin и end, идентифицирующие этот оператор, будут опускаться.

АЛГОРИТМ 1.1. ВЫБОР МИНИМАЛЬНОГО ЭЛЕМЕНТА АЛГОРИТМ 1.1. ВЫБОР МИНИМАЛЬНОГО ЭЛЕМЕНТА Данные: числовое множество X. Результат: число minX - минимальный элемент X begin minX := +∞; for х ϵ X do if x < minX then minX := x; end. Поясним на этом примере понятие сложности алгоритма. Размером этой задачи естественно считать n — количество элементов во множестве X. Цикл в строках 3-4 работает ровно n раз. В строке 4 при каждом шаге цикла осуществляется одна операция сравнения и, в худшем случае, одна операция присваивания. Таким образом, в строках 3 и 4 проводится не более чем 2n операций. С учетом оператора присваивания в строке 2 получаем, что число шагов алгоритма не превосходит 2n+1. Значит сложность этого алгоритма есть О(n). Алгоритмы такой сложности принято называть линейными.

Повсюду в дальнейшем будем использовать следующие обозначения. Для произвольного вещественного числа х через |_x_| Повсюду в дальнейшем будем использовать следующие обозначения. Для произвольного вещественного числа х через |_x_| (читается дно х) и |¯х¯| (потолок х) будем обозначить соответственно наибольшее целое число, не превосходящее х, и наименьшее целое, не меньшее х. Все логарифмы являются логарифмами чисел по основанию 2. Поэтому вместо log2x будем писать logx.

Удобно вершины графа считать пронумерованными натуральными числами, и на рисунках сразу вместо точки ставить соответствующий номер Удобно вершины графа считать пронумерованными натуральными числами, и на рисунках сразу вместо точки ставить соответствующий номер Число ребер, инцидентных данной вершине, называется степенью вершины. Вершины степени 1 называют висячими вершинами, а степени 0 — изолированными. Например, в графе, изображенном на рис. 2.1.а, вершины 2, 5, 6 являются висячими. Степенью захода узла в некотором орграфе называется число дуг, в нее входящих, степенью исхода — из нее исходящих. Под степенью узла будем понимать сумму степеней исхода и захода данного узла. Например, в орграфе, изображенном на рис. 2.1.б, степень исхода узла 1 равна 2, а степень захода — 1.

Цепью (соответственно путем) в графе (орграфе) Цепью (соответственно путем) в графе (орграфе) G = (V,E) назовем чередующуюся последовательность вершин и ребер (узлов и дуг) v0,e0, v1, ... ,ek-1, vk такую, что каждое ребро ek соединяет вершины vk и vk+1 (соответственно исходит из vk и входит в vk+1). Вершины (узлы) v0 и vk будем называть соответственно началом и концом цепи (пути). Если все вершины (узлы) цепи (пути) различны, то такую цепь (путь) будем называть простой цепью (простым путем).

Цепь в графе (соответственно путь), начальная и конечная вершины (узлы) которого совпадают, будем называть циклом {контуром). Цепь в графе (соответственно путь), начальная и конечная вершины (узлы) которого совпадают, будем называть циклом {контуром). Если в цикле (соответственно в контуре) все промежуточные вершины различны, то такой цикл (контур) будем на­зывать простым. Иногда нам будет удобно цепь (путь) v0,e0,v1, ... , ek-1,vk отождествлять с множеством ребер (дуг) е0, ... , ek-1 или вершин (узлов) v0,v1, ... ,vk, его образующих. Длиной цепи (пути) будем называть число входящих в нее ребер (дуг).

Деревья Одним из важнейших понятий в теории графов является понятие дерева. Деревом называется связный неориентированный граф без циклов. Теорема1. Пусть G = (V,E) — граф, n=|V|, m=|E|. Тогда следующие условия эквивалентны: G — дерево. Для любых двух вершин u,v V существует и притом единственная цепь, их соединяющая. Граф G связен, и m=n-l. Граф G не содержит циклов, и m=n-l. Граф G не содержит циклов, и при соединении любых двух несмежных вершин ребром образуется ровно один цикл.

Корневое дерево Ориентированный граф без контуров называется корневым деревом, если имеется в точности один узел, называемый корнем, в который не входит ни одна дуга (т.е. степень захода равна нулю); в каждый узел, кроме корня, входит ровно одна дуга; для каждого узла существует путь, начинающийся в корне и заканчивающийся в этом узле.

Корневое дерево

Корневое дерево

Двоичные (бинарные) деревья

Двоичные (бинарные) деревья

Машинное представление графов и сетей

Машинное представление графов и сетей

Машинное представление графов и сетей

Машинное представление графов и сетей

Машинное представление графов и сетей

Машинное представление графов и сетей

Машинное представление графов и сетей

Машинное представление графов и сетей

Машинное представление графов и сетей Для ориентированных графов возможны два способа формирования списков смежностей. В первом в список ЗАПИСЬ[v] включаются лишь те узлы w, для которых (v, w) E, т.е. те узлы, к которым ведут дуги из w. Такой список будем обозначать СЛЕД[v]. Д ругой способ — включать в список ЗАПИСЬ[v] лишь те узлы w, из которых идут дуги в узел v. Этот список будем обозначать ПРЕДШ[v]. Для представления взвешенного графа или сети достаточно в соответствующих списках смежностей отвести одно дополнительное поле для весов ребер или дуг.

Машинное представление графов и сетей Проанализируем способ представления графов и сетей списками смежностей. Понятно, что объем памяти, необходимый для представления графа или сети, имеет порядок n+m, что, вообще говоря, лучше, чем представление матрицей смежности. Особенно заметным этот выигрыш по памяти становится для редких графов (m ˂˂ n2). Ограничимся далее случаем неориентированного графа. Для ответа на вопросы имеется ли в графе (орграфе) ребро {v,w} (дуга (v,w))? к каким вершинам (узлам) ведут ребра (дуги) из V? какова степень вершины (узла) v? достаточно просмотреть список ЗАПИСЬ[v]. Сложность такого просмотра есть О(n) — такая же, как и в случае матрицы смежностей.

Машинное представление графов и сетей Однако, если определять степень всех вершин графа, то здесь сложность ответа будет O(n+m), так как каждое ребро смотрится ровно два раза, в то время как для матрицы смежностей вычислительная сложность такого просмотра есть О(n2). Списки смежностей являются достаточно удобным инструментом для решения задач добавления или удаления ребер из графа. Осуществляются подобные процедуры стандартными средствами для работы со списками. Понятно, что сложность процедуры добавления ребра является константой, если известно, что данного ребра в графе нет, и имеет сложность О(n), если предварительно требуется осуществить поиск для ответа на вопрос о том, есть или нет данное ребро в графе. Аналогично обстоит дело и с процедурой удаления ребра (дуги) из графа (соответственно орграфа).

ЗАДАЧИ Докажите, что в любом графе число вершин нечетной степени четно. В некоторых задачах удобно представлять граф связанными списками смежностей. А именно, каждая запись в списке 3AПИСЬ[v] имеет еще одно поле, где в записи, содержащей вер­шину w, в дополнительном поле ставится ссылка на ту запись списка 3AПИСЬ[w], которая содержит вершину v. Напишите алгоритмы удаления и добавления ребра в граф, заданный связанными списками смежностей. Предложите алгоритм, сложности О(n), записывающий все вершины в списке ЗАПИСЬ[v] в обратном порядке. Пусть некоторый граф задан матрицей смежностей. Рассмотрим следующую процедуру: begin х:=0; for р:=1 to n do for q:=p to n do х:= х + A[p,q]; end. Чему будет равен х в результате работы этой процедуры?

Машинное представление графов и сетей В тех случаях, когда нет необходимости добавлять и удалять ребра или дуги из графа, все списки смежностей вместе с массивом НАЧАЛО можно упаковать в один массив, называемый массивом смежностей. Массив смежностей представляет собой одномерный массив А длины (n+2m+2) для неориентированного графа, и (n+m+2) — для ориентированного. Рассмотрим случай неориентированного графа. Первые n+1 элементов массива А являются адресной частью, а именно, значением A[v] (v=l,2,...,n) является адрес (индекс) в массиве А, начиная с которого в А записаны подряд все вершины, смежные с вершиной v; А[n+1] указывает на конец массива.

Машинное представление графов и сетей Поскольку каждое ребро графа встречается в таком массиве дважды (и имеет индексы в массиве от А[n+2] до А[n+1]-1), то массив действительно имеет длину n+2m+2. Отсюда следует, что этот способ представления графа требует меньше памяти, чем матрица смежностей и чем списки смежностей (так как в последнем случае нет нужды в храпении ссылок на следующие записи). Для ориентированных графов в массиве смежностей, так же как и в списках смежностей, можно хранить дуги по одному разу, записывая либо только исходящие дуги, либо только входящие. И в том, и в другом случае массив будет иметь длину n+m+2 .

Машинное представление графов и сетей Пример. Для неориентированного графа 1 2 3 4 массив смежностей должен быть следующим: 6 8 10 13 14 2 3 1 3 1 2 4 3 32767

Машинное представление графов и сетей Поясним на примере: Количество вершин n = 4 Количество ребер m = 4 Ниже перечислены для указанного в примере графа вершины и соответствующие каждой вершине смежные вершины. 1: 2, 3; 2: 1, 3; 3: 1, 2, 4; 4: 3.

Машинное представление графов и сетей Для взвешенного неориентированного графа (25) 1 2 (4) (0) 3 4 (7) массив смежностей должен быть следующим: 6 10 14 20 nil 2 25 3 4 1 25 3 0 1 4 2 0 4 7 3 7 nil 22 – количество элементов массива 32767

Машинное представление графов и сетей Поясним Количество вершин n = 4 Количество ребер m = 4 Ниже перечислены для указанного в примере графа вершины и соответствующие каждой вершине пары вида (вес, смежная вершина). 1: (25, 2); (4, 3); 2: (25, 1); (0, 3); 3: (4, 1); (0, 2); (7, 4); 4: (7, 3);

Машинное представление графов и сетей Вернемся к предложенным на прошлой паре задачам. После решения задачи «Предложите алгоритм, сложности О(n), записывающий все вершины в списке ЗАПИСЬ[v] в обратном порядке» Программа, работающая по указанному алгоритму должна выдавать соответствующие каждой вершине пары вида (вес, смежная вершина) в обратном порядке. 1: (4, 3); (25, 2); 2: (0, 3); (25, 1); 3: (7, 4); (0, 2); (4, 1); 4: (7, 3).

Решение задачи Входные данные содержат описание графа, заданного массивом смежности. В первой строке n - число элементов в массиве. Далее построчно расположен массив смежности (не более 10 чисел в одной строке). Последний элемент массива равен 32767. 22 6 10 14 20 22 2 25 3 4 1 25 3 0 1 4 2 0 4 7 3 7 32767

Решение задачи На выходе программа построчно выдает для каждой вершины (начиная с первой и до n-ой) пары вида (вес, смежная вершина) в прямом порядке. А затем для каждой вершины (опять начиная с первой и до N-ой) пары вида (вес, смежная вершина) в прямом порядке. Количество вершин n = 4 Cписок смежности в прямом порядке: 1: (25, 2); 1: (4, 3); 2: (25, 1); 2: (0, 3); 3: (4, 1); 3: (0, 2); 3: (7, 4); 4: (7, 3); Cписок смежности в обратном порядке: 1: (4, 3); 1: (25, 2); 2: (0, 3); 2: (25, 1); 3: (7, 4); 3: (0, 2); 3: (4, 1); 4: (7, 3);

Программа на C++ // Библиотеки #include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; void main() { int n = 0; vector < pair < int, pair<int,int> > > g; // ребра: вес - вершина 1 - вершина 2 freopen("in.txt","r", stdin); freopen("out.txt","w", stdout); int temp; cin >> temp;// сколько чисел вообще считывать int *temp_ar = new int [temp];//весь массив смежностей int *temp_ar_number = new int [temp];//вспомогательный массив для хранения только позиций (адресов)

Программа на C++ for (int i = 0; i < temp; i++) { temp_ar_number[i] = -1; } for(int i = 0; i < temp; i++) { cin >> temp_ar[i]; // считали из файла массив, где все входные данные (весь массив смежности) } for (int i = 0; i < temp; i++){ temp_ar_number[i] = temp_ar [i]; //массив с адресной частью if (temp_ar[i] == temp) { n = i; break; } } // Определили количество вершин графа (в соответствии с придуманной и реализованной нами структурой входного файла)

Программа на C++ cout << "\n" <<"Количество вершин n = "<< n << "\n"; Формирование массива смежности int fict = 1;//фиктивная переменная начало ребра int k; for (int i = 0; i < temp; i++){ int numb_begin = temp_ar_number[i]-1; //взяли первое определяющее число массива int numb_end = temp_ar_number[i+1]-1; //взяли второе определяющее число массива for (int j = numb_begin; j < numb_end; j+=2){ g.push_back(make_pair(temp_ar[j+1], make_pair (fict, temp_ar[j]))); } fict++; if (numb_end == (temp-1)) break; }

Программа на C++ Вывод (печать) массива смежности cout <<«Список смежности в прямом порядке:\n"; for( int i = 0; i < g.size(); i++ ) { cout << g[i].second.first<<": (" << g[i].first << ", " << g[i].second.second << "); "; k = i+1; if(g[i].second.first != g[k].second.first){ cout << "\n"; } }

Программа на C++ Формирование массива смежности vector < pair < int, pair<int,int> > > g_convert; // обратные списки смежности fict = 1; for (int i = 0; i < temp; i++){ int numb_begin = temp_ar_number[i]-1;//взяли первое определяющее число массива int numb_end = temp_ar_number[i+1]-1;//взяли второе определяющее число массива for (int j = numb_end; j > numb_begin; j-=2){ g_convert.push_back(make_pair(temp_ar[j-1], make_pair (fict, temp_ar[j-2]))); } fict++; if (numb_end == (temp-1)) break; }

Программа на C++ Вывод массива смежности cout <<"\nCписок смежности в обратном порядке:\n"; for( int i = 0; i < g_convert.size(); i++) { cout << g_convert[i].second.first<<": (" << g_convert[i].first << ", " << g_convert[i].second.second << "); "; k = i+1; if( g_convert[i].second.first != g_convert[k].second.first){ cout << "\n"; } } }

Индивидуальное задание для реализации на уроке (прямо сегодня!!!) Обучающийся 1) рисует взвешенный граф, 2) «вручную» пишет на листке массив смежности (в прямом и обратном порядках), 3) подписанный листок с нарисованным графом сдает преподавателю (мне!!!), 4) пишет программу на Java или на Паскале, которая решает задачу, 5) после проверки правильности ее работы преподаватель проверяет работоспособность программы на нескольких графах (скорее всего, на графах, предложенных одногруппниками), 6) объясняет код и получает «плюсик».

Сортировка данных Сортировка является неотъемлемой частью многих алгоритмов решения математических задач. Задача сортировки формулируется следующим образом: Дана последовательность из n элементов a1,...,an, выбранных из множества, на котором задано отношение линейного порядка. Требуется найти перестановку s = (s(l),…,s(n)) индексов, для которой as(1) ≤ as(2) ≤ ... ≤ as(n), т.е. расположить элементы данной последовательности в неубывающем порядке (или в невозрастающем, т.е. as(1) ≥ as(2) ≥ ... ≥ as(n)).

Сортировка данных При формулировании задачи сортировки в общем виде информацию о последовательности элементов можно получать только с помощью операции сравнения двух элементов. Пусть а1,...,аn - последовательность сортируемых элементов. Не ограничивая общности, можно считать, что элементы заданной последовательности помещены в некоторый массив А Не ограничивая общности, можно считать, что элементы заданной последовательности помещены в некоторый массив А в том же порядке, m.е. A[i] = ai при i = 1,2,...,n.

Сортировка выбором Алгоритм сортировки выбором Данные: массив А[1..n]. Результат: массив А[1..n] такой, что А[1] ≤ А[2] ≤ ... ≤ A[n]. begin procedure MIN(i): begin for j = i to n do if A[i] < A[j] then A[i]↔A[j]; end; begin (* главная программа *) for i := 1 to n-1 do MIN(i); end; end.

Сортировка выбором Процедура MIN(i) выбирает минимальный элемент из массива аi,...,аn и ставит его на первое место, т.е. на место ai. Алгоритм начинает работу с вызова процедуры MIN(l), которая перемещает на первое место наименьший элемент исходного массива. Далее процедура повторяется для массива а2,...,аn и т.д.

Сортировка выбором Сортировка выбором имеет вычислительную сложность O(n2). Действительно, в процедуре MIN(i) осуществляется (n-i) операции сравнения и, в худшем случае, (n-i) операции обмена. Значит, общее число шагов, выполняемое процедурой MIN(i) пропорционально (n-i). Число сравнений в алгоритме (n - 1) + (n - 2) + ... + 1 = n(n - 1 )/2 Т.е. сложность алгоритма есть O(n2).

Сортировка данных Приведем теорему, позволяющую оценить снизу сложность любого алгоритма сортировки. В любом алгоритме, упорядочивающем с помощью сравнений, на упорядочение последовательности из n элементов тратится не менее c∙n∙loq n сравнений при некотором с > 0 и достаточно большом n. Для доказательства представим алгоритм в виде корневого дерева. Любой алгоритм, упорядочивающий с помощью сравнений, можно схематично представить в виде корневого дерева, называемого двоичным деревом решений. Это дерево можно рассматривать как блок-схему алгоритма сортировки, в котором показаны все сравнения элементов и исходы алгоритма. Вершины дерева (кроме листьев) соответствуют сравнениям элементов, при этом корень дерева соответствует первому сравнению, осуществляемому алгоритмом. Сыновья вершин изображают возможные исходы сравнения отца. Листья соответствуют исходу алгоритма в зависимости от начальных значений переменных.

Двоичное дерево решений для сортировки трех элементов

Сортировка данных Поскольку, всякое двоичное дерево высоты к имеет не более 2к листьев, то получаем, что должно выполняться неравенство 2к > n!, т.к. листьев в двоичном дереве решений должно быть не меньше, чем перестановок из n элементов. Отсюда, k > log n! Осталось заметить, что при n > 1 справедлива следующая цепочка неравенств: n! ≥ n(n - 1 )(n - 2)... () ≥ (n/2)n/2, так что log n! ≥ log( n/2 )n/2 = n/2 log n/2 ≥ n/4 log n Итак, k ≥ n/4 log n — полученное неравенство завершает доказательство теоремы.

Алгоритм СОРТДЕРЕВО Алгоритм сортировки, называемый СОРТДЕРЕВО, имеет сложность O(n log n). В разных учебниках он называется: алгоритмом пирамидальной сортировки, Heapsort или Treesort. Определим структуру корневого двоичного дерева в массиве А[1..n], считая, что в корне находится элемент А[1], и элемент A[i] имеет двух сыновей: A[2i] (если 2i ≤ n) и A[2i+1] (если 2i+1 ≤ n). Такую структуру назовем двоичным деревом массива А.

Алгоритм СОРТДЕРЕВО Лемма. Двоичное дерево массива длины n имеет высоту Напомним, что высота корневого дерева есть по определению длина самого длинного пути из корня до какого-нибудь листа. Например, на рис.3.2 это путь до листа, в котором находится число 7. Легко видеть, что длина этого пути равна 3.

Алгоритм СОРТДЕРЕВО Пусть k - высота двоичного дерева массива длины n. Для всех s < k в дереве имеется ровно 2s вершин глубины s. Пусть h — количество вершин глубины k. Тогда справедливо неравенство 1 < h < 2k. Поскольку число вершин равно n — длине массива, то справедливо равенство: n = 1 + 2 + ... + 2k-1 + h = 2k - 1 + h. Учитывая, что h ≤ 2k, получаем, что n = 2k - 1 + h ≤ 2k - 1 + 2k < 2k+1. Отсюда n < 2k+1. С другой стороны, так как h ≥ 1, то n= 2k - 1 + h ≥ 2k. Таким образом, справедливо неравенство 2k ≤ n ≤ 2k+1. Отсюда, k ≤ logn ≤ k+1, то есть k =

Алгоритм СОРТДЕРЕВО Двоичное дерево массива А называется сортирующим деревом массива А, если выполняются условия: А[k] ≥ А[2 k] и А[k] ≥ А[2 k +1] для к = l,2,.... Непосредственно из определения вытекает, что наибольший элемент массива находится в корне его сортирующего дерева. Легко видеть также, что двоичное дерево, изображенное на представленном выше рис., не является сортирующим. Именно на представлении массива сортирующим деревом основан один из теоретически наилучших алгоритмов сортировки данных — СОРТДЕРЕВО.

Алгоритм СОРТДЕРЕВО На первом этапе двоичное дерево массива А преобразуется в сортирующее. Процедуру, осуществляющую это преобразование, будем называть ПСД. Затем, поскольку по свойству сортирующего дерева, элемент в корне, а именно, А[1] является наибольшим в А, то, переставляя А[1] и А[n], и удаляя А[n] из дерева, получим массив А[1.. n-1] и A[n] = max А[1..n]. Теперь преобразуем А[1..n-1] в сортирующее дерево, затем переставим А[1] и А[n-1] и удалим А[n-1]. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда А[1],...,А[n] — упорядоченная по неубыванию последовательность.

Алгоритм СОРТДЕРЕВО Перейдем к формальному описанию алгоритма СОРТДЕРЕВО. Начнем с описания процедуры ПСД (построение сортирующего дерева). В его основе лежит рекурсивная процедура ПЕРЕСЫПК(i,j), имеющая параметры i и j. Они задают область ячеек массива А, которая в результате процедуры ПЕРЕСЫПКА будет обладать свойством сортирующего дерева, при этом его корень помещается в вершину i.

Алгоритм СОРТДЕРЕВО АЛГОРИТМ 3.2. СОРТДЕРЕВО Данные: массив элементов А[1..n]. Результат: массив элементов А[1..n], упорядоченный по неубыванию, то есть А[1] ≤ А[2] ≤ ... ≤ А[n]. begin ПСД; (* вначале строится сортирующее дерево *) for i := n downto 2 do begin A[l] ↔ A[i]; ПЕРЕСЫПКА( 1,i-1) end; end

Алгоритм СОРТДЕРЕВО procedure ПСД; begin for i := downto 1 do ПЕРЕСЫПКА(i,n) End Ниже дано формальное описание процедур ПЕРЕСЫПКА. Без формального описания используется функция MAXCЫH(i), значением которой является тот сын i, который со­держит наибольший из элементов A[2i] и A[2i+1].

Алгоритм СОРТДЕРЕВО procedure ПЕРЕСЫПКА( i ,j); begin if i ≤ then (* если i — не лист *) begin k := MAXCЫH(i); if A[i] < A[k] then begin A[i]↔ A[k]; ПЕРЕСЫПКА(k,j) end; end; end;

Алгоритм СОРТДЕРЕВО Разберем пример, иллюстрирующий работу обеих этих процедур Пусть задан числовой массив А[1…10]: I 1 2 3 4 5 6 7 8 9 10 А[I] 2 3 6 1 4 5 8 0 7 9

Алгоритм СОРТДЕРЕВО

Алгоритм СОРТДЕРЕВО Изобразим окончательный результат в виде таблицы: I 1 2 3 4 5 6 7 8 9 10 A[I] 9 7 8 2 4 5 6 0 1 3

Алгоритм СОРТДЕРЕВО

Алгоритм СОРТДЕРЕВО На рис.3.4 дерево f) является сортирующим деревом исходно­го массива А, полученным в результате работы процедуры ПСД. Затем происходит перестановка А[1] и А[10] (дерево g) ). К дере­ву g) применяется процедура ПЕРЕСЫПКА(1,9), в результате которой число 3 проходит путь по правым ветвям из корня дере­ва до листа. Затем вновь происходит перестановка корня с лис­том и т.д. В результате получится массив А, упорядоченный по возрастанию.

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

Поиск в глубину Поиск начинается с некоторой фиксированной вершины v, называемой корневой вершиной поиска или корнем. При этом считаем v просмотренной вершиной. Затем выбираем какое-нибудь ребро {v,w}, инцидентное v, проходим его и попадаем в вершину w.

Поиск в глубину Тот факт, что в процессе поиска использовано именно ребро {v,w} отмечается обычно следующим образом. Ребро {v,w} ориентируется из v в w. Полученную дугу (v,w) считают дугой корневого дерева с корнем v. Такое дерево называется ПВГ-деревом с корнем v, или короче ПВГ(v)—деревом. При переходе от v к w, вершина v объявляется отцом вершины w и обозначается OTEЦ[w], вершина w объявляется просмотренной, и поиск продолжается из вершины w.

Поиск в глубину В общем случае, когда мы находимся в некоторой вершине v, возникают две возможности: 1) Все вершины, смежные с v, уже просмотрены. В этом случае возвращаемся к вершине ОТЕЦ[v] и продолжаем поиск из нее, а вершину v с этого момента считаем использованной.

Поиск в глубину 2) Существует еще не просмотренная вершина w, смежная с вершиной v. Тогда ребро {v,w} превращаем в дугу (v,w), добавляя ее к ПВГ(v)-дереву; полагаем ОТЕЦ[w]=v; проходим по дуге из v в w и продолжаем поиск из w.

Поиск в глубину Поиск в глубину завершается тогда, когда все вершины графа будут просмотрены. Здесь возможны две ситуации: 1) Корневая вершина использована (т.е. все смежные с ней вершины просмотрены), однако в графе еще есть не просмотренные вершины. В этом случае выбираем произвольную не просмотренную вершину, объявляем ее корнем и вновь начинаем поиск уже из этой вершины. Такая ситуация возникает только в случае несвязного графа. 2) Корневая вершина и все другие использованы. Поиск на этом заканчивается.

Поиск в глубину Представим формальное описание изложенного алгоритма поиска в глубину, основанную на рекурсивной процедуре ПВГ(v) — поиск в глубину из вершины v. В рассматриваемом алгоритме связность графа не предполагается. АЛГОРИТМ Поиск в глубину.1 Данные: неориентированный граф G=(V,E), заданный списками смежностей ЗАПИСЬ[v]. Результаты: массив ОТЕЦ, множество Т. procedure ПВГ (v); (*поиск в глубину с корнем v) begin METKA[v]:=l; for w ЗАПИСЬ[v] do if METKA[w]=0 then begin OTEЦ[w]:=v; T:=T{(v,w)}; ПВГ(w); end; end; begin (*Главная программа) T := Ø; for v V do METKA[v]:=0; (*инициализация) for v V do if METKA[v]=0 then begin OTEЦ[v]:=nil; ПВГ(v); end; end.

Поиск в глубину Примечание. Массив МЕТКА, используемый в алгоритме имеет по одному элементу для каждой вершины графа и служит указателем на то, что просмотрена или нет данная вершина. Считаем, что METKA[v]=0, если v не просмотрена, и METKA[v]=1 в противном случае. Массив ОТЕЦ описан ранее. Понятно, что он имеет длину n, где n — число вершин в графе. В множестве Т будем хранить дуги ПВГ-деревьев.

Поиск в глубину На следующем рис. показано, как поиск в глубину исследует неориентированный граф G. Предполагается, что в списках смежности этого графа вершины встречаются в порядке возрастания номеров, и, что цикл в строках 11-14 алгоритма Поиск в глубину.1 выполнялся в порядке возрастания номеров вершин.

Поиск в глубину

Поиск в глубину В просмотренном графе G дуги ПВГ-деревьев обозначены стрелками в соответствии с ориентацией, полученной в ходе поиска. Такие дуги часто называют прямыми дугами поиска. Прочие ребра графа, называемые иногда обратными дугами поиска, обозначены на рисунке пунктирами. Числа в скобках, стоящие у вершин просмотренного графа, соответствуют очередности, в которой они просматривались в ходе поиска. Отметим, что вершины с номерами 1, 9 и 11 являются корнями ПВГ-деревьев.

Поиск в глубину Разберем теперь нерекурсивную версию процедуры ПВГ(v). Рекурсия устраняется стандартным способом с помощью стека. Каждая вершина помещается в стек сразу, как только будет достигнута, то есть просмотрена, и удаляется из стека после того, как будет использована. Поиск новой непросмотренной вершины ведется из той вершины, которая последней попала в стек.

Поиск в глубину Для организации такого процесса понадобится дополнительно массив указателей УКАЗ длины n, где n=|V|. Предполагается, что в начале работы процедуры поиска выполняются равенства УKA3[v]=HAЧAЛO[v], для всех v из V, иначе говоря, УКАЗ[v] дает адрес первой записи в списке ЗАПИСЬ[v]. В процессе работы процедуры поиска УКАЗ[v] меняется таким образом, что указывает на следующую запись в списке ЗАПИСЬ[v] после той, которая содержит последнюю просмотренную из нее вершину.

Поиск в глубину procedure ПВГ1(v); (* нерекурсивная версия *) begin СТЕК :=Ø; СТЕК v; METKA[v]:=l; while СТЕК ≠ Ø do begin u СТЕК; while (УКАЗ[u] ≠ nil) and (МЕТКА[УКАЗ[u]^.строка]=1) do УКАЗ[u] := УКАЗ[u]^.след; if УКАЗ[u] ≠ nil then (*найдена непросмотренная вершина *) begin w := УКАЗ[u]^.строка: СТЕК w; OTEЦ[w]:=u; METKA[w]:=l; T := T(u,w); УКАЗ[u]:= УКАЗ[u]^.след; end; else СТЕК (* вершина u использована *) end; end.

Поиск в глубину Теорема. Сложность алгоритма Поиск в глубину 1 есть O(n+m). Следствие. Связные компоненты неориентированного графа могут быть найдены за время O(n+m).

Поиск в глубину Поиск в глубину в ориентированном графе отличается от поиска в неориентированном графе только тем, что ребра проходятся в соответствии с их ориентацией. Поскольку в главе 2 мы условились считать, что в списке ЗАПИСЬ[у] встречаются только те вершины w, для которых (v,w) E, то алгоритм Поиск в глубину1 корректно работает и в ориентированных графах.

Поиск в ширину Поиск в ширину Другое название этого популярнейшего метода — волновой алгоритм. Причины появления такого названия станут ясны из дальнейшего. Поиск в ширину начинается с некоторой фиксированной вершины v, называемой корнем. Вершину v считаем просмотренной и помещаем ее в организуемую нами очередь. Считаем также, что вершина v образует нулевой фронт распространения волны.

Поиск в ширину Затем проходим все ребра {v,w}, инцидентные v, в каком-нибудь порядке и ориентируем их из v в w. Вершины w, смежные с v, считаем просмотренными и размещаем их в порядке просмотра ребер в очередь. Для всех таких вершин w полагаем OTEЦ [w]:=v и говорим, что w просмотрена из v. Ориентированные ребра (v,w) будем называть ребрами ПВШ(v)-дерева. Говорят часто, что все такие вершины w образуют первый фронт распространения волны. Вершина v после этих действий считается использованной и удаляется из очереди.

Поиск в ширину Дальнейший поиск продолжается следующим образом. Берем очередную вершину v из очереди, проходим по всем ребрам, ин­цидентным v, которые соединяют вершину v с еще непросмотренными вершинами w. Все такие вершины w объявляются просмотренными, для них полагают OTEЦ[w]:=v, ребра (v,w) относят к ПВШ(v)-дереву.

Поиск в ширину После этих действий вершина v считается использованной и удаляется из очереди. Говорят также, что вершины, просмотренные из вершин, принадлежащих фронту с номером k, образуют (k+1)-ый фронт распространения волны. Завершается поиск в ширину с корнем в заданной вершине таким же образом, как и поиск в глубину, а именно тогда, когда ни одной новой вершины просмотреть не удается.

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

Поиск в ширину

Поиск в ширину Отметим, что в ПВШ(1) - дереве поиска вершины 2, 3, 4 обра­зуют первый фронт распространения волны, вершины 5, 6 и 7 — второй, а вершина 8 — третий.

Поиск в ширину Отметим, что в ПВШ(1) – дереве поиска вершины 2, 3, 4 образуют первый фронт распространения волны, вершины 5, 6 и 7 — второй, а вершина 8 — третий. Далее представлен АЛГОРИТМ 4.2. ПОИСК В ШИРИНУ Данные: неориентированный граф G=(V,E), заданный списками смежностей. Результаты: массив ОТЕЦ, множество D.

Поиск в ширину procedure ПВШ(v); (* поиск в ширину с корнем v *) begin ОЧЕРЕДЬ :=Ø; ОЧЕРЕДЬ v; METKA[v]:=1; while ОЧЕРЕДЬ ≠Ø do begin u ОЧЕРЕДЬ; ОЧЕРЕДЬ; for w ЗАПИСЬ[u] do (* используем вершину u *) if METKA[w]=0 then begin ОЧЕРЕДЬ w; OTEЦ[w]:=u; METKA[w]:=1; D=Du{(u,w)}; end; end; end; begin (*главная программа*) D:=Ø; for vV do METKA[v]:=0; (* инициализация *) for v V do if METKA[v]=0 then (*v – корень*) begin OTEЦ([v]:=nil; ПВШ(v); end; end.

Поиск в ширину В приведенном формальном описании алгоритма поиска в ширину переменная МЕТКА имеет тот же смысл, что и ранее в алгоритме Поиск в глубину 1. Дуги ПВШ-деревьев хранятся в множестве D. Смысл переменной ОТЕЦ объяснен выше. Просмотренные вершины помещаются в ОЧЕРЕДЬ и удаляются оттуда сразу после их использования (строка 4 алгоритма).

Поиск в ширину В алгоритме Поиск в ширину 2 связность графа не предполагается. Для корневых вершин поиска и только для них выполняется равенство ОТЕЦ[v]=nil. Теорема 4.2. Алгоритм ПОИСК В ШИРИНУ 2 имеет вычислительную сложность O(n+m).

Цепи и пути в графах Применительно к только связным неориентированным графам нетрудно проверить, что и ПВГ-дерево, и ПВШ-дерево действительно являются деревьями, и более того — корневыми деревьями, причем корнями этих деревьев являются те вершины, с которых начинался поиск (собственно поэтому они и в ПВГ и в ПВШ названы корневыми вершинами).

Цепи и пути в графах Если в ориентированном графе имеется дуга (v,w), то v — отец w, a w — сын v. Легко видеть, что даваемые алгоритмами ПоискВглубину1 и ПоискВширину2 значения переменных ОТЕЦ[w] согласуются с ранее введенным понятием, а именно, если v=ОТЕЦ[w], то (v,w)E. Вершина v называется предком вершины w, и, соответственно, w — потомком v, если в корневом дереве существует путь от v до w. Например, в корневом дереве ПВШ(1) из рис. вершина 8 является потомком вершины 2.

Цепи и пути в графах Теорема 3. Пусть Т — ПВГ-дерево связного неориентиро­ванного графа G=(V,E), и пусть {u,w}E. Тогда либо u — потомок w, либо w потомок u в корневом дереве Т. Понятно, что ПВШ-дерево не обладает свойством, сформули­рованным в теореме3. Например, в ПВШ(1)-дереве, изобра­женном на рис. 2, ни вершина 3 не является потомком вершины 6, ни вершина 6 не является потомком вершины 3 (говорят, что такие вершины несравнимы в корневом дереве).

Цепи и пути в графах Как в ПВГ-дереве, так и в ПВШ-дереве для каждой вершины w, существует единственный путь из корня v в w. Как построить этот путь? Это несложно делается с помощью массива ОТЕЦ. Отметим только, что под путем в орграфе мы договорились понимать в зависимости от степени удобства, либо последовательность ребер, либо последовательность вершин.

Цепи и пути в графах В предлагаемом ниже алгоритме ПостроениеПути3 требуемый путь идентифицируется последовательностью вершин. Предполагается, что перед работой этого алгоритма работала либо процедура ПВГ(v), либо процедура ПВШ(v).

Цепи и пути в графах АЛГОРИТМ ПостроениеПути3. Данные: корневая вершина поиска v, вершина w. массив ОТЕЦ. begin СТЕК:=Ø; СТЕК w; u:=w; while u≠v do begin u:=ОТЕЦ[u]; CTEK u; end; end. Результат: СТЕК, содержащий последовательность вершин, об­разующих v-w-путь.

Цепи и пути в графах Понятно, что последовательность вершин v=v0,v1,...,vk=w, по­лученная считыванием СТЕКА, образует как v-w-путь в корневом дереве Т (или D), так и v-w-цепь в исходном графе G. Оказывается, что пути, построенные поиском в ширину, обладают очень полезным свойством, а именно, справедлива. Теорема 4. Пусть D — ПВШ-дерево с корнем v связного неориентированного графа G=(V,E). Тогда для любой вершины w V единственный v-w-путь в D определяет кратчайшую по числу ребер цепь среди всех v-w-цепей в графе G.

Цепи и пути в графах Заметим, что пути, определяемые поиском в глубину, вообще говоря, не являются кратчайшими. Например, на рис.1 путь от вершины 1 до вершины 8 проходит через вершины 2,3,4,7,6 и имеет длину 6, а поиск в ширину (см.рис.2) определяет путь, проходящий через вершины 4,7, длиной 3.