Невозможно отобразить презентацию
mathematicsSimilar presentations:
Дискретные экстремальные задачи. Лекция 1
Институт математики, ауд.220 пятница 14:15 Лектор: Кононов Александр Вениаминович http://www.math.nsc.ru/LBRT/k5/dep.html Программа первого семестра 1.Введение 2.Графы 3.Остовные деревья 4.Кратчайшие пути 5.Потоки в сетях 6.Максимальное паросочетание 7.Матроиды 1.
Введение 1.1.
Перечисление (перебор) 1.2.
Время работы алгоритмов 1.3.
Алгоритм сортировки слиянием 2.
Графы 2.1 Основные определения 2.2 Деревья, обходы и разрезы 2.3 Связность 2.4 Эйлеровы и двудольные графы 3.
Остовные деревья 3.1 Задача о минимальном остовном дереве 3.2 Задача о минимальном взвешенном ориентированном остовном дереве 3.3 Упаковка остовных деревьев 4.
Кратчайшие пути 4.1 Кратчайшие пути из одной вершины 4.2 Кратчайшие пути между всеми парами вершин 4.3 Задача о минимальном усредненном цикле 5.
Потоки в сетях 5.1 Теорема о максимальном потоке и минимальном разрезе 5.2 Теорема Менгера 5.3 Алгоритм Эдмонса-Карпа 5.4 Блокирующие потоки 5.5 Алгоритм Голдберга-Тарьяна 6.Максимальное паросочетание 6.1 Двудольное паросочетание 6.2 Матрица Татта 6.3 Теорема Татта 6.4 Алгоритм Эдмонса Матроиды 7.1 Независимые системы и матроиды 7.2 Жадный алгоритм для задачи максимизации независимой системы Литература
• Korte B., Vygen J.
Combinatorial Optimization: theory and algorithms.
(Algorithms and Combinatorics 21), Springer, Berlin, 2000.
• Пападимитриу Х., Стайглиц К.
Комбинаторная оптимизация.
Алгоритмы и сложность.
М.: Мир, 1985.
Век комбинаторной оптимизации
• Теория чисел ~ 4000 лет назад
• Геометрия ~ 2600 лет назад
• Анализ ~ 300 лет назад
• Алгебра ~ 200 лет назад ---------------------------------------------------- Комбинаторная оптимизация ~ 50 лет назад! Причина Тысячи проблем в экономике, военных приложениях, организации производства могут быть сформулированы как задачи комбинаторной оптимизации.
Производство печатных плат
• Даны: Множество точекp1 ,…,pnR2 .
• Найти: Перестановку : {1,...,n} {1,...,n} такую чтоd(pπ(i),pπ(i+1)) минимально.∑−=1ni Задача о назначении
• Даны: Множество чиселp1 ,…,pnR+ (длительность работ),mN рабочих, и непустое подмножествоSi⊆ {1,...,m} рабочих для каждой работыi∈ {1,...,n}.
• Найти: Числаxij∈R+(i=1 ,...,n;jSi) так что (i=1 ,...,n)и минимизирующее maxj.∑∈=iSiijpxj∑∈iSijxj:i Комбинаторная оптимизация Вычислительные проблемы ― не только задачки, которые должны быть решены;
они ― также объекты, которые заслуживают изучения.
Задачи и алгоритмы можно формализовать и изучать математически.
Х.
Пападимитриоу Задача разметки печатных плат
• Даны: Множество точекp1 ,…,pnR2 .
• Найти: Перестановку : {1,...,n} {1,...,n} такую чтоd(pπ(i),pπ(i+1)) минимально.∑−=1ni Алгоритм ??? Input:N точек … Найти оптимальный путь !!! Output: оптимальный путьNO Алгоритм ??? Input:N точек … Перебрать все возможные перестановки и выбрать оптимальную ! Output: оптимальный путьNO Перебор с возвратом (1, 1, … , 1, 1) (1, 1, … , 1,2 )(1, 1, … , 1,3) (1, 1, … , 1,n) (1, 1, … ,2 , 1) (1, 1, … , 2,2 )(1, 1, … , 2,3) (1, 1, … , 2,n) (1, 1, … ,3 , 1) (1, 1, … , 3,2 )(1, 1, … , 3,3) (1, 1, … , 3,n)
•
•
•
•
• •n шаговn! перестановок n! << nn Лексикографический порядок Определение 1.1 Пусть x,y∈Rn― два вектора.
Вектор x лексикографически меньше чем y , если существует индексj∈ {1,...,n }, такой чтоxi=yi дляi =1,...,j – 1 и xj<yj.
Алгоритм перебора путей Input: Натуральное числоn≥ 3 .
Множество{p1 ,…,pn} точек на плоскости Output: Перестановкаπ* :{1,...,n }→{1,...,n}, минимизирующая cost(π*): = d(p p (i),p p (i+1)).
1.
Setπ(i):=i,π*(i):=ifori =1,...,n.Seti:= n −1.
2.
Letk :=min({π(i)+1 ,…,n +1}\ {π(1) ,…, π(i)− 1}).3.Ifk≤ n then: Setπ(i):=k.If i= n& cost (π) < cost(π*) thenset π*:=π.If i< n thensetπ(i+ 1):=0 &i:=i+1.Ifk=n+1 thenseti := i − 1.Ifi≥ 3 then go to2.∑−=1ni Пример π := (1, 2, 3, 4, 5, 6 )i := 5k := 6π := (1, 2, 3, 4, 6,0 )i := 6k := 7k := 5π := (1, 2, 3, 4,6,5 ) ? cost(π) < cost(π*) ?k := 5π := (1, 2, 3,5, 0 , 5 )i := 5k := 4π := (1, 2, 3, 5, 4,0 )i := 6k := 6π := (1, 2, 3, 5,4,6 ) ? cost(π) < cost(π*) ?
•
• •i := 5i := 4 Полезное обозначение Определение 1.2 Пусть f , g:D R+ две функции.
Будем говорить, чтоf есть O(g) (и писать f = O(g)), если существуют константы α, β >0 , такие что f(x)≤ αg(x)+β для всехx∈D .
Если f = O(g)и g = O(f), то будем писать f = Θ(g).
Алгоритм перебора путей Input: Натуральное числоn≥ 3 .
Множество{p1 ,…,pn} точек на плоскости Output: Перестановкаπ* :{1,...,n }→{1,...,n}, минимизирующая cost(π*): = d(p p (i),p p (i+1)).
1.
Setπ(i):=i,π*(i):=ifori =1,...,n.Seti:= n −1.2.Letk :=min({π(i)+1 ,…,n +1}\ {π(1) ,…, π(i)− 1}).3.Ifk≤ n then: Setπ(i):=k.If i= n& cost (π) < cost(π*) thenset π*:=π.If i< n thensetπ(i+ 1):=0 &i:=i+1.Ifk=n+1 thenseti := i − 1.Ifi≥ 3 then go to2.∑−=1nik :=min({π(i)+1 ,…,n +1}\ {π(1) ,…, π(i)−1})•Forj := 1tondoaux(j ) := 0.•Forj := 1toi – 1doaux (π(j )) := 1.•Setk := π(i ) + 1.
• Whilek≤nandaux(k ) = 1dok:=k + 1.
Алгоритм
• Множество исходных данных (Вход)
• Последовательность инструкций, каждая из которых может быть представлена цепочкой элементарных шагов.
• Для каждого допустимого входа алгоритм в процессе вычисления выполняет единственно определенную серию элементарных шагов и выдает некоторый ответ.
Время работы алгоритма Определение 1.3 Пусть алгоритмA получает на входе множествоX,и пустьf:X→R+.
Если существует константа α >0 такая что алгоритмA заканчивает вычисления не более чем черезαf(x) элементарных шагов (включая арифметические операции) для любого входа x∈X, то будем говорить, чтоO(f) время работы алгоритмаA.
Размер входа
• Размер входа примера с рациональными данными равен числу бит требуемых для его двоичного представления.
Полиномиальный алгоритм
• Определение 1.4 Алгоритм с рациональным входом называется полиномиальным , если существует целоеk такое что алгоритм работает время O(nk ), гдеn есть размер входа и все числа, используемые алгоритмом в процессе вычислений ограничены величиной O(nk ) бит.
Алгоритм с произвольным входом называется сильно полиномиальным , если существует целоеk такое что алгоритм работает время O(nk ) на любом входе состоящим из n чисел и он полиномиальный на рациональном входе.
Если k=1 алгоритм называется линейным.
Таблица 1.1n100n logn 10n2n3.5nlogn 2n! 10 3μs 1μs 3μs 2μs 1μs4μs 30 15μs 9μs148μs20ms 1s>1015y 100 66μs100μs 10ms 5 h>1013y103 1ms 10ms 32s>1013y108 266s 3 y>1010y1012 46d>108y Таблица 1.2 1h100n logn10n2n3.5nlogn2n! (a)1.19*109 600003868 87 41 15 (b)10.8*109 1897377468 104 45 16 Алгоритм сортировки слиянием Input: Список a1 ,…,an действительных чисел.
Output: Перестановка :π {1,...,n} {1,...,n }, такая что aπ(i) ≤aπ(i+1) для всехi =1,...,n – 1.1.Ifn=1 thensetπ (1) :=1and stop (returnπ ).
2.
Set m:=[n/2].
Let :=ρ Merge-Sort(a1 ,…,am).
Let :=σ Merge-Sort(am+1 ,…,an).3.Set k:=1,l :=1.
Whilek≤m andl≤n–mdo:Ifa ρ(k)≤a m+σ(l) then set(πk+l– 1):= (ρk ) andk: = k +1.
else set (πk+l– 1):=m+ (σl ) andl: =l +1.
Whilek ≤ mdo:Setπ(k+l– 1):= (ρk ) andk: = k+1.
Whilel ≤ n-mdo:Setπ(k+l– 1):=m+ (σl ) andl: = l +1.
Время работы алгоритма Теорема 1.5 Алгоритм сортировки слиянием находит решение заO(n logn) элементарных операций.
Алгоритм сортировки слиянием Input: Список a1 ,…,an действительных чисел.
Output: Перестановка :π {1,...,n} {1,...,n }, такая что aπ(i) ≤aπ(i+1) для всехi =1,...,n – 1.1.Ifn=1 thensetπ (1) :=1and stop (returnπ ).
2.
Set m:=[n/2].
Let :=ρ Merge-Sort(a1 ,…,am).
Let :=σ Merge-Sort(am+1 ,…,an).3.Set k:=1,l :=1.
Whilek≤m andl≤n–mdo:Ifa ρ(k)≤a m+σ(l) then set(πk+l– 1):= (ρk ) and k:=k +1.
else set (πk+l– 1):=m+ (σl ) and l:= l +1.
Whilek ≤ mdo:Setπ(k+l– 1):= (ρk ) andk: = k+1.
Whilel ≤ n-mdo:Setπ(k+l– 1):=m+ (σl ) andl: = l +1.
Доказательство теоремы 1.5•T(n ) время работы алгоритма на примере сn числами.
• Грубо оценим шаг 3 сверху через 5n + 2.()1log122521+≤++=nTnTnTnT Упражнение 1.1 ()().log!log,n что ДоказатьΘ= Упражнение 1.2().logn,1ε+=nOn что Доказать Упражнение 1.3 Показать, что время работы алгоритма перебора путей естьO( n•n!).
Упражнение 1.4 Пустьs,t строчки из нулей и единиц длиныm.
Скажем, что s лексикографически меньше чемt если существует индексj∈ {1,...,n} , такой чтоsi=ti дляi =1,...,j-1иsj<tj.
Даноn строчек длиныm, требуется упорядочить строчки в лексикографическом порядке.
Доказать, что существует линейный алгоритм, решающий эту задачу, то есть алгоритм с временем
Введение 1.1.
Перечисление (перебор) 1.2.
Время работы алгоритмов 1.3.
Алгоритм сортировки слиянием 2.
Графы 2.1 Основные определения 2.2 Деревья, обходы и разрезы 2.3 Связность 2.4 Эйлеровы и двудольные графы 3.
Остовные деревья 3.1 Задача о минимальном остовном дереве 3.2 Задача о минимальном взвешенном ориентированном остовном дереве 3.3 Упаковка остовных деревьев 4.
Кратчайшие пути 4.1 Кратчайшие пути из одной вершины 4.2 Кратчайшие пути между всеми парами вершин 4.3 Задача о минимальном усредненном цикле 5.
Потоки в сетях 5.1 Теорема о максимальном потоке и минимальном разрезе 5.2 Теорема Менгера 5.3 Алгоритм Эдмонса-Карпа 5.4 Блокирующие потоки 5.5 Алгоритм Голдберга-Тарьяна 6.Максимальное паросочетание 6.1 Двудольное паросочетание 6.2 Матрица Татта 6.3 Теорема Татта 6.4 Алгоритм Эдмонса Матроиды 7.1 Независимые системы и матроиды 7.2 Жадный алгоритм для задачи максимизации независимой системы Литература
• Korte B., Vygen J.
Combinatorial Optimization: theory and algorithms.
(Algorithms and Combinatorics 21), Springer, Berlin, 2000.
• Пападимитриу Х., Стайглиц К.
Комбинаторная оптимизация.
Алгоритмы и сложность.
М.: Мир, 1985.
Век комбинаторной оптимизации
• Теория чисел ~ 4000 лет назад
• Геометрия ~ 2600 лет назад
• Анализ ~ 300 лет назад
• Алгебра ~ 200 лет назад ---------------------------------------------------- Комбинаторная оптимизация ~ 50 лет назад! Причина Тысячи проблем в экономике, военных приложениях, организации производства могут быть сформулированы как задачи комбинаторной оптимизации.
Производство печатных плат
• Даны: Множество точекp1 ,…,pnR2 .
• Найти: Перестановку : {1,...,n} {1,...,n} такую чтоd(pπ(i),pπ(i+1)) минимально.∑−=1ni Задача о назначении
• Даны: Множество чиселp1 ,…,pnR+ (длительность работ),mN рабочих, и непустое подмножествоSi⊆ {1,...,m} рабочих для каждой работыi∈ {1,...,n}.
• Найти: Числаxij∈R+(i=1 ,...,n;jSi) так что (i=1 ,...,n)и минимизирующее maxj.∑∈=iSiijpxj∑∈iSijxj:i Комбинаторная оптимизация Вычислительные проблемы ― не только задачки, которые должны быть решены;
они ― также объекты, которые заслуживают изучения.
Задачи и алгоритмы можно формализовать и изучать математически.
Х.
Пападимитриоу Задача разметки печатных плат
• Даны: Множество точекp1 ,…,pnR2 .
• Найти: Перестановку : {1,...,n} {1,...,n} такую чтоd(pπ(i),pπ(i+1)) минимально.∑−=1ni Алгоритм ??? Input:N точек … Найти оптимальный путь !!! Output: оптимальный путьNO Алгоритм ??? Input:N точек … Перебрать все возможные перестановки и выбрать оптимальную ! Output: оптимальный путьNO Перебор с возвратом (1, 1, … , 1, 1) (1, 1, … , 1,2 )(1, 1, … , 1,3) (1, 1, … , 1,n) (1, 1, … ,2 , 1) (1, 1, … , 2,2 )(1, 1, … , 2,3) (1, 1, … , 2,n) (1, 1, … ,3 , 1) (1, 1, … , 3,2 )(1, 1, … , 3,3) (1, 1, … , 3,n)
•
•
•
•
• •n шаговn! перестановок n! << nn Лексикографический порядок Определение 1.1 Пусть x,y∈Rn― два вектора.
Вектор x лексикографически меньше чем y , если существует индексj∈ {1,...,n }, такой чтоxi=yi дляi =1,...,j – 1 и xj<yj.
Алгоритм перебора путей Input: Натуральное числоn≥ 3 .
Множество{p1 ,…,pn} точек на плоскости Output: Перестановкаπ* :{1,...,n }→{1,...,n}, минимизирующая cost(π*): = d(p p (i),p p (i+1)).
1.
Setπ(i):=i,π*(i):=ifori =1,...,n.Seti:= n −1.
2.
Letk :=min({π(i)+1 ,…,n +1}\ {π(1) ,…, π(i)− 1}).3.Ifk≤ n then: Setπ(i):=k.If i= n& cost (π) < cost(π*) thenset π*:=π.If i< n thensetπ(i+ 1):=0 &i:=i+1.Ifk=n+1 thenseti := i − 1.Ifi≥ 3 then go to2.∑−=1ni Пример π := (1, 2, 3, 4, 5, 6 )i := 5k := 6π := (1, 2, 3, 4, 6,0 )i := 6k := 7k := 5π := (1, 2, 3, 4,6,5 ) ? cost(π) < cost(π*) ?k := 5π := (1, 2, 3,5, 0 , 5 )i := 5k := 4π := (1, 2, 3, 5, 4,0 )i := 6k := 6π := (1, 2, 3, 5,4,6 ) ? cost(π) < cost(π*) ?
•
• •i := 5i := 4 Полезное обозначение Определение 1.2 Пусть f , g:D R+ две функции.
Будем говорить, чтоf есть O(g) (и писать f = O(g)), если существуют константы α, β >0 , такие что f(x)≤ αg(x)+β для всехx∈D .
Если f = O(g)и g = O(f), то будем писать f = Θ(g).
Алгоритм перебора путей Input: Натуральное числоn≥ 3 .
Множество{p1 ,…,pn} точек на плоскости Output: Перестановкаπ* :{1,...,n }→{1,...,n}, минимизирующая cost(π*): = d(p p (i),p p (i+1)).
1.
Setπ(i):=i,π*(i):=ifori =1,...,n.Seti:= n −1.2.Letk :=min({π(i)+1 ,…,n +1}\ {π(1) ,…, π(i)− 1}).3.Ifk≤ n then: Setπ(i):=k.If i= n& cost (π) < cost(π*) thenset π*:=π.If i< n thensetπ(i+ 1):=0 &i:=i+1.Ifk=n+1 thenseti := i − 1.Ifi≥ 3 then go to2.∑−=1nik :=min({π(i)+1 ,…,n +1}\ {π(1) ,…, π(i)−1})•Forj := 1tondoaux(j ) := 0.•Forj := 1toi – 1doaux (π(j )) := 1.•Setk := π(i ) + 1.
• Whilek≤nandaux(k ) = 1dok:=k + 1.
Алгоритм
• Множество исходных данных (Вход)
• Последовательность инструкций, каждая из которых может быть представлена цепочкой элементарных шагов.
• Для каждого допустимого входа алгоритм в процессе вычисления выполняет единственно определенную серию элементарных шагов и выдает некоторый ответ.
Время работы алгоритма Определение 1.3 Пусть алгоритмA получает на входе множествоX,и пустьf:X→R+.
Если существует константа α >0 такая что алгоритмA заканчивает вычисления не более чем черезαf(x) элементарных шагов (включая арифметические операции) для любого входа x∈X, то будем говорить, чтоO(f) время работы алгоритмаA.
Размер входа
• Размер входа примера с рациональными данными равен числу бит требуемых для его двоичного представления.
Полиномиальный алгоритм
• Определение 1.4 Алгоритм с рациональным входом называется полиномиальным , если существует целоеk такое что алгоритм работает время O(nk ), гдеn есть размер входа и все числа, используемые алгоритмом в процессе вычислений ограничены величиной O(nk ) бит.
Алгоритм с произвольным входом называется сильно полиномиальным , если существует целоеk такое что алгоритм работает время O(nk ) на любом входе состоящим из n чисел и он полиномиальный на рациональном входе.
Если k=1 алгоритм называется линейным.
Таблица 1.1n100n logn 10n2n3.5nlogn 2n! 10 3μs 1μs 3μs 2μs 1μs4μs 30 15μs 9μs148μs20ms 1s>1015y 100 66μs100μs 10ms 5 h>1013y103 1ms 10ms 32s>1013y108 266s 3 y>1010y1012 46d>108y Таблица 1.2 1h100n logn10n2n3.5nlogn2n! (a)1.19*109 600003868 87 41 15 (b)10.8*109 1897377468 104 45 16 Алгоритм сортировки слиянием Input: Список a1 ,…,an действительных чисел.
Output: Перестановка :π {1,...,n} {1,...,n }, такая что aπ(i) ≤aπ(i+1) для всехi =1,...,n – 1.1.Ifn=1 thensetπ (1) :=1and stop (returnπ ).
2.
Set m:=[n/2].
Let :=ρ Merge-Sort(a1 ,…,am).
Let :=σ Merge-Sort(am+1 ,…,an).3.Set k:=1,l :=1.
Whilek≤m andl≤n–mdo:Ifa ρ(k)≤a m+σ(l) then set(πk+l– 1):= (ρk ) andk: = k +1.
else set (πk+l– 1):=m+ (σl ) andl: =l +1.
Whilek ≤ mdo:Setπ(k+l– 1):= (ρk ) andk: = k+1.
Whilel ≤ n-mdo:Setπ(k+l– 1):=m+ (σl ) andl: = l +1.
Время работы алгоритма Теорема 1.5 Алгоритм сортировки слиянием находит решение заO(n logn) элементарных операций.
Алгоритм сортировки слиянием Input: Список a1 ,…,an действительных чисел.
Output: Перестановка :π {1,...,n} {1,...,n }, такая что aπ(i) ≤aπ(i+1) для всехi =1,...,n – 1.1.Ifn=1 thensetπ (1) :=1and stop (returnπ ).
2.
Set m:=[n/2].
Let :=ρ Merge-Sort(a1 ,…,am).
Let :=σ Merge-Sort(am+1 ,…,an).3.Set k:=1,l :=1.
Whilek≤m andl≤n–mdo:Ifa ρ(k)≤a m+σ(l) then set(πk+l– 1):= (ρk ) and k:=k +1.
else set (πk+l– 1):=m+ (σl ) and l:= l +1.
Whilek ≤ mdo:Setπ(k+l– 1):= (ρk ) andk: = k+1.
Whilel ≤ n-mdo:Setπ(k+l– 1):=m+ (σl ) andl: = l +1.
Доказательство теоремы 1.5•T(n ) время работы алгоритма на примере сn числами.
• Грубо оценим шаг 3 сверху через 5n + 2.()1log122521+≤++=nTnTnTnT Упражнение 1.1 ()().log!log,n что ДоказатьΘ= Упражнение 1.2().logn,1ε+=nOn что Доказать Упражнение 1.3 Показать, что время работы алгоритма перебора путей естьO( n•n!).
Упражнение 1.4 Пустьs,t строчки из нулей и единиц длиныm.
Скажем, что s лексикографически меньше чемt если существует индексj∈ {1,...,n} , такой чтоsi=ti дляi =1,...,j-1иsj<tj.
Даноn строчек длиныm, требуется упорядочить строчки в лексикографическом порядке.
Доказать, что существует линейный алгоритм, решающий эту задачу, то есть алгоритм с временем