- •Временная сложность алгоритмов
- •Задачи решимости, задачи оптимизации
- •Применение полного перебора для решения задачи коммивояжера. Перебор всех перестановок. Простой рекурсивный алгоритм
- •Применение полного перебора для решения задачи о рюкзаке. Перебор всех подмножеств множества. Сведение к перебору двоичных векторов. Коды Грея.
- •Общая схема метода ветвей и границ. Применение метода ветвей и границ для решения задачи о рюкзаке
- •Динамическое программирование
- •Жадные алгоритмы. Задача о выборе заявок. Свойства задач, для которых применимы жадные алгоритмы.
- •Эвристические методы решения задач. Эвристика жадного выбора и локального поиска. Примеры. Задача о покрытии, задача о камнях. Метаэвристики
- •Абстрактные типы данных. Атд стек, очередь, корневое дерево, множество, словарь, очередь с приоритетом, система непересекающихся множеств, граф и способы их реализации
- •Обходы графа. Поиск в глубину, поиск в ширину
Применение полного перебора для решения задачи о рюкзаке. Перебор всех подмножеств множества. Сведение к перебору двоичных векторов. Коды Грея.
Определение: Задача о рюкзаке: Дан рюкзак грузоподъёмности V и n предметов с указанной ценностью aj > 0 и весом cо > 0. Цель: Заполнить рюкзак, получив наибольшую ценность.
Вариант решения полным перебором с помощью алгоритма генерации кодов Грея:
Вариант решения поиска с возвратом с помощью рекурсий векторов 0-1:
Общая схема метода ветвей и границ. Применение метода ветвей и границ для решения задачи о рюкзаке
Определение: Задача о рюкзаке: Дан рюкзак грузоподъёмности V и n предметов с указанной ценностью aj > 0 и весом cо > 0. Цель: Заполнить рюкзак, получив наибольшую ценность.
Определение: Метод ветвей и границ (Branch and Bound) основан на комбинировании перебора и оценки наборов предметов, чтобы исключить неперспективные варианты и сократить поиск оптимального решения.
Определение: Ветвление - это функция β, которая каждому подмножеству A множества Ω ставит в соответствие некоторое его разбиение. Если |A| > 1, то β(A) = {A1, A2, ..., Ak } Если |A| ≤ 1, то β(A) = ∅.
О пределение: Оценка - это функция ψ : 2Ω → R, для которой ψ(A) ≥ φ(x) для всех x ∈ A; ψ(A) = φ(x), если A = {x}. Величина ψ(A) оценивает сверху значения функции φ на множестве A и совпадает с ней на множествах, состоящих из одного элемента. Для вычисления оценки решается упрощенная оптимизационная задача.
При этом на каждом шаге обновляем рекорд при обнаружении лучшего решения.
Метод ветвей и границ относится к классу точных методов. Он позволяет сократить число рассматриваемых вариантов решений по сравнению с полным перебором, но в худшем случае сводится к нему.
Динамическое программирование
Определение: Динамическое программирование (Dynamic Programming) - это метод решения сложных задач, которые можно разбить на более простые подзадачи и затем комбинировать их оптимальным образом. Он использует идею сохранения промежуточных результатов для избегания повторных вычислений и повышения эффективности.
Определение: Задача линейного раскроя: Дан стержень длины L и n видов деталей. Деталь вида j имеет длину aj > 0 и цену cj > 0, j = . Цель: раскроить стержень на детали с максимальной стоимостью по итогу.
Временная сложность алгоритма: O(L*n)
Решение для задачи о рюкзаке:
Определение: Задача про перемножение матриц (выбор скобок): Дан набор матриц, требуется найти оптимальный порядок их перемножения с минимальным количеством умножений.
Код алгоритм:
for i = 1 to n do fii = 0 i = 1, j = 2, t = 2 while j – i < n do fij = ∞ for k = i to j – 1 do q = fik + fk+1j + pi-1pkpj if q < fij then fij = q, gij = k i++, j++ if j = n then i = 1, t++, j = t
Код перемножения матриц: Запуск: MULT(1, n) MULT(i, j) if j > i then X = MULT(i, gij) Y = MULT(gij+1, j) return XY else return Mi
4. Задача о наибольшей общей подпоследовательности (Longest Common Subsequence, LCS):
Формулировка: Даны две последовательности элементов, требуется найти подпоследовательность наибольшей длины.
5. Задача коммивояжера (Traveling Salesman Problem):
Даны города, нужно каждый из них обойти наикратчайшим путём единожды, вернувшись в конце к исходному.
Матмодель: Поиск гамильтонова цикла в графе, где вершины – города, а грани – дороги между ними.
Время: O(n22n)
Свойства задач, для которых применимо динамическое программирование:
- Можно разбить на подзадачи, что оптимально скажется на вычислении решения. - Обладает перекрывающимися подзадачами, т.е. вычисление оптимального решения для одной подзадачи может потребоваться для вычисления оптимального решения других подзадач.
Сравнение с полным перебором: Динамическое программирование использует принцип оптимальной подструктуры и сохраняет результаты промежуточных вычислений, что позволяет избежать повторных вычислений и значительно ускоряет процесс. На что полный перебор не способен)