Лекция 2 | Алгоритмы для задачи коммивояжёра | Александр Куликов | Лекториум

YOUTUBE · 28.11.2025 03:08

Ключевые темы и таймкоды

Приближенные алгоритмы для задачи коммивояжера

0:15
  • Максимизационные алгоритмы отличаются от минимизационных.
  • Замена весов на противоположные не всегда применима в приближенных алгоритмах.
  • Задача коммивояжера связана с минимальным покрывающим деревом.

Минимальное покрывающее дерево

1:17
  • Минимальное покрывающее дерево связывает все вершины с максимальным весом.
  • Задача коммивояжера требует, чтобы дерево не ветвилось и степень каждой вершины была не больше двух.
  • Это усложняет задачу, делая её менее решаемой за линейное время.

Покрытие ориентированными циклами

2:39
  • Покрытие ориентированными циклами требует, чтобы каждая вершина была покрыта одним входящим и одним исходящим ребром.
  • Задача решается за полиномиальное время, если размер цикла не превышает трех.
  • Для неориентированных графов задача становится NP-трудной при размере цикла больше трех.

Алгоритм для покрытия циклами

6:10
  • Покрытие циклами можно решить за полиномиальное время, используя паросочетания.
  • Каждая вершина заменяется на две копии, и покрытие циклами соответствует паросочетанию.
  • Алгоритм находит покрытие циклами максимального веса и удаляет ребро минимального веса из каждого цикла.

Приближение для максимального цикла коммивояжера

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

Улучшение константы приближения

10:08
  • Улучшение константы приближения для максимального коммивояжера улучшает известные приближения для задачи над строкой.
  • Для евклидова коммивояжера известно почти идеальное приближение, называемое полимальной приближенной схемой PTAS.
  • PTAS была независимо предложена Авророй и Митчеллом в 1997 году.

Принцип работы PTAS

10:57
  • PTAS работает с параметром эпсилон, который определяет точность приближения.
  • Точки на плоскости заключаются в квадрат, который затем делится на более мелкие квадраты.
  • Вводятся порталы, которые позволяют найти путь, пересекающий только порталы, что улучшает структуру пути.

Максимизационная версия и полуребра

14:57
  • Для максимизационной версии коммивояжера существуют алгоритмы с приближениями 2/3 и 3/4.
  • Вводится понятие полуребер, которые позволяют найти покрытие без трициклов.
  • Это улучшает задачу, делая ее решаемой за полиномиальное время.

Метрический коммивояжер и ориентированные графы

15:56
  • Метрический коммивояжер рассматривается как частный случай, где веса берутся из кратчайшего расстояния в графе.
  • Для неориентированных графов известны оценки лучше, чем 1.5, а для ориентированных графов недавно получено константное приближение.

Точные алгоритмы

17:53
  • Точные алгоритмы находят решения, про которые можно доказать, что они работают за полиномиальное время.
  • Метод динамического программирования позволяет решить задачу за полиномиальное время, что является классическим подходом.

Динамическое программирование

18:38
  • Задача разбивается на подзадачи, которые решаются постепенно.
  • Важно не порядок обхода вершин, а пройденное расстояние.
  • Подзадача: найти кратчайший путь из вершины 1 в вершину j, обходя все остальные вершины.

Пересчет и оптимизация

19:35
  • Если путь оптимален, то любой его подпуть также оптимален.
  • Отрезаем последнее ребро и решаем подзадачи для оставшихся вершин.
  • Пересчет и оптимизация могут быть реализованы рекурсивно или с использованием мемоизации.

Реализация на Python

21:28
  • Граф сохраняется в переменную, затем создается таблица для записи значений.
  • Подмножества городов кодируются целыми числами.
  • Перебор подмножеств и пересчёт значений.

Работа с графами в Python

22:38
  • Использование библиотеки NetworkX для работы с графами.
  • Удобство работы с графами в Python: создание, поиск и рисование графов.
  • Возможность настройки отображения графов.

Практическая значимость

24:50
  • Динамическое программирование работает медленнее, чем факториал.
  • На практике важно учитывать память и производительность.
  • Алгоритм может не работать на больших графах из-за нехватки памяти.

Теория и практика

28:15
  • Теория и практика часто расходятся.
  • Примеры задач, которые решаются быстро на практике, несмотря на теоретическую сложность.
  • Задача SAT и её применение в решении сложных формул.

Введение в SAT

30:52
  • SAT используется для описания комбинаторных задач.
  • SAT-соревнования популярны и важны для верификации.
  • SAT- solvers могут находить выполняющие наборы и доказывать невыполнимость формул.

Формула включения исключений

32:51
  • Формула включения исключений позволяет решать задачу о гамильтоновом цикле без экспоненциальной памяти.
  • Динамическое программирование было введено для задачи о гамильтоновом цикле.
  • Формула включения исключений была переоткрыта несколько раз.

Применение формулы включения исключений

34:47
  • Формула используется для подсчета пересечений и объединений множеств.
  • В данном случае формула применяется для подсчета функций на подмножествах множества.
  • Формула включает коэффициенты, учитывающие размер подмножеств.

Доказательство формулы включения исключений

36:42
  • Доказательство формулы включает суммирование по подмножествам и учет коэффициентов.
  • Сумма равна нулю, если подмножество не содержит элемент.
  • Разбиение на пары подмножеств показывает, что четные и нечетные подмножества равны.

Применение к задаче о гамильтоновом пути

41:17
  • Формула включения исключений применяется для поиска гамильтонова пути.
  • Путь начинается и заканчивается в фиксированных вершинах.
  • Алгоритм остается экспоненциальным, но задача упрощается.

Определение множества и функции

42:18
  • Рассматривается множество вершин и подмножества.
  • Функция f от x определяет количество путей из n-1 ребра, которые проходят через множество x.
  • Пути могут проходить через вершины несколько раз.

Подсчет функции f

43:57
  • Функция f легко подсчитывается с помощью матрицы смежности графа.
  • Можно использовать динамическое программирование для подсчета путей.
  • Подсчет функции f возможен за полиномиальное время.

Определение функции g

45:40
  • Функция g отличается от f: пути из n-1 ребра должны посещать каждую вершину множества.
  • Подстановка всех вершин множества дает число гамильтоновых путей.

Формула включения-исключения

46:38
  • Функция f от x равна сумме всех подмножеств y, лежащих в x.
  • Это позволяет быстро считать функцию f для любого x.
  • Формула дает алгоритм с полиномиальной памятью и временем.

Применение метода включения-исключения

48:48
  • Метод включения-исключения используется для решения задачи раскраски графа.
  • Включение-исключение позволяет решать задачу за полиномиальное время.
  • Метод был забыт, но в 2010 году его снова начали использовать.

Алгоритм Йоркорквунда

50:11
  • Алгоритм работает для неориентированных графов и решает задачу гамильтонова цикла быстрее, чем за O n^2.
  • Для ориентированных графов задача остается открытой.
  • Алгоритм применим только для двудольных графов.

Динамическое программирование и формула включения-исключения

54:04
  • Динамическое программирование зависит от логарифма числа, а формула включения-исключения - от самого числа.
  • Формула включения-исключения решает более сложную задачу, чем динамическое программирование.
  • Матрица Тата используется для анализа графа.

Перманент матрицы

55:05
  • Перманент матрицы - это сумма произведений всех возможных перестановок элементов матрицы.
  • В перманенте учитываются все возможные перестановки и их знаки.
  • Перманент можно рассматривать как многочлен, который равен нулю, если в графе есть гамильтонов цикл.

Поле и многочлен

57:56
  • Перманент матрицы вычисляется в поле с характеристикой два.
  • Поле выбирается так, чтобы сумма любых двух элементов была равна нулю.
  • Многочлен, полученный из перманента, равен нулю, если в графе есть гамильтонов цикл.

Проверка многочлена на равенство нулю

59:44
  • Проверка многочлена на равенство нулю требует раскрытия скобок.
  • Для проверки используется полиномиальный тестинг, который использует случайные значения.
  • Вероятность ошибки уменьшается с увеличением размера поля.

Вероятность ошибки

1:02:34
  • Вероятность ошибки меньше или равна степени многочлена, деленной на размер поля.
  • При повторении эксперимента вероятность ошибки уменьшается.
  • В криптографических приложениях вероятность ошибки менее одного на два в сотый считается пренебрежимо малой.

Введение в многочлены и перманенты

1:05:11
  • Обсуждение многочленов и их связи с перманентами матриц.
  • Проблема с гамильтоновыми циклами в неориентированных графах.
  • Цель: сократить плохие покрытия циклами и сохранить гамильтоновы циклы.

Несимметризация матрицы

1:07:02
  • Преобразование матрицы для сохранения гамильтоновых циклов.
  • Введение новых переменных в первом столбце матрицы.
  • Разные обходы гамильтонова цикла теперь соответствуют разным маномам.

Проблема с циклами длины два

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

Двудольный граф и помеченный гамильтонов цикл

1:13:21
  • Преобразование графа в двудольный с пометками на ребрах.
  • Поиск помеченного гамильтонова цикла.
  • Замена переменных в матрице для учета пометок.

Заключение и дальнейшие шаги

1:16:20
  • Перманент матрицы теперь не равен нулю только при наличии гамильтонова цикла.
  • Введение новых видов мусора: покрытия циклами с более чем одним циклом и покрытия с неполными пометками.
  • Цель: сократить мусор и сохранить гамильтоновые циклы.

Формула включения исключений

1:18:31
  • Используется формула включения исключений для подсчета многочленов.
  • Рассматривается множество пометок и их подмножества.
  • Маномы, использующие все пометки, сокращаются по модулю два.

Гамильтоновы циклы и циклы длины два

1:20:56
  • Маномы, соответствующие циклам длины два, сокращаются.
  • В матрице такие маномы соответствуют симметричным элементам.
  • Пометки позволяют различать циклы длины два.

Завершающий слайд и вероятностные алгоритмы

1:23:17
  • Рассматривается перманент по всем множествам пометок.
  • Многочлен не равен нулю, если в графе есть гамильтонов цикл.
  • Лемма Шварца-Зиппеля используется для вероятностных алгоритмов.

Задача о k-пути

1:25:42
  • Задача о k-пути обобщает задачу о гамильтоновом цикле.
  • В неориентированных графах задача решается за O 1.66^k.
  • В ориентированных графах задача решается за O 2^k.

Двудольные графы и четность

1:26:51
  • В двудольных графах задача решается за O 3^n/2.
  • Вычисление четности в ориентированном графе помогает найти гамильтонов цикл.
  • Выкидывание ребер может оставить один гамильтонов цикл с высокой вероятностью.

Открытые задачи

1:29:52
  • Неизвестен алгоритм для ориентированных графов лучше, чем O 2^k.
  • Алгоритм Бьоркленда вероятностный и не может быть детерминирован.
  • Задача о k-пути решается за O 2.5^k, но улучшение до O 2^k было бы интересно.

Задача о на строке

1:31:21
  • Задача о на строке сводится к ориентированному коммивояжеру.
  • Решение задачи о на строке не может быть проще, чем решение задачи коммивояжера быстрее, чем за два войны.
  • Существует гипотеза, что жадный алгоритм для задачи о на строке дает два приближения, но доказать её пока не удалось.

Жадный алгоритм для задачи о на строке

1:32:18
  • Алгоритм заключается в наложении двух строк с наибольшим перекрытием и возвращении полученной строки.
  • Алгоритм простой и понятный, но его эффективность остаётся спорной.
  • Гипотеза о двух приближениях для этого алгоритма существует с 70-х годов, но доказательств нет.

Проблемы с генерацией строк

1:33:18
  • Случайное генерирование строк может не выявить контрпримеры для жадного алгоритма.
  • Строки с повторами могут быть специально созданы для проверки жадного алгоритма.
  • Решение задачи о на строке может доказать гипотезу и улучшить существующие приближенные алгоритмы.

Улучшение приближенных алгоритмов

1:34:09
  • Улучшение текущего алгоритма для задачи о на строке до двух-трех приближений было бы значительным достижением.
  • Вопрос о возможности обратного сведения: если есть быстрый алгоритм для задачи о на строке, может ли он ускорить коммивояжера?
  • Ответ на этот вопрос пока не ясен, но было бы интересно попробовать.

Заключение и вопросы

1:35:47
  • Вопросы и предложения по решению задач можно присылать на указанный адрес.
  • Автор заинтересован в решении задачи коммивояжера быстрее, чем за два войны.
Похожие пересказы
#0 [БАЗА] Вступление и Big O - Базовые структуры данных и алгоритмы
YOUTUBE 01.12.2025
Алгоритмы и структуры данных (С++), лекция №12 (осень)
YOUTUBE 01.12.2025
Алгоритмы и структуры данных 4. Суффиксный автомат
YOUTUBE 01.12.2025
Урок 1. Алгоритмы и структуры данных. Алгоритм линейного поиска
YOUTUBE 01.12.2025