Граница Парето в 2D за O(NlogN) или O(N) время

Постановка задачи

Предположим, что есть набор из N возможных решений {pi} некоторой задачи, и заданы показатели качества f1(p) → max и f2(p) → max, таким образом, каждому pi соответствует некоторая точка xi = (f1(pi), f2(pi)) на плоскости. Предположим, что заранее мы не можем решить, какой из показателей важнее, или как свести два показателя к одному общему, но мы можем заранее убрать из рассмотрения заведомо проигрышные решения pj, т.е. такие, для которых мы можем подобрать некоторое pk: f1(pj) ≤ f1(pk) и f2(pj) ≤ f2(pk). Тогда соответствующий набор оставшихся xk составит «границу Парето» исходного набора точек.

Очевидно, что мы можем сделать это за O(N2)-время, сравнив все значения показателей для решений попарно. Несколько лет назад мне понадобилось решать эту задачу в качестве подзадачи. Тогда я разработал для её решения алгоритм, работающий за O(NlogN)-время с помощью сортировки. Недавно мне пришлось вспомнить тот результат, кроме того, я решил обратиться к литературе по вычислительной геометрии и нашёл тот самый алгоритм в классической книге Препараты и Шеймоса «Вычислительная геометрия: Введение» (М.: Мир, 1989, с.194-195), где данная задача названа задачей «о поиске максимумов множества точек». Позволю себе высказать одно замечание. Для этого мне необходимо процитировать вводную часть из книги (с.192).

В действительности первоначально эта задача была описана как «задача о плавающих курсах валют»: каждый гражданин Эревона имеет некоторое количество («пакет») денег в иностранной валюте; курсы иностранных валют плавают в довольно широком диапазоне, поэтому каждый вечер человек, пакет валюты которого имеет наибольшую общую стоимость, провозглашается Королем Эревона. Каково наименьшее подмножество населения Эревона, с определенностью содержащее всех потенциальных королей?

Далее в книге приведена формальная постановка задачи. Что интересно, указанная неформальная постановка относится к совсем другой (хотя и похожей внешне) задаче — задаче о выпуклой оболочке. Это станет очевидным, если её формализовать корректно: пусть vi — это количество дензнаков i-й валюты, ci — курс i-й валюты в некоторых условных единицах (в конце концов, всегда можно взять некоторую валюту за единицу, у неё ci = 1), тогда стоимость пакета v есть скалярное произведение векторов (vi) и (ci). Это будет максимизируемый показатель качества (см. опорная функция). Ниже показана иллюстрация с тремя «пакетами», где все три пакета являются элементами границы Парето, но «средний» из них не будет решением задачи о потенциальных королях Эревона (показано три возможных вектора).

(иллюстрация)

Итак, пусть заданы бинарные предикаты Sl, l=1..n, каждый из которых удовлетворяет аксиомам нестрогого порядка. Частным случаем таких предикатов могут быть операции сравнения точек по значению фиксированной координаты на «меньше или равно».

Определение. Элемент p доминирует элемент q, если Sl(q, p) для всех l.

Задача. Найти все p из набора pi, i=1..N, такие, что для любого j из 1..N : pj ≠ p ⇒ pj не доминирует p (для простоты формулировки задачи положим, что набор pi не содержит дубликатов, представленный ниже алгоритм отбрасывает дубликаты).

Алгоритм

Решение указанной задачи для случая n=2 (в частности, для точек на плоскости) основывается на том наблюдении, что если некоторый p находится «левее» (S1) некоторого q, то из недоминирования q над p следует, что p должен находиться «выше» (S2) q. Аналогично, некоторый r, находящийся «левее» p, должен быть «выше» p. Пусть процедура report(p) сообщает p в качестве одного из элементов решения.

  1. Переномеруем (отсортируем) pi так, чтобы для любого i=1..(N-1) и любого j=(i+1)..N было верно S1(pi, pj).
  2. Положим max=pN; report(max).
  3. Для i=(N-1)..1: если S1(max, pi), то max=pi; report(max).

граница Парето алгоритм 2D

Данный довольно простой алгоритм демонстрирует один из базовых приёмов вычислительной геометрии — «заметание» (плоскости прямой) в его простейшей форме.

Обобщённая реализация данного алгоритма на C++ здесь.

Простой анализ алгоритма даёт O(NlogN)-время для произвольного предиката S1 (сортировка с предикатом) и O(N)-память для хранения результата сортировки для последующего заметания. В случае, если pi можно отобразить в точки xi=(f1(pi), f2(pi)) на плоскости, заданные с ограниченной точностью, и сравнивать покоординатно, то сортировку можно выполнить за O(N)-время (например, с помощью блочной или поразрядной сортировок).

Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: