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

Разбираем алгоритм решения задачи коммивояжёра методом ветвей и границ на взвешенном ориентированном графе. Сначала ручное исполнение, затем начало переписывания алгоритма на python.

#python #TSP #Travel_Salesman_Problem #Branch_and_Bound #ориентированный #ориентированный_граф #взвешенный #взвешенный_граф #dict #enumerate #list #max #lambda #рекурсия #транспонирование #редуцирование #back_tracking #дерево_решений

[EgorKo]

Спасибо вам огромное, объяснение и решение выше всяких похвал!
Вы мне очень помогли

[Ржавая_шпага]

Спасибо за видео! Очень помогло, наконец-то понял как работает этот метод. Надеюсь сдам экзамен)

[Ржавая_шпага]

53:00, разве не 1, 4 надо было запретить? Почему 5, 4 запретили?
И потом 1:00:30 должно быть не 2, а 3 при подсчете

[arsuHaha]

Подскажите, пожалуйста, почему при подсчёте дуги (1, 2) - 32:00 - мы не запретили заходить в вершину 1. Нужно же было ставить бесконечность в дуги, ведущие в 1. Например, (3, 1). Подскажите, пожалуйста

[margokd]

Подскажите, пожалуйста. Что значит, если решение методом ветвей и границ и решение методом Гомори не совпадает?