Алгоритмы и структуры данных 9. Продолжение кратчайших путей. А*, Флойд, Форд-Беллман

Введение в программирование, алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики

Лекция прочитана 31 марта 2022 года
Лектор: Степанов Илья Даниилович
Оператор: Жильцов Игорь
Монтаж: Жильцов Игорь

0:00 - A*. Поиск кратчайшего пути от S до T
12:05 - Доказательство корректности. Эвристики
16:48 - Теорема. Асимптотика и корректность А*
20:50 - Интуитивное понимание теоремы
23:27 - Д-во пункта 1. Вспомогательное утверждение
27:37 - Д-во времени работы А* на монотонной эвристике
30:14 - Почему вернём правильный ответ?
36:00 - Сравнение с Дейкстрой
38:10 - Примеры "хороших" эвристик
47:30 - Алгоритм Флойда. Поиск попарных кратчайших расстояний в графе без отрицательных циклов
53:35 - Почему же недопустимы отрицательные циклы?
54:42 - Асимптотика
55:47 - Максимально простой код. Оптимизация по памяти
57:25 - Корректность
1:02:12 - Восстановление ответа (оптимального пути)
1:05:42 - Алгоритм Форда-Беллмана. Кратчайшие пути в графе с отрицательными циклами от S до всех
1:06:19 - dist равный -∞
1:12:24 - Сам алгоритм
1:15:30 - Асимптотика в отсутствии отрицательных циклов
1:18:27 - Обработка отрицательных циклов
1:19:15 - Д-во корректности обработки отрицательных цикло