Методы разработки алгоритмов

Методы разработки алгоритмов Лекция 13 Основные методы разработки алгоритмов ▪ Метод грубой силы (brute force, исчерпывающий поиск – полный перебор) ▪ Декомпозиция (decomposition, “разделяй и властвуй”) ▪ Уменьшение размера задачи (“уменьшай и властвуй”) ▪ Преобразование (“преобразуй и властвуй”) ▪ Жадные алгоритмы (greedy algorithms) ▪ Динамическое программирование (dynamic programming) ▪ Поиск с возвратом (backtracking) ▪ Локальный поиск (local search) 2 Метод грубой силы (brute force) ▪ Метод грубой силы (brute force) – решение “в лоб” ▪ Основан на прямом подходе к решению задачи ▪ Опирается на определения понятий, используемых в постановке задачи ▪ Пример Задача возведения числа 𝑎 в неотрицательную степень 𝑛 Алгоритм решения “в лоб” По определению 𝑎𝑛 = 𝑎 ∙ 𝑎 ∙ … ∙ 𝑎 𝑛 3 Метод грубой силы (brute force) Из определения следует простейший алгоритм function pow(a, n) pow = a for i = 2 to n do pow = pow * a end for return pow end function 𝑇𝑃𝑜𝑤 = 𝑂(𝑛) 4 Метод грубой силы (brute force) Примеры алгоритмов, основанных на методе грубой силы: ▪ Умножение матриц по определению 𝑂(𝑛3) ▪ Линейный поиск наибольшего/наименьшего элемента в списке ▪ Сортировка выбором (Selection sort, 𝑂(𝑛2)) ▪ Пузырьковая сортировка (Bubble sort, 𝑂(𝑛2)) ▪ Поиск подстроки в строке методом грубой силы ▪ Поиск перебором пары ближайших точек на плоскости ▪ … 5 Поиск подстроки в строке ▪ Поиск подстроки 𝑝 в строке 𝑠 методом грубой силы: function strstr(s, p) i=4 n = strlen(s) s H e l l o W o r l d m = strlen(p) p l o W o for i = 1 to n – m do j = 1 while j <= m and s[i + j - 1] = p[j] do j = j + 1 end while if j > m then return i end if end for end function 6 Поиск пары ближайших точек ▪ Задача. Во множестве из 𝑛 точек необходимо найти две, расстояние между которыми минимально (точки ближе других друг к другу) ▪ Координаты всех точек известны: 𝑃𝑖 = (𝑥𝑖 , 𝑦𝑖 ) ▪ Расстояние 𝑑(𝑖, 𝑗) между парой точек вычисляется как евклидово: 𝒅(𝒊, 𝒋) = (𝒙𝒊 – 𝒙𝒋)𝟐 + (𝒚𝒊 – 𝒚𝒋)𝟐 7 Поиск пары ближайших точек function SearchClosestPoints(x[1..n], y[1..n]) dmin = Infinity for i = 1 to n – 1 do for j = i + 1 to n do d = sqrt((x[i] – x[j])^2 + (y[i] – y[j])^2) if d < dmin then dmin = d imin = i jmin = j end if end for end for return imin, jmin end function Какова вычислительная сложность алгоритма? 8 Поиск пары ближайших точек function SearchClosestPoints(x[1..n], y[1..n]) dmin = Infinity for i = 1 to n – 1 do for j = i + 1 to n do d = sqrt((x[i] – x[j])^2 + (y[i] – y[j])^2) if d < dmin then dmin = d imin = i jmin = j end if end for end for return imin, jmin end function Какова вычислительная сложность алгоритма? 𝑻 = 𝑶(𝒏𝟐) 9 Метод декомпозиции (Decomposition) ▪ Метод декомпозиции (decomposition method, метод “разделяй и властвуй” – “divide and conquer”) ▪ Структура алгоритмов, основанных на этом методе: 1. Задача разбивается на несколько меньших экземпляров той же задачи 2. Решаются сформированные меньшие экземпляры задачи (обычно рекурсивно) 3. При необходимости решение исходной задачи формируется как комбинация решений меньших экземпляров задачи Problem Problem = SubProblemA + SubProblemB A B 10 Вычисление суммы чисел ▪ Задача. Вычислить сумму чисел 𝑎0, 𝑎1, . . , 𝑎𝑛−1 ▪ Алгоритм на основе метода грубой силы: function sum(a[0, n - 1]) sum = 0 for i = 0 to n - 1 do sum = sum + a[i] end for 𝑇𝑆𝑢𝑚 = 𝑂(𝑛) end function 11 Вычисление суммы чисел ▪ Задача. Вычислить сумму чисел 𝑎0, 𝑎1, . . , 𝑎𝑛−1 . ▪ Алгоритм на основе метода декомпозиции: 𝒂𝟎 + 𝒂𝟏 + ⋯ + 𝒂𝒏−𝟏 = 𝒂𝟎 + ⋯ + 𝒂 𝒏Τ𝟐 −𝟏 + 𝒂 𝒏Τ𝟐 + … + 𝒂𝒏−𝟏 4 + 5 + 1 + 9 + 13 + 11 + 7 = (4 + 5 + 1) + (9 + 13 + 11 + 7) = = ((4) + (5 + 1)) + ((9 + 13) + (11 + 7)) = 50 12 Вычисление суммы чисел int sum(int *a, int l, int r) { int k; if (l == r) return a[l]; k = (r - l + 1) / 2; return sum(a, l, l + k - 1) + sum(a, l + k, r); } int main() { s = sum(a, 0, N - 1); } 13 Вычисление суммы чисел Структура рекурсивных вызовов функции sum(0, 6) [0, 6] [0, 2] [0, 0] [1, 2] [1, 1] [3, 6] [3, 4] [2, 2] [3, 3] [5, 6] [4, 4] [5, 5] [6, 6] 4 + 5 + 1 + 9 + 13 + 11 + 7 = (4 + 5 + 1) + (9 + 13 + 11 + 7) = = ((4) + (5 + 1)) + ((9 + 13) + (11 + 7)) = 50 14 Возведение числа 𝑎 в степень 𝑛 ▪ Задача. Возвести число 𝑎 неотрицательную степень 𝑛 ▪ Решение. Алгоритм на основе метода декомпозиции: 𝑎𝑛 𝑛Τ2 ∙ 𝑎 𝑛− 𝑛Τ2 , 𝑛 > 1 𝑎 =ቊ 𝑎, 𝑛=1 int pow_decomp(int a, int n) { int k; if (n == 1) return a; } k = n / 2; return pow_decomp(a, k) * pow_decomp(a, n - k); 15 Метод декомпозиции (Decomposition) ▪ В общем случае задача размера 𝒏 делится на экземпляры задачи размера 𝒏 /𝒃, из которых 𝒂 требуется решить (𝑏 > 1, 𝑎 ≥ 0) ▪ Время 𝑇(𝑛) работы алгоритмы, основанного на методе декомпозиции, равно 𝑻(𝒏) = 𝒂𝑻(𝒏 / 𝒃) + 𝒇(𝒏), (*) где 𝑓(𝑛) – функция, учитывающая затраты времени на разделение задачи на экземпляры и комбинирование их решений ▪ Рекуррентное соотношение (*) – это обобщённое рекуррентное уравнение декомпозиции (general divide-and-conquer recurrence) 16 Метод декомпозиции (Decomposition) ▪ Теорема. Если в обобщённом рекуррентном уравнении декомпозиции функция 𝑓(𝑛) = Θ(𝑛𝑑), где 𝑑 ≥ 0, то вычислительная сложность алгоритма равна Θ 𝑛𝑑 , 𝑇 𝑛 = Θ 𝑛𝑑 log 𝑛 , Θ 𝑛log𝑏 𝑎 , если 𝑎 < 𝑏 𝑑 , если 𝑎 = 𝑏 𝑑 , если 𝑎 > 𝑏 𝑑 . 17 Анализ алгоритма суммирования 𝑛 чисел ▪ 𝑏 = 2 (интервал делим на 2 части) ▪ 𝑎 = 2 (обе части обрабатываем) ▪ 𝑓(𝑛) = 1 (трудоемкость разделения интервала на 2 подмножества и слияние результатов (операция “+”) выполняется за время 𝑂(1)) 𝑇(𝑛) = 2𝑇(𝑛 / 2) + 1 ▪ Так как 𝑓(𝑛) = 1 = 𝑛0, следовательно 𝑑 = 0, тогда согласно теореме сложность алгоритма суммирования 𝑛 чисел 𝑇 𝑛 = 𝜃 𝑛log22 = 𝜃 𝑛 18 18 Метод декомпозиции (Decomposition) ▪ Примеры алгоритмов, основанных на методе декомпозиции: ❑ Сортировка слиянием (MergeSort) ❑ Быстрая сортировка (QuickSort) ❑ Бинарный поиск (Binary Search) ❑ Обход бинарного дерева (Tree traverse) ❑ Решение задачи о поиске пары ближайших точек ❑ Решение задачи о поиске выпуклой оболочки ❑ Умножение матриц алгоритмом Штрассена ❑… 19 Динамическое программирование ▪ Динамическое программирование (Dynamic programming) – метод решения задач (преимущественно оптимизационных) путем разбиения их на более простые подзадачи ▪ Решение задачи идет от простых подзадач к сложным, периодически используя ответы для уже решенных подзадач (как правило, через рекуррентные соотношения) ▪ Основная идея – запоминать решения встречающихся подзадач на случай, если та же подзадача встретится вновь ▪ Теория динамического программирования разработана Р. Беллманом в 1940-50-х годах 20 Последовательность Фибоначчи 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … 𝑭(𝒏) = 𝑭(𝒏 – 𝟏) + 𝑭(𝒏 – 𝟐), при 𝒏 > 𝟏 𝑭(𝟎) = 𝟎, 𝑭(𝟏) = 𝟏 ▪ Задача Вычислить 𝑛-й член последовательности Фибоначчи 𝐹(𝑛) = ? 21 Последовательность Фибоначчи function Fibo(n) if n <= 1 then return n end if return Fibo(n - 1) + Fibo(n - 2) end function 22 Последовательность Фибоначчи Fibo(5) Fibo(3) Fibo(4) Fibo(3) Fibo(2) Fibo(1) Fibo(1) Fibo(0) Fibo(2) Fibo(1) Fibo(0) Fibo(2) Fibo(1) Fibo(1) Fibo(0) Рекурсивные вызовы функции Fibo Некоторые элементы последовательности вычисляются повторно: Fibo(3), Fibo(2), … 23 Последовательность Фибоначчи function Fibo(n) F[0] = 0 F[1] = 1 for i = 2 to n do F[i] = F[i - 1] + F[i - 2] end for return F[n] end function В динамическом программировании используются таблицы, в которых сохраняются решения подзадач (жертвуем памятью ради времени) 24 “Жадные” алгоритмы (Greedy) ▪ “Жадный” алгоритм (Greedy algorithms) – алгоритм, принимающий на каждом шаге локально-оптимальное решение ▪ Предполагается, что конечное решение окажется оптимальным ▪ Примеры “жадных” алгоритмов: o алгоритм Прима o алгоритм Крyскала o алгоритм Дейкстры o алгоритм Хаффмана (кодирования) 25 Задача о размене ▪ Задача Имеется неограниченное количество монет номиналом (достоинством) 𝑎1 < 𝑎2 < … < 𝑎𝑛 ▪ Требуется выдать сумму 𝑆 наименьшим числом монет ▪ Пример Имеются монеты достоинством 1, 2, 5 и 10 рублей Выдать сумму S = 27 рублей ▪ “Жадное” решение (алгоритм): 2 монеты по 10 руб., 1 по 5, 1 по 2 ▪ На каждом шаге берётся наибольшее возможное количество монет достоинства 𝑎𝑛 (от большего к меньшему) 26 Задача о размене ▪ Задача Имеется неограниченное количество монет номиналом (достоинством) 𝑎1 < 𝑎2 < … < 𝑎𝑛 ▪ Требуется выдать сумму 𝑆 наименьшим числом монет ▪ Пример Имеются монеты достоинством 1, 2, 5 и 10 рублей Выдать сумму S = 27 рублей ▪ Решение жадным алгоритмом: 3 по 7, 3 по 1 = 6 монет ▪ Оптимальное решение: 2 по 7, 2 по 5 = 4 монеты 27 Код Хаффмана ▪ Деревья Хаффмана (Huffman) и коды Хаффмана используются для сжатия информации путем кодирования часто встречающихся символов короткими последовательностями битов ▪ Предложен Д. А. Хаффманом в 1952 году (США, MIT) 28 Код Хаффмана ▪ Задано множество символов и известны вероятности их появления в тексте (в файле) ▪ 𝐴 = {𝑎1, 𝑎2, … , 𝑎𝑛} – множество символов (алфавит) ▪ 𝑃 = {𝑝1, 𝑝2, … , 𝑝𝑛} – вероятности появления символов ▪ Требуется каждому символу сопоставить код – последовательность битов (codeword) С(𝐴, 𝑃) = {𝑐1, 𝑐2, … , 𝑐𝑛} Пример Символ A B C D _ Код (биты) 11 100 00 01 101 29 Код Хаффмана ▪ Шаг 1. Создается 𝑛 одноузловых деревьев ▪ В каждом узле записан символ алфавита и вероятность его повеления в тексте A 0.35 B 0.1 C 0.2 D 0.2 _ 0.15 30 Код Хаффмана ▪ Шаг 2. Находим два дерева с наименьшими вероятностями и делаем их левым и правым поддеревьями нового дерева – создаем родительский узел ▪ В созданном узле записываем сумму вероятностей поддеревьев ▪ Повторяем шаг 2 пока не получим одно дерево На каждом шаге осуществляется “жадный выбор” – выбираем два узла с наименьшими вероятностями 31 Код Хаффмана _ B C D A Символ B _ C D A Вероятность 0.1 0.15 0.2 0.2 0.35 32 Код Хаффмана _ B C D A 0.25 Символ Вероятность B _ 0.25 C D A 0.2 0.2 0.35 33 Код Хаффмана C D Вероятность C D 0.4 A 0.25 0.4 Символ _ B B, _ A 0.25 0.35 34 Код Хаффмана _ B C D 0.25 0.4 Символ Вероятность C 0.6 D 0.4 A B, _ A 0.6 35 Код Хаффмана _ B C A 0.2 5 D 0.6 0.4 1.0 root 36 Код Хаффмана C D 1 0.4 B _ 1 A 0.25 1 0.6 1 ▪ Левое ребро – 1 ▪ Правое ребро – 0 Символ A Код 11 B 100 C D 00 01 _ 101 1.0 ▪ Часто встречающиеся символы получили короткие коды ▪ Ни один код не является префиксом другого 37 Поиск с возвратом ▪ Поиск с возвратом (Backtracking) – метод решения задач, в которых необходим полный перебор всех возможных вариантов в некотором множестве М ▪ “Построить все возможные варианты …”, “Сколько существует способов …”, “Есть ли способ …”. ▪ Термин Backtrack введен в 1950 г. D. H. Lehmer ▪ Примеры задач: o Задача коммивояжёра o Подбор пароля o Задача о восьми ферзях o Задача о ранце o Раскраска карты 38 Поиск выхода из лабиринта 6 1 1 1 1 1 1 1 9 1 1 1 1 6 строк, 9 столбцов 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Старт: cтрока 1, столбец 1 ▪ 1 – стена ▪ 0 – проход ▪ Разрешено ходить влево, вправо, вверх и вниз Поиск выхода из лабиринта int main(int argc, char **argv) { if (argc < 2) { fprintf(stderr, "usage: maze \n"); exit(1); } load_maze(argv[1]); print_maze(); backtrack(startrow, startcol); printf("Exit not found\n"); } return 0; Поиск выхода из лабиринта void backtrack(int row, int col) { int drow[4] = {-1, 0, 1, 0}; int dcol[4] = {0, 1, 0, -1}; int nextrow, nextcol, i; maze[row][col] = 2; // Встали на новую позицию if (row == 0 || col == 0 || row == (nrows - 1) || col == (ncols - 1)) { print_maze(); // Нашли выход } } for (i = 0; i < 4; i++) { nextrow = row + drow[i]; nextcol = col + dcol[i]; if (maze[nextrow][nextcol] == 0) backtrack(nextrow, nextcol); } maze[row * ncols + col] = 0; // Проход есть? Поиск выхода из лабиринта 1 1 1 1 1 1 1 2 1 1 1 2 1 1 2 1 1 1 1 2 1 2 2 2 1 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Задача о восьми ферзях ▪ Классическая ф ормулировка Расставить на стандартной 64-клеточной шахматной доске 8 ферзей (королев) так, чтобы ни один из них не находился под боем другого ▪ Альтернативная ф ормулировка Заполнить матрицу размером 8×8 нулями и единицами таким образом, чтобы сумма всех элементов матрицы была равна 8, при этом сумма элементов ни в одном столбце, строке или диагональном ряде матрицы не превышала единицы 43 Задача о восьми ферзях ▪ Задача впервые была решена в 1850 г. Карлом Фридрихом Гаубом (Carl Friedrich Gaub) ▪ Число возможных решений на 64-клеточной доске: 92 44 Задача о восьми ферзях 1 X 45 Задача о восьми ферзях 1 X X X X X X X … 2 46 Задача о восьми ферзях 1 X X X X X X X X 3 … X X 2 X X X … 47 Задача о восьми ферзях 1 X X X X X X X X … X X X X 2 X … 3 … 8 48 Задача о восьми ферзях enum { N = 8 }; int board[N][N]; int main() { int i, j; for (i = 0; i < N; i++) { for (j = 0; j < N; j++) { board[i][j] = 0; } } } backtrack(0); return 0; 49 Задача о восьми ферзях void backtrack(int row) { int col; if (row >= N) { print_board(); } } for (col = 0; col < N; col++) { if (is_correct_order(row, col)) { board[row][col] = 1; // Ставим ферзя backtrack(row + 1); board[row][col] = 0; // Откат } } 50 Задача о восьми ферзях int is_correct_order(int row, int col) { int i, j; if (row == 0) return 1; X /* Проверка позиций сверху */ for (i = row - 1; i >= 0; i--) { if (board[i][col] != 0) return 0; } /* Проверить левую и правую диагонали... */ } return 1; 51 Задача о восьми ферзях 1 1 1 1 1 1 1 1 52 Задача о раскраске графа в k цветов ▪ Имеется граф 𝐺 = (𝑉, 𝐸) состоящий из 𝑛 вершин ▪ Каждую вершину надо раскрасить в один из 𝑘 цветов так, чтобы смежные вершины были раскрашены в разные цвета Пример раскраски 10 вершин графа в 3 цвета 53 Задача о раскраске графа в k цветов int main() { backtracking(1); } void backtracking(int v) { if (v > nvertices) { print_colors(); return; /* exit(0) */ } } for (i = 0; i < ncolors; i++) { color[v - 1] = i; if (is_correct_color(v)) backtracking(v + 1); color[v - 1] = -1; } 54 Задача о раскраске графа в k цветов /* * Граф представлен матрицей смежности */ int is_correct_color(int v) { int i; } for (i = 0; i < nvertices; i++) { if (graph_get_edge(g, v, i + 1) > 0) if (colors[v - 1] == colors[i]) return 0; } return 1; 55 Литература ▪ [Levitin] Раздел о методах разработки алгоритмов 56