🎥 Видеолекции по теорверу и матстату от профессора, заведующего кафедрой математической статистики факультета ВМК МГУ Виктора Королёва. После внимательного просмотра видео вероятность успешной сдачи экзамена стремительно приближается к 1.
🌚 Ждём 50 реакций, чтобы опубликовать вторую часть лекций.
🌚 Ждём 50 реакций, чтобы опубликовать вторую часть лекций.
🌚21👍8🤡2🤩1
🛁 Эврика! Увы, сегодня мы не решили гробешник, но постарались уместить в несколько карточек самое важное об эвристических алгоритмах.
⏪ Псевдокод для удобства оставим здесь:
🥲 Но кое-что всё же не поместилось…
Накидай побольше реакций – и мы сделаем ещё пост на эту тему. В следующий раз расскажем о типах эвристических алгоритмов и в каких задачах олпроги их лучше применять.
FUNCTION A*(start,end)
closedset = the empty set // Множество вершин, которые уже были обработаны(раскрыты)
openset = {start} // Множество вершин(очередь), которые предстоит обработать(раскрыть).
// Изначально здесь присутствует только начальная вершина start.
fromset = the empty set // Карта пройденных вершин. Используется функцией RECONSTRUCT_PATH
для восстановления пути (вывода результата).
// Заполняем свойства вершины start
G(start) = COST(start,start) = 0 // Стоимость пути от начальной вершины. У start g(x) = 0.
F(start) = G(start) + H(start,end) // h(x) - эвристическая оценка расстояния до цели.
// Основной цикл алгоритма
WHILE openset IS NOT EMPTY
curr = MIN_F(openset) // Вершина из openset имеющая самую низкую оценку f(x).
IF (curr = end) RETURN RECONSTRUCT_PATH(fromset,start,end) // Выводим результат.
REMOVE curr FROM openset // Вершина curr пошла на обработку, а значит её следует удалить из очереди на обработку.
ADD curr TO closedset // И добавить в список уже обработанных.
FOREACH neighbour OF curr neighbours // Проверяем каждого соседа curr
IF neighbour IN closedset CONTINUE // Пропускаем соседей из закрытого списка (предварительный, ожидаемый)
tentative_g_score = G(curr) + COST(curr,neighbour) // Вычисляем g(x) для обрабатываемого соседа
IF neighbour NOT IN openset // Если сосед curr ещё не в открытом списке
ADD neighbour TO openset //добавим его туда
tentative_is_better = TRUE // вводим признак того, что нужно обновить свойства для соседней вершины
ELSE // Сосед был в открытом списке, а значит мы уже знаем его g(x), h(x) и f(x)
IF tentative_g_score < G(neighbour) // Вычисленная g(x) оказалась меньше, а значит нужно будет обновить значения g(x), h(x), f(x)
tentative_is_better = TRUE
ELSE // Вычисленная g(x) оказалась больше, чем имеющаяся в openset.
// Это означает, что из вершины curr путь через этого соседа дороже
// т.е. существует менее дорогой маршрут, пролегающий через этого соседа (из какой-то другой вершины, не из curr)
// Поэтому данного соседа мы игнорируем
tentative_is_better = FALSE
// Обновление свойств соседа.
IF tentative_is_better = TRUE
fromset(neighbour) = curr //Вершина с которой мы пришли. Используется для реконструкции пути.
G(neighbour) = tentative_g_score
F(neighbour) = G(neighbour) + H(neighbour, end)
// Обратите внимание, что если происходит обновление свойств - значит neighbour(сосед curr) так или иначе находится в openset.
// Т.е. при следующей итерации внешнего цикла из openset будет извлечена вершина с наименьшей оценкой f(x).
// Не исключено, что она окажется соседом нашего curr, которого мы только что добавили.
// В общем это самая важная особенность алгоритма А*.
RETURN FAILURE // управление передаётся сюда когда openset пуст,а вершина end не найдена (путь найти не удалось)
// Восстанавливаем результироующий путь.
// Путь можно проследить только от заданной вершины(чаще всего это end) к старту(каждая вершина имеет пути находится в fromset, чем мы и воспользуемся).
FUNCTION RECONSTRUCT_PATH(fromset,start,end)
pathset = the empty list // Упорядоченное множество результирующих вершин пути.
curr = end // Поиск начинается от финиша.
ADD curr TO pathset // Добавляем end в результирующий путь.
WHILE curr <> start // Добавляем в путь все вершины от end до start.
curr = fromset(curr) // Получаем вершину из которой пришли в curr.
ADD curr TO pathset // Добавить вершину в результирующий путь.
RETURN REVERSE(pathset) // Так как мы построили путь от end к start, то результирующий набор вершин необходимо перевернуть.Накидай побольше реакций – и мы сделаем ещё пост на эту тему. В следующий раз расскажем о типах эвристических алгоритмов и в каких задачах олпроги их лучше применять.
Please open Telegram to view this post
VIEW IN TELEGRAM
🔥7👍2❤1
Покажешь, насколько крут твой вуз? А если на кону 1 миллион рублей и другие заманчивые призы от Яндекса? 🦖
30 заботливо упакованных наборов умных устройств (возможно, среди подарков есть новая умная колонка Яндекс.Станция Дуо Макс?) уже ждут победителей.
200 лучших участников попадут в финал на грандиозный фестиваль YOUNG CON 2025 на Live Арена✔️
Баттл вузов уже стартовал. Стремительно врывайся! Первый этап проходит онлайн до 20 мая.
Ждём 11-классников, студентов и выпускников вузов — любого года выпуска.
💻 Регистрируйся, участвуй и побеждай!
30 заботливо упакованных наборов умных устройств (возможно, среди подарков есть новая умная колонка Яндекс.Станция Дуо Макс?) уже ждут победителей.
200 лучших участников попадут в финал на грандиозный фестиваль YOUNG CON 2025 на Live Арена
Баттл вузов уже стартовал. Стремительно врывайся! Первый этап проходит онлайн до 20 мая.
Ждём 11-классников, студентов и выпускников вузов — любого года выпуска.
Please open Telegram to view this post
VIEW IN TELEGRAM
👍6🔥2❤1
Время посоревноваться в решении задач по олпроге со школьниками со всей России. Такими же талантливыми, как и ты
Регистрируйся уже сейчас!
Ночная лига – это захватывающий турнир по олимпиадному программированию для школьников 9-11 классов, который проводит Высшая школа программной инженерии МФТИ совместно с партнером факультета – одной из ведущих IT компаний России.
Успей записаться и зови комрадов!
P.s На все вопросы охотно ответим здесь.
Please open Telegram to view this post
VIEW IN TELEGRAM
❤6👍1🔥1
Please open Telegram to view this post
VIEW IN TELEGRAM
Please open Telegram to view this post
VIEW IN TELEGRAM
👍8❤3🔥3