приближение

GRA Алгоритм Задача коммивояжёра Кратчайший объезд всех точек: ближайший сосед, 2-opt со списками соседей, Or-opt, оценка Хелда — Карпа. NP-трудна; точно O(2ⁿ · n²) 2 задачи DP Алгоритм Задача о рюкзаке Лучший набор вещей под ограничение по весу: таблица n × W и путь по ней назад. O(n·W) 3 задачи PAR Приём Жадные алгоритмы Лучший шаг сейчас без оглядки назад: когда это оптимально, когда почти, и как это доказать. обычно O(n log n): сортировка или куча 2 задачи GEO Алгоритм Упрощение линий Рамера — Дугласа — Пекера Упростить ломаную без потери формы: точка, дальше всех от хорды, остаётся, если она дальше допуска. O(n log n) в типичном случае, O(n²) в худшем 2 задачи NUM~ Алгоритм Бисекция и метод Ньютона Корень уравнения: деление отрезка пополам надёжно, касательные Ньютона — быстро. бисекция — log₂((b − a)/ε) шагов; Ньютон — около log₂ от числа знаков 2 задачи NUM~ Алгоритм Градиентный спуск Ищет минимум функции шагами против градиента — в сторону самого крутого спуска. O(κ · log(1/ε)) шагов 2 задачи NUM~ Алгоритм Численное интегрирование Площадь под кривой суммой: трапеции, Симпсон, узлы Гаусса, адаптивный шаг и оценка ошибки по Рунге. O(n) вычислений функции 2 задачи NUM~ Алгоритм Метод Монте-Карло Оценка числа случайным опытом: ошибка 1/√n в любой размерности, честный доверительный интервал. O(n) испытаний, ошибка ~ σ/√n 2 задачи NUM~ Алгоритм Методы Эйлера и Рунге — Кутты Шаг за шагом по закону движения: Эйлер, РК4, адаптивный шаг, Верле для орбит и неявные схемы. O(T/h) шагов, у РК4 четыре вычисления правой части на шаг 2 задачи SYS Алгоритм MinHash и LSH Подпись из K минимумов хешей: доля совпавших — оценка сходства Жаккара; полосы LSH сводят похожие пары в одни корзины. O(K·S) на подписи, O(n·b) на корзины, плюс проверка кандидатов 2 задачи SYS Алгоритм Планирование задач Порядок работы: короткие сначала, сроки, прерывания, много ядер и аномалии Грэма. O(n log n): сортировка или куча 2 задачи ML Алгоритм Метод главных компонент Находит направления наибольшего разброса данных и описывает каждую точку немногими числами вдоль них. O(n·d² + d³) 2 задачи RND Алгоритм Имитация отжига Локальный поиск, который принимает ухудшения с вероятностью e^(−Δ/T) и постепенно остывает. O(S · c) 2 задачи