?

Log in

No account? Create an account
параметрический поиск - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

параметрический поиск [фев. 2, 2010|01:50 am]
Anatoly Vorobey
(эта запись будет интересна скорее всего лишь программистам и сочувствующим)

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

Параметрический поиск - метод, разработанный Нимродом Мегиддо в конце 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), как и обещано.
СсылкаОтветить

Comments:
[User Picture]From: r_atri
2010-02-02 12:15 am
>У этих прямых есть n(n+1)/2 = O(n2) точек пересечения

n(n-1)/2 ?
(Ответить) (Thread)
[User Picture]From: avva
2010-02-02 12:17 am
да, спасибо, сглючил. Сейчас исправлю.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2010-02-02 12:33 am
находятся в общей позиции - неправильно,
правильно "в общем положении".
(Ответить) (Thread)
[User Picture]From: avva
2010-02-02 12:36 am
спасибо. Я не знаю русскую терминологию, как обычно.
(Ответить) (Parent) (Thread)
[User Picture]From: wizzard0
2010-02-02 12:38 am
круто. надо с утра перечитать.
(Ответить) (Thread)
[User Picture]From: akopyan
2010-02-02 03:24 am
Здорово!
А зачем это надо на практике?
(Ответить) (Thread)
[User Picture]From: avva
2010-02-02 10:16 am
Думаю, чтобы статьи публиковать :)
Пока никто не придумал по-настоящему быстрый параллельный поиск, это остается красивым теоретическим результатом.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2010-02-02 04:07 am
Выч.геометры вечно радуют нас, программистов, предположением, что все объекты в общем положении. Как доходит до кода, так непонятно, что с этим делать. Первый импульс, конечно, наплевать и забыть, но тут приходят данные пользователя, представляющие собой диагонали правильного 10,000-угольника, и общий привет. Кстати, на них же выясняется, что плавающая точка все же не годится, точности не хватает, нужны длинные рациональные числа...
(Ответить) (Thread)
(Удалённый комментарий)
From: (Anonymous)
2010-02-02 09:00 pm
Именно так. В принципе есть методы борьбы с этим безобразием, но они добавляют к О-большому еще разнообразные веселые константы. Например, техника, называемая Simulation of Simplicity — кому интересно, погуглите, доставляет ;)
(Ответить) (Parent) (Thread)
[User Picture]From: vlasenko
2010-02-02 06:14 am
На рисунке точка пересечения прямых 3 и 4 - самая правая. Самая левая точка пересечения - 1 и 2.
(Ответить) (Thread)
[User Picture]From: avva
2010-02-02 08:49 am
Я написал этот пример вне связи с рисунком. Но хорошо, давайте подгоню под него, если это путает.
(Ответить) (Parent) (Thread)
[User Picture]From: ars_longa
2010-02-02 07:37 am

совершенно потрясена

На Земле действительно существовал человек по имени Нимрод Мегиддо? :о
(Ответить) (Thread)
[User Picture]From: avva
2010-02-02 08:50 am

Re: совершенно потрясена

http://theory.stanford.edu/~megiddo/
Я понимаю, что это звучит очень по-библейски :) но вполне нормальное имя-фамилия для Израиля.
(Ответить) (Parent) (Thread)
[User Picture]From: ars_longa
2010-02-02 08:53 am

Re: совершенно потрясена

Это даже не по-библейски звучит. Это звучит как имя персонажа голливудского блокбастера "Седьмая тайна Библии" или какого-нить подобного трэша. Даже, может быть, по Дэну Брауну.
(Ответить) (Parent) (Thread)
[User Picture]From: tacente
2010-02-02 11:50 am

Re: совершенно потрясена

Во-во. Я читать-то эту запись, к сожалению, не могу, но мне было достаточно этого имени, чтобы подорвать мозг.
(Ответить) (Parent) (Thread)
[User Picture]From: ars_longa
2010-02-02 08:37 pm

Re: совершенно потрясена

Аналогично. :)
(Ответить) (Parent) (Thread)
[User Picture]From: gianthare
2010-02-02 11:17 am

Re: совершенно потрясена

Ну, фамилию я бы нормальной не назвал - явно из придуманных. Я думаю, носителей мало и все одна семья
(Ответить) (Parent) (Thread)
[User Picture]From: ygam
2010-02-05 07:48 pm
Я через неделю буду работать в бригаде человека по фамилии Кохави - нужно набраться смелости и спросить, носил ли его дед фамилию Штерн.
(Ответить) (Parent) (Thread)
From: silly_sad
2010-02-02 10:43 am
меня всегда мучал вопрос каким путём люди до этого додумываются? если даже просто понимание всего фокуса до последнего абзаца не предвещает хорошего результата методу.
(Ответить) (Thread)
From: metaguest
2010-02-02 03:27 pm
А что Вы читали об этом алгоритме?
(Ответить) (Thread)
[User Picture]From: avva
2010-02-02 03:34 pm
Так, пару статей. А что?
(Ответить) (Parent) (Thread)
From: metaguest
2010-02-02 03:58 pm
Просто любопытно. Понравилось описание и захотелось прочитать что-нибудь еще на эту тему (когда-нибудь в будущем).
(Ответить) (Parent) (Thread)
From: ext_72902
2010-02-02 09:59 pm
Ого!
(Ответить) (Thread)
(Удалённый комментарий)
[User Picture]From: avva
2010-02-07 03:22 pm
Не пытался, если честно. Не настолько заинтересовало - а стоит?
(Ответить) (Parent) (Thread)