оптимизация

Статьи

SRT Приём Двоичный поиск по ответу Если проверить ответ легче, чем найти, и проверка монотонна, — ищем ответ делением пополам. O(log D · стоимость проверки) 2 задачи SRT Алгоритм Троичный поиск Вершина унимодальной функции: сравнить две точки и отбросить часть отрезка. И почему золотое сечение лучше. O(log(L/ε)) вычислений функции 2 задачи GRA Алгоритм Минимальный разрез Самая дешёвая граница в графе: вырезает предмет на фотографии и находит слабое место сети. O(m n² |C|) 2 задачи GRA Алгоритм Венгерский алгоритм Кому какую работу при наименьшей общей цене: потенциалы, честные пары и увеличивающие пути за O(n³). O(n³) 2 задачи GRA Алгоритм Поток наименьшей стоимости Поток с наименьшей суммарной ценой: круги отрицательной стоимости, кратчайшие пути с потенциалами, транспортная задача 1930 года. O(F · E log V) 2 задачи GRA Алгоритм Задача коммивояжёра Кратчайший объезд всех точек: ближайший сосед, 2-opt со списками соседей, Or-opt, оценка Хелда — Карпа. NP-трудна; точно O(2ⁿ · n²) 2 задачи DP Приём Динамическое программирование Сводим задачу к подзадачам, решаем каждую один раз и храним ответы в таблице. состояния × переходы 2 задачи DP Алгоритм Задача о рюкзаке Лучший набор вещей под ограничение по весу: таблица n × W и путь по ней назад. O(n·W) 3 задачи DP Приём Динамика на отрезках Состояние — отрезок [i, j], переход — где его разрезать: дерево поиска, порядок умножения матриц, распил. O(n³) 2 задачи DP Приём Динамика на деревьях Ответ поддерева — из ответов детей: проход от листьев к корню, а для всех корней сразу — перерасчёт с корня. O(n) 2 задачи DP Приём Динамика по маскам Состояние — подмножество, записанное битами числа: точный коммивояжёр, назначения, раскладки по профилю. O(2ⁿ · n²) для коммивояжёра 2 задачи DP Приём Convex hull trick Минимум прямых вместо перебора: 1776 тестов каталога по запускам песочницы — и квадратичная динамика становится линейной. O(n) 2 задачи DP Приём Оптимизации Кнута и «разделяй и властвуй» 45 тысяч городов на карте по классам населения: 3,5 млн вычислений вместо пяти миллиардов — потому что лучший разрез монотонен. O(k · n log n) 2 задачи PAR Приём Жадные алгоритмы Лучший шаг сейчас без оглядки назад: когда это оптимально, когда почти, и как это доказать. обычно O(n log n): сортировка или куча 2 задачи PAR Приём Ветви и границы 38 аэропортов, где из каждого прямой рейс в каждый: оценка раскраской сжимает перебор с миллиона узлов до 242. экспоненциальное в худшем случае 1 задача PAR Приём Встреча посередине Перебрать две половины по отдельности и встретиться в отсортированной таблице: 2·2^(n/2) шагов вместо 2ⁿ. O(2^(n/2) · n) 2 задачи GEO Приём Вращающиеся калиперы У 971 из 2679 кварталов центра Алматы наименьший прямоугольник повёрнут на 4–8°: сетка улиц смотрит не строго на север. O(n) после оболочки, O(n log n) с ней 2 задачи NUM~ Алгоритм Градиентный спуск Ищет минимум функции шагами против градиента — в сторону самого крутого спуска. O(κ · log(1/ε)) шагов 2 задачи NUM~ Алгоритм Симплекс-метод 24 числа вместо 88 клавиш — и симплекс-метод восстанавливает каждый аккорд прелюдии Шопена точно. Наименьшие квадраты — ни одного.

шаг — O(m·n); число шагов на практике порядка m, в худшем случае экспоненциальное

1 задача ML Алгоритм Логистическая регрессия Оценивает вероятность ответа «да»: взвешенная сумма признаков, пропущенная через сигмоиду. O(n·d² + d³) на шаг Ньютона 3 задачи RND Алгоритм Имитация отжига Локальный поиск, который принимает ухудшения с вероятностью e^(−Δ/T) и постепенно остывает. O(S · c) 2 задачи RND Алгоритм Генетический алгоритм Популяция решений, отбор, скрещивание и мутация: эволюция траектории на настоящем автодроме. O(G · N · c) 2 задачи TEC Приём Отсечения Не открывать ветки, где заведомо нет ответа лучше: рекорд, порядок, симметрия, оценки снизу. O(kⁿ) в худшем случае 2 задачи

Задачи

Журнал обменов Заказы для курьера Охрана выставки Распил бревна Самый дальний бросок Самый длинный безопасный шаг Склад на сетке улиц Весь отрыв в кадре Две лиги поровну Две монеты Диски для аудиокниги Кому какой заказ Курьеры и заказы Память для фильтров План облёта Погасить все лампочки Проекты для района Пронести в проём Пункт выдачи Размер блока Скобки на калькуляторе Сплав из лома Туда на восток, обратно на запад Чтецы аудиокниги Что прочитать Вечера чтения Грузовой лифт Никто не едет далеко Пачки тестов Рулон кабеля Самый дешёвый тариф Слить соседние

Часто рядом

классика 19 олимпиады 13 собеседования 7 динамика 7 итерации 6 карты и навигация 6 приближение 5 граф 4 логистика 4 эвристика 4 геоданные 4 двоичный поиск 3