Задача Коммивояжёра Метод ветвей и границ Часть 2/3 Запись занятия 2021 12 20

• Разбор метода ветвей и границ с датчиками вояжера.  

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

• Переход к реализации на Python.  

• Создание массива минимумов по строкам матрицы.  

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

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

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

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

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

• Создание словаря для хранения пар ключ-значение.  

• Поиск ключа с максимальным значением в словаре.  

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

• Возвращение значений при использовании бесконечности.  

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

• Создание новой матрицы для продолжения алгоритма.  

• Повторение всех шагов алгоритма для новой матрицы.  

• Учитывание изменений в количестве строк и столбцов.  

• Рассматривается процесс минимизации матрицы.  

• Заменяются значения в матрице.  

• Проверяется размер матрицы и транспонирование.  

• Проверяется правильность транспонирования.  

• Обсуждается редуцированная матрица и её минимизация.  

• Подписываются значения в матрице.  

• Рассматривается рекурсивное решение задачи.  

• Обсуждаются варианты выбора ребер и их стоимость.  

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

• Обсуждаются важные моменты реализации алгоритма.  

• Рассматривается матрица смежности и её заполнение.  

• Обсуждаются ошибки в статьях по задачам вояжера.  

• Используется онлайн калькулятор для решения задачи.  

• Вводится матрица и проверяется решение.  

• Обсуждается точность онлайн калькулятора.  

• Метод ветвей и границ является приближенным методом.  

• Обсуждается точность метода и его недостатки.  

• Планируется улучшение алгоритма с помощью рекурсии.  

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

• Планируется создание функции для реализации метода.  

• Обсуждаются аргументы функции и их назначение.  

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

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

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

• Рекурсивное решение включает подсчет ребер, вычеркивание строк и столбцов, транспонирование и редукцию.  

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

• Пример: ребро 2-5 и ребро 1-2, где ребро 2-1 не может быть запрещено из-за вычеркнутой строки.  

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

• Алгоритм должен проверять наличие циклов, так как ребер может быть много.  

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

• Поиск в глубину называется DFS.  

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

• Вершина, с которой начинается поиск, красится в серый цвет.  

• Если вершина белая, запускается DFS из нее, если серая, то был цикл, и вершина красится в черный цвет.  

• Обсуждение работы алгоритма на примере графа.  

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

• Алгоритм начинает с первой вершины и красит её в серый цвет.  

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

• Если ближайшая вершина серая, то цикл найден.  

• Пример с циклом 0, 1, 2.  

• Алгоритм переходит к седьмой вершине и красит её в серый цвет.  

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

• Цикл найден, так как шестая вершина становится серой.  

• Опасение, что алгоритм может вернуться в начальную вершину.  

• Демонстрация алгоритма с расставленными стрелками.  

• Алгоритм находит цикл, несмотря на случайное расположение стрелок.  

• Модернизация алгоритма для возврата true при нахождении цикла.  

• Проверка работы алгоритма на графе без циклов.  

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

• Идея сократить глубину рекурсии для быстрого обнаружения циклов.  

• Если цикл найден, нужно сразу выйти из рекурсии.  

• Проблема с перекраской вершин в черный цвет при обнаружении цикла.  

• Пример с графом, где вершины перекрашиваются в серый цвет и передаются обратно.  

• Алгоритм для ациклического графа, где вершины перекрашиваются в черный цвет.  

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

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

• Запуск DFS только если "сайкл" равен false.  

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

• Реализация функции DFS с проверкой на наличие циклов.  

• Проверка ребер на наличие циклов перед добавлением их в список смертности.  

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

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

• Рекурсивный вызов с редуцированной матрицей.  

• Запрещение ребер в транспонированной матрице.  

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

• Список смежности содержит ребра, уже вошедшие в ответ.  

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

• Проверка на зацикливание: если ребро взято, исключаем зацикливание.  

• Использование двух бесконечностей для проверки.  

• Запуск DFS и добавление ребра в список смежности.  

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

• Обновление нумерации в списке смежности.  

• Создание копии для сохранения старой нумерации.  

• Запуск DFS из добавленной вершины.  

• Проверка на наличие цикла и установка флага.  

• Запрещение ребра, если оно найдено.  

• Проверка всех элементов уменьшенной матрицы.  

• Запрещение ребер, если они не бесконечность.  

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

• Проверка готовности к рекурсии.  

• Удаление запрещенного ребра из матрицы.  

• Обновление номеров строк и столбцов.  

• Удаление ребер по значению, а не по индексу.  

• Обновление списка смежности.  

• Удаление обновленного списка смежности.  

• Обновление имен строк и столбцов.  

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

• Перемещение процесса запрета ребра в начало.  

• Поиск цикла в старой или новой матрице.  

• Сохранение позиций через кортежи.  

• Повторение процесса вырезания строки и столбца.  

• Проверка наличия обратного ребра.  

• Установка обратного ребра в бесконечность.  

• Удаление ненужных операций при построении транспонированной матрицы.  

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

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

• Тезисное повторение проделанной работы.  

• Найдена нижняя граница целевой функции.  

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

• Написаны функции для поиска циклов и наиболее важного ребра.  

• Позитивный вариант: вырезание строки и столбца, установка обратного ребра на бесконечность.  

• Негативный вариант: запрет ребра.  

• Сравнение оценок: если негативная оценка выгоднее, позитивная оценка игнорируется.  

• Удаление строк и столбцов из массива имен.  

• Обновление списка смежности и матрицы.  

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

• Алгоритм останавливается, когда остается матрица 2x2.  

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

• В этом случае выбирается позитивный вариант.  

• Матрица 2x2 всегда приводит к позитивному ответу.  

• Проверка текущего ответа: если текущий ответ лучше предыдущего, он обновляется.  

• Пример на дереве решений: улучшение ответа с 44 до 42.  

• Добавляем переменную в глобальный словарь.  

• Копируем словарь через срез.  

• Проверяем, что найденный тур не превышает текущую оценку.  

• Проверяем длину найденного тура.  

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

• Проверяем равенство и приоритет.  

• Запускаем код и проверяем ошибки.  

• Ошибки связаны с глобальными и локальными переменными.  

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

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

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

• Исправляем ошибки в рекурсии и поиске лучшего ребра.  

• Анализируем работу алгоритма на примере.  

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

• Печатаем оценки и бест эйч для отладки.  

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

• Призываем участников зарегистрироваться на олимпиаду СПбГУ.  

• Завершаем запись и анонсируем третью часть задачи.