Перейти к основному содержанию
EDU-MMCS
Вы используете гостевой доступ (
Вход
)
Алгоритмы на графах
В начало
Курсы
Осенний семестр
Прикладная математика и информатика
GraphAlgo(BI)
Модуль 3. NP-трудные задачи.
Лекция 13. Метод ветвей и границ и динамическое пр...
Лекция 13. Метод ветвей и границ и динамическое программирование для задачи коммивояжёра
Нажмите на ссылку
13 Метод ветвей и границ и динамическое программирование для ЗК.pdf
, чтобы просмотреть файл.
◄ Лекция 12. Изоморфизм. Задача коммивояжёра
Перейти на...
Перейти на...
Объявления
Общие сведения о курсе
Пример передачи параметров через командную строку
Экзаменационная программа
Лекция 1. Основные понятия. Представления графов
Задание 1. Представления графов
Лекция 2. Поиск в ширину.
Лекция 3. Поиск в глубину
Задание 2. Обнаружение цикла
Лекция 4. Поиск в глубину. Эйлеровы циклы.
Задание 3. Эйлеровы циклы.
Контрольная работа 1
Лекция 5. Минимальные остовные деревья
Лекция 6. Алгоритм Краскала
Лекция 7. Алгоритм Прима
Задание 4. Минимальное остовное дерево
Лекция 8. Кратчайшие пути (часть 1)
Задание 5. Алгоритм Дейкстры.
Лекция 9. Кратчайшие расстояния (часть 2)
Лекция 10. Кратчайшие пути (часть 3)
Контрольная работа 2
Лекция 11. NP-трудные задачи
Лекция 12. Изоморфизм. Задача коммивояжёра
Задание 6. Метод ветвей и границ для задачи коммивояжёра
Лекция 14. Эвристические алгоритмы
Задание 7. Жадные эвристики для задачи коммивояжёра.
Лекция 15. Приближённые алгоритмы. Алгоритм Кристофидеса.
Контрольная работа 3
Задание 6. Метод ветвей и границ для задачи коммивояжёра ►