Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

параметрический поиск

(эта запись будет интересна скорее всего лишь программистам и сочувствующим)

Пару дней назад прочитал о параметрическом поиске - и весьма впечатлился; я бы даже сказал, впервые за много лет мне алгоритм взорвал мозг. Попробую рассказать об этом методе на примере конкретной задачи. Заранее предупреждаю, что в этой записи речь идет о красоте алгоритмов и их идей, а не практической пользе; описываемая идея теоретически эффективна, но из-за больших констант непрактична.

Параметрический поиск - метод, разработанный Нимродом Мегиддо в конце 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, это впечатляет. Метод состоит из трех частей: процедура сравнения, собственно сам параметрический поиск, и его параллелизация.

Процедура сравнения. Обозначим через x* x-координату искомой k-й слева точки пересечения. Нам достаточно найти число x*, потому что тогда найти точки всех прямых в ней, и проверить, отсортировав, какие две пересекаются, тривиально за O(n*logn). Процедура сравнения делает следующее: сравнивает любое данное x с x*, и отвечает, меньше, больше или равно (не зная при этом значения x*). Я покажу, как можно это сделать за O(n*logn).

Посмотрим на наши прямые где-нибудь левее всех точек пересечения, и пронумеруем их снизу вверх от 1 до n по порядку в этой области (т.е. просто согласно их наклонам). Теперь двигаемся слева направо, и замечаем, что каждое прохождение точки пересечения меняет порядок на одну транспозицию соседних прямых. Например, изначальный порядок 1 2 3 4, самая левая точка пересечения - прямых 1 и 2, тогда после нее порядок стал 2 1 3 4. Следующая точка будет точкой пересечения каких-то других двух прямых, соседних в этом порядке, и тоже поменяет их местами, и так далее.



У любой перестановки можно посчитать число инверсий, т.е. число пар, стоящих в обратном порядке: индексов i,j, так что i<j, но ai>aj. Легко видеть, что транспозиция соседних элементов меняет число инверсий ровно на единицу: либо +1, когда "портит" правильный порядок этих двух элементов, либо -1, когда восстанавливает, а на все остальные пары в любом случае не влияет. Но поскольку в нашем случае каждые две прямые пересекаются только один раз, и когда это происходит, меньшая из них по номеру стоит в перестановке перед большей, выходит, что каждая точка пересечения именно увеличивает число инверсий на 1.

Пусть нам дали какую-то точку x, про которую известно, что она - одна из точек пересечения. Мы легко можем найти y-координаты всех прямых в этой точке, и отсорировать их, за O(n*logn). Это даст нам некую перестановку прямых. Если мы теперь найдем число инверсий в этой перестановке, то сравнив его с k, мы узнаем, где лежит x относительно искомой точки x*: если оно меньше k, то слева, больше - справа, равно - x и есть x*.

Осталось объяснить, как найти число инверсий за O(n*logn), хотя само это число может быть порядка О(n2), так что слишком дорого делать одну операцию для каждой инверсии. Произведем merge sort перестановки, глядя на нее, как на список чисел. В процессе сортировки мы получим рекурсивно число инверсий внутри левой половины и правой половины, а во время фазы слияния посчитаем число инверсий между двумя половинами; сложив эти три числа вместе, получим ответ. Во время фазы слияния мы делаем следующее: все время смотрим, какое следующее число ставить в общий список: из отсортированной левой половины или отсортированной правой половины. В первом случае мы ничего нового не делаем, т.к. добавляемое левое число меньше всех правых, и инверсий нет. А вот каждый раз, когда мы выбираем следующее число справа, мы добавим к счетчику инверсий количество оставшихся чисел слева, потому что с каждым из них у выбранного числа есть инверсия. Таким образом во время фазы слияния мы за те же O(n) посчитали число инверсий между двумя половинами.

Вся процедура сравнения вместе занимает O(n*logn), и отвечает, для любой координаты x некой точки пересечения, на вопрос: меньше, равно или больше это число, чем x*.

Параметрический поиск. Теперь я перехожу к главной идее этого метода - той самой, которая взорвала мне мозг. Она на данном примере состоит в следующем. Давайте представим себе, что мы хотим отсортировать y-координаты всех n прямых в точке, лежащей сразу после k-того пересечения. Если k-тое пересечение имеет координату x*, возьмем какое-то x*+ε, посмотрим, в каком порядке идут наши прямые в этом месте, и отсортируем их в соответствии с этим порядком. Скажем, прямая 1 должна быть меньше прямой 5, если она в этом месте все еще ниже ее, и так далее. Правда, мы не знаем, чему равно x*, и не знаем, как найти y-координаты наших прямых в этом месте, но почему нас это должно остановить? Возьмем какой-нибудь алгоритм сортировки сравнениями, любой - тот же merge sort - дадим ему n объектов, обозначающих наши прямые, и скажем: сортируй! Он будет пытаться сортировать, и для этого ему эти прямые надо сравнивать; и каждый раз, когда он хочет сравнить две прямые, мы сделаем это за него следующим образом. Предположим, merge sort пришел к нам и говорит: мне надо знать, прямая i меньше прямой j или больше. Пусть i≤j. Найдем точку пересечения i и j, какое-то xij. Запустим на xij нашу процедуру сравнения из предыдущего пункта, и она скажет нам, находится он слева от x* или справа (если точно x*, то нам повезло и все закончено). Если слева, то прямые уже успели пересечься до x*, и значит прямая j больше прямой i; если справа, то меньше. Мы даем этот ответ алгоритму сортировки, и одновременно записываем в сторонке ограничение на x*, о котором мы узнали: x*, оказывается, больше (или меньше) конкретного числа xij.

Merge sort продолжает сортировать прямые и просить нас сравнить пары прямых, а мы это делаем с помощью процедуры сравнения, и как побочный эффект получаем все время все новые и новые ограничения на x* - собственно, мы храним интервал возможных значений x*, и все время его подправляем. В какой-то момент merge sort закончит сортировать и даст нам порядок прямых в точке x*+ε. И вот какая штука выходит: интервал возможных значений x* к этому моменту будет в точности интервалом между k-й и k+1-й точками пересечения - т.е. его левая граница немедленно даст нам x*. Почему это так? Потому что любая точка из интервала, который мы построили, "подходит" в качестве кандидата для перестановки, к-ю мы получили - в ней обязана быть именно такая перестановка прямых, потому что она дала бы именно такие ответы на все заданные вопросы-сравнения. Но мы видели раньше, что до k-й точки и после k+1-й перестановки обязательно будут другими, из-за все время растущего числа инверсий.

Вот этот трюк меня потряс: что мы делаем что-то с неизвестными нам вообще числами (сортируем по неизвестным нам y-координатам в неизвестной нам точке x*), да и конечный итог наших действий нас совершенно не интересует (эта перестановка нам не нужна вовсе). Но по мере работы мы одновременно ухитряемся сравнить любые два из этих неизвестных чисел, и заодно из этого получить побочные данные, которые в конце концов дают нам именно то, что мы хотим. Очень, очень красиво.

Но все еще, меж тем, неэффективно. Сортировка сравнениями требует O(n*logn) сравнений, и каждое такое сравнение у нас отнимает O(n*logn) - столько стоит запустить процедуру сравнения. Поэтому все вместе работает за O(n2log2n), и тогда непонятно, зачем было все это городить. Остается объяснить один последний фокус.

Параллелизация. Существуют параллельные алгоритмы, которые могут отсортировать n элементов, пользуясь n процессорами, за O(logn) параллельного времени, т.е. каждый процессор делает O(logn) шагов и О(logn) сравнений. Вот пример одного из таких алгоритмов для тех, кто хочет узнать подробности - я не буду в них вдаваться; я подчеркну, что практичным его назвать нельзя из-за огромных констант. Но тем не менее теоретически это возможно.

Мы сделаем следующую странную штуку. Вместо merge sort, в предыдущем пункте, будем пользоваться этим параллельным алгоритмом. Только вместо того, чтобы на самом деле запускать его параллельно, будем его симулировать в обычном последовательном исполнении: сначала выполним один за другим n первых шагов всех n процессоров. Потом n вторых шагов... и так log(n) раз (с точностью до константы, ясно). В итоге наша сортировка все равно займет O(n*logn) шагов, как и merge sort, поэтому неясно, как нам это помогает.

А вот как. Вместо того, чтобы отвечать на каждый вопрос-сравнение по отдельности, мы будем отвечать на них группами из n штук. Ведь в параллельном алгоритме n процессоров работают независимо, так что на каждом шагу они хотят задать нам O(n) вопросов-сравнений, не зависящих друг от друга (т.е. от ответа на первый вопрос не зависит, каким будет второй вопрос, и так далее). Мы возьмем эти n вопросов вместе - это n пар прямых, которые нас просят сравнить друг с другом, или, что то же, n точек пересечения, которые нас просят сравнить с x*. Найдем эти точки пересечения и отсортируем их по x-координатам, за O(n*logn). А теперь вместо того, чтобы сравнить каждую с x* отдельно, как мы делали раньше, найдем место x* среди них двоичным поиском. Это даст нам и новые ограничения на возможный интервал для x*, и ответы на все n вопросов. А сравнений при этом нам надо будет делать только O(logn), как в любом двоичном поиске, и каждое сравнение - вызов нашей процедуры. Поэтому всего мы потратим на это O(n*log2n) времени. Делать это надо будет O(logn) раз, по числу шагов в параллельном алгоритме. Так что конечный ответ - время, за которое мы находим x* - равен O(nlog3n), как и обещано.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 25 comments