Кирилл Хоружий "Введение в методы поиска короткого пути на больших графах" скачать в хорошем качестве

Кирилл Хоружий "Введение в методы поиска короткого пути на больших графах"

🚀 @SBERLOGASCI webinar on data science: 👨‍🔬 Кирилл Хоружий (https://t.me/diagrams_every_day) "Введение в методы поиска короткого пути на больших графах" ⌚️ Четверг 4 июня, 19.00 (по Москве) https://t.me/sberlogabig/451 https://t.me/diagrams_every_day На вебинаре мы рассмотрим методы решения задачи поиска пути в крупных перестановочных графах, таких как Кубик Рубика или Пятнашки, где задача поиска пути становится весьма сложной. Мы обсудим state-of-art подходы, показанные в работах DeepCubeA (2019) (Nature (https://www.nature.com/articles/s4225...) и Self-Supervision methods (2023) (arXiv (https://arxiv.org/abs/2106.03157)). Возможные варианты решения задачи о поиске пути: 1. Оценка дистанции случайными блужданиями. Из целевой вершины делаем K шагов и обучаем модель предсказывать K, которое хорошо коррелирует с реальной дистанцией (d). Используем эту модель как эвристику для алгоритма A*. 2. DQ-learning. Предсказывать моделью реальную дистанцию, в лучших традициях DQN основываясь на уравнение Беллмана (https://t.me/diagrams_every_day/391) улучшать после обучения предсказанные расстояния и обучаться заново. Затем также на А* искать путь. 3. Обратная диффузия. Делая случайные шаги, мы почти гарантировано отдаляемся от целевой вершины. Научимся по вершине, предсказывать откуда в неё мы пришли, случайно блуждая. Затем через beam search находим наиболее вероятный путь в целевую вершину (самый короткий ~ самый вероятный). Также обсудим возможные упрощения жизни для модели через алгоритм Метрополиса и существующие эвристики.