![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
параметрический поиск
Feb. 2nd, 2010 01:50 am(эта запись будет интересна скорее всего лишь программистам и сочувствующим)
Пару дней назад прочитал о параметрическом поиске - и весьма впечатлился; я бы даже сказал, впервые за много лет мне алгоритм взорвал мозг. Попробую рассказать об этом методе на примере конкретной задачи. Заранее предупреждаю, что в этой записи речь идет о красоте алгоритмов и их идей, а не практической пользе; описываемая идея теоретически эффективна, но из-за больших констант непрактична.
Параметрический поиск - метод, разработанный Нимродом Мегиддо в конце 70-х - начале 80-х. Особенно часто он подходит к проблемам в вычислительной геометрии.
Рассмотрим следующую задачу. Даны уравнения n прямых на плоскости, и для простоты предположим, что они находятся в общем положении: то есть, любые две из них пересекаются, и нет трех, пересекающихся в одной точке. У этих прямых есть n(n-1)/2 = O(n2) точек пересечения, которые можно отсортировать по их x-координатам слева направо - опять же для простоты положим, что все x-координаты разные. Проблема: найти k-ю слева точку пересечения, где 1≤k≤n(n-1)/2.
Наивное решение: отсортируем точки пересечения, и возьмем k-ю. Т.к. точек O(n2), это займет примерно O(n2logn) времени. Метод, который я опишу, решает задачу за O(n*log3n) времени. Учитывая то, что сам аргумент k двигается в пределах от 1 до n(n-1)/2, это впечатляет. Метод состоит из трех частей: процедура сравнения, собственно сам параметрический поиск, и его параллелизация.
( Read more... )
Пару дней назад прочитал о параметрическом поиске - и весьма впечатлился; я бы даже сказал, впервые за много лет мне алгоритм взорвал мозг. Попробую рассказать об этом методе на примере конкретной задачи. Заранее предупреждаю, что в этой записи речь идет о красоте алгоритмов и их идей, а не практической пользе; описываемая идея теоретически эффективна, но из-за больших констант непрактична.
Параметрический поиск - метод, разработанный Нимродом Мегиддо в конце 70-х - начале 80-х. Особенно часто он подходит к проблемам в вычислительной геометрии.
Рассмотрим следующую задачу. Даны уравнения n прямых на плоскости, и для простоты предположим, что они находятся в общем положении: то есть, любые две из них пересекаются, и нет трех, пересекающихся в одной точке. У этих прямых есть n(n-1)/2 = O(n2) точек пересечения, которые можно отсортировать по их x-координатам слева направо - опять же для простоты положим, что все x-координаты разные. Проблема: найти k-ю слева точку пересечения, где 1≤k≤n(n-1)/2.
Наивное решение: отсортируем точки пересечения, и возьмем k-ю. Т.к. точек O(n2), это займет примерно O(n2logn) времени. Метод, который я опишу, решает задачу за O(n*log3n) времени. Учитывая то, что сам аргумент k двигается в пределах от 1 до n(n-1)/2, это впечатляет. Метод состоит из трех частей: процедура сравнения, собственно сам параметрический поиск, и его параллелизация.
( Read more... )
