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

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

Содержание слайда: Введение Примеры дискретных оптимизационных задач задача о кратчайшем пути: Пусть имеется несколько городов и известны попарные расстояния между соседними городами. При этом два города считаются соседними, если есть дорога, их соединяющая, и не проходящая через какой-либо другой город. Требуется найти кратчайший путь между некоторой парой городов; задача оптимального назначения: Пусть имеется 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.