Тренировки по алгоритмам 4.0. Лекция 4: Перебор и методы его оптимизации

• Существуют задачи, которые невозможно решить за полиномиальное время.  

• В контексте лекции рассматриваются задачи, которые нужно решать, даже если нет эффективного решения.  

• Пример задачи: расстановка ферзей на поле nxn.  

• Задача: расставить n ферзей на поле nxn так, чтобы они не били друг друга.  

• Ферзь ходит по горизонтали, вертикали и диагонали.  

• Решение: перебор всех возможных расстановок и проверка их на соответствие условиям.  

• Перебор представляет собой рекурсивную функцию с параметрами.  

• В задаче расстановки ферзей нужно ставить ферзя в каждую клетку или пропускать её.  

• Важно учитывать количество оставшихся ферзей и номер клетки в рекурсивной функции.  

• Не обязательно доходить до конца рекурсии, если уже поставлено нужное количество ферзей.  

• Это сокращает время выполнения и уменьшает количество действий.  

• Важно обрезать дерево перебора как можно раньше.  

• В одну строку и столбец ставить двух ферзей бессмысленно.  

• Рекурсивная функция принимает параметр номер столбца для постановки ферзя.  

• Проверка на соответствие условиям осуществляется после постановки всех ферзей.  

• Проверка на плохие случаи: все ферзи в одной строке или столбце.  

• Обрезка дерева перебора на ранних этапах для экономии действий.  

• Проверка всех возможных перестановок чисел от 1 до n для генерации всех комбинаций.  

• Генерация перестановок и проверка на соответствие условиям.  

• Оптимизация дерева перебора для сокращения времени выполнения.  

• Важность ручного написания генерации перестановок для более ранней обрезки дерева.  

• Дерево перестановок с четырьмя вариантами на каждом слое.  

• Проверка диагоналей позволяет быстрее отсекать неверные варианты.  

• Пример: проверка правильности расстановки ферзей.  

• Проверка диагоналей помогает избежать ненужных переставлений.  

• Ускорение перебора за счет фиксации количества предыдущих ферзей.  

• Использование рекурсивной функции для генерации перестановок.  

• Запрещенные горизонтали и вертикали для предотвращения неверных перестановок.  

• Использование массива для хранения запрещенных горизонталей.  

• Оптимизация проверки диагоналей для ускорения перебора.  

• Проверка диагоналей вместо перебора всех предыдущих ферзей.  

• Введение булевых массивов для диагоналей.  

• Упрощение проверки и добавления новых ферзей.  

• Оптимизация может как ускорить, так и замедлить решение.  

• Важность практических экспериментов для оценки эффективности.  

• Переход к задаче коммивояжера.  

• Рассматривается полный граф, где каждое ребро имеет вес, например, время в минутах.  

• Задача: доставить товары из интернет-магазина, используя одну машину.  

• Важно минимизировать время доставки, посетив все вершины графа.  

• Важно учитывать время доставки и порядок загрузки товаров.  

• Задача: посетить все вершины графа за наименьшее время.  

• Пример: маршрут с минимальным временем может быть найден через перебор всех возможных маршрутов.  

• Гамильтонов цикл: посещение всех вершин графа.  

• Жадный алгоритм: выбор ближайшей непосещенной точки.  

• Пример с регулярной сеткой: жадный алгоритм может выбрать неправильную точку.  

• Перебор всех перестановок для выбора оптимального маршрута.  

• Проблема: перебор всех перестановок занимает много времени.  

• Решение: использование рекурсивной функции для отсечения неэффективных маршрутов.  

• Рекурсивная функция для перебора перестановок и отсечения неэффективных маршрутов.  

• Учет веса ребер и их влияния на время доставки.  

• Пример: односторонние дороги могут значительно увеличить время доставки.  

• Учет текущего маршрута и количества оставшихся вершин для доставки.  

• Использование минимального ребра для оценки времени оставшегося пути.  

• Пример: если ближайшее ребро имеет вес два, то оставшаяся часть пути займет не менее двух минут.  

• Оценка оставшегося пути помогает отсекать ненужные ветви перебора.  

• Важно, чтобы оценка считалась быстро, чтобы не тормозить выполнение программы.  

• Быстрая оценка позволяет отсекать ветки раньше, что ускоряет процесс.  

• Для каждой вершины запоминается минимальное инцидентное ребро.  

• Сумма минимальных ребер для всех вершин гарантирует, что путь не будет меньше определенного значения.  

• Оценка снизу помогает определить, когда нужно прекратить поиск пути.  

• Оценка обновляется на каждом шаге перебора.  

• Удаление посещенных вершин и добавление новых помогает поддерживать актуальную оценку.  

• Быстрая и эффективная оценка позволяет отсекать ветки раньше и улучшать производительность.  

• Можно улучшить оценку, перебирая всех соседей и выбирая минимальное ребро, ведущее в непосещенные вершины.  

• Это может привести к более точной оценке, но требует перебора всех соседей, что может замедлить процесс.  

• Оптимизации могут работать лучше или хуже в зависимости от конкретной задачи и графа.  

• Важно найти хороший начальный путь для перебора.  

• Случайный путь может быть плохим, поэтому лучше использовать жадный алгоритм для начального пути.  

• Жадный алгоритм может дать неплохой путь, который можно улучшить с помощью перебора с отсечением.  

• Алгоритм включает поиск начального пути жадным алгоритмом и перебор с отсечением.  

• Отсечение происходит на основе оценки оставшегося пути.  

• Это позволяет увеличить количество мест для решения задачи, что может быть полезно в конкурентной борьбе.  

• Задача не связана с домашней работой, но интересна.  

• Нужно построить цикл, посещая подмножество вершин.  

• Важно посетить все вершины как можно быстрее.  

• Можно посетить подмножество вершин разными способами.  

• Перебор всех путей занимает много времени.  

• Нужен только лучший способ посещения вершин.  

• Перебор плохих способов замедляет решение.  

• Нужно научиться понимать, когда рекурсия не приносит пользы.  

• Динамическое программирование по подмножеству.  

• Подмножества можно представить как двоичные числа.  

• Единица означает, что элемент входит в подмножество.  

• Маленькие подмножества удобно представлять в виде двоичных чисел.  

• Добавление элемента в подмножество: поставить единичку в нужное место.  

• Проверка и удаление битов для элементов.  

• Множество представляется как бит-маска, что важно для работы.  

• Рассматривается задача нахождения оптимального пути через множество вершин.  

• Используется метод динамического программирования для минимизации общего веса пути.  

• Перебираются все возможные варианты предпоследней вершины и прибавляется вес ребра из предпоследней в текущую вершину.  

• Сложность алгоритма составляет O 2^n * n^2, что значительно меньше, чем n! для больших значений n.  

• Для 20 вершин алгоритм работает за одну-две секунды на современном компьютере.  

• Оптимизация перебора и использование двоичной системы счисления для перебора подмножеств.  

• Алгоритм полезен не только в логистике, но и в других задачах, таких как управление дорогим станком.  

• Оптимизация перемещения сверла для экономии времени и ресурсов.  

• В задачах с большим количеством вершин могут потребоваться эвристические решения.  

• Объяснение, почему диагонали в матрице характеризуются уникальными суммами.  

• Алгоритм Дейкстры не решает задачу коммивояжера, так как не учитывает все промежуточные пункты.  

• Дейкстра может быть полезна на этапе построения полного графа для задачи доставки.  

• Важно научиться писать перебор и использовать отсечения для оптимизации.  

• Если задача не решается на конкретном языке программирования, это будет проверено и исправлено.  

• Прощание и приглашение на разбор задач.