Глава 2 | Задача о походе конём

Описание: 0:00 Введение
1:13 Ориентированные, обратные и неориентированные походы коня
1:34 Обозначения для представления походов коня
1:57 Открытые, закрытые, магические походы коня
2:49 Количество ориентированных походов коня
3:47 Шахматные графы
4:43 Задача о n ферзях
5:29 Независимый набор узлов
6:34 Путь Гамильтона | Цикл Гамильтона
7:12 Определение алгоритма
7:52 Задача принятия решения | Алгоритм принятия решения, проверки
9:52 P | NP | NP-сложная | NP-полная
12:17 Полный перебор
14:16 Откат
16:03 Откат на графе | Пример 1
19:20 Откат на графе | Пример 2
20:34 Откат на графе коня | Пример 3
21:13 Алгоритм Варнсдорфа
22:37 Интуитивная идея, лежащая в основе алгоритма Варнсдорфа
23:47 Сила эвристики
25:43 Алгоритм Варнсдорфа на графе
27:55 Алгоритм Варнсдорфа для гамильтоновых путей?
29:11 Комбинирование подходов
31:21 Алгоритм Варнсдорфа | Поиск с возвратом | Перебор
31:43 Хроматическое число
34:56 Связь между теорией графов и линейной алгеброй
38:49 Реализация алгоритма Варнсдорфа на Python

Анимации созданы с помощью Manim и Adobe Premiere Pro.
Manim: https://docs.manim.community/en/stable/

Код Manim для визуализации алгоритма Варнсдорфа:
https://github.com/ccAcademycc/Warnsd...

Музыка:
▶ Винсент Рубинетти
Скачать музыку на Bandcamp:
https://vincerubinetti.bandcamp.com/a...
Слушать музыку на Spotify:
https://open.spotify.com/playlist/3zN...
▶ Вступление: Bellissimo — Дуг Максвелл

Звуковые эффекты: https://mixkit.co/free-sound-effects/

#теорияграфов #графы #математика #шахматы #шахматнаяголоволомка