Tag Archives: граница Парето

Граница Парето в 2D: STL-версия

Почти пять лет назад я описал алгоритм вычисления границы Парето множества точек на плоскости.

С тех пор я использовал данную задачу как задачу по программированию на первом курсе (на алгоритмы STL). Всё дело в том, что этот алгоритм очень просто записывается с помощью STL. Требуется применить два алгоритма (sort и unique) и адаптер компаратора (not_fn или самописный, например, переставляющий аргументы местами). Бывают простенькие задачи, к которым невозможно адекватно применить STL без написания своих компонент, а бывает и наоборот. Итак, код.

#include <algorithm>
#include <functional>

template 
  <
    class RanIt, 
    class Comp1, 
    class Comp2
  >
RanIt remove_dominated
  (
    RanIt from,
    RanIt to,
    Comp1 compare1,
    Comp2 compare2
  )
{
  std::sort(from, to, std::not_fn(compare1));
  return std::unique(from, to, std::not_fn(compare2));
}

////////////////////////////
#include <string>
#include <vector>
#include <iostream>
using namespace std;

bool test_remove_dominated()
{
  vector<string> input
  {
    "look",
    "after",
    "the",
    "raven",
    "star"
  };
  
  input.erase(
    remove_dominated(
      input.begin(), input.end(),
      std::less<>{},
      [](auto & a, auto & b)
      {
        return a.size() < b.size();
      }),
    input.end()
    );
    
  sort(input.begin(), input.end());
  return input == vector<string>
    {
      "raven",
      "star",
      "the"
    };
}

int main()
{
  cout << test_remove_dominated() << '\n';
  return 0;
}

В примере два критерия сравнения строк: лексикографический и по длине. Так «raven» доминирует «look» (и лексикографически, и по длине), но не «star».

Реклама

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

Продолжая тему поста «Граница Парето в 2D за O(NlogN) или O(N) время«, я решил реализовать и опубликовать аналог в трёхмерном пространстве (обобщение на три показателя качества). Соответствующий алгоритм также описан в книге Препараты и Шеймоса «Вычислительная геометрия: Введение» вслед за двумерным алгоритмом. Алгоритм основан на принципе заметания объёма плоскостью.

  1. Отсортировать точки по координате z.
  2. Проходя точки в порядке сортировки от максимального значения координаты z до минимального, добавлять их в статус заметающей плоскости.

Статус плоскости хранит упорядочение (например, по координате x) подмножества доминирующих точек и представляет собой сечение плоскостью z = const области пространства, доминируемой перебранными на данный момент точками («лесенку», см. рисунок ниже). При добавлении новой точки P в статус:

  1. Ищем в статусе точку R, ближайшую справа к P.
    • Если она лежит выше P, то отбрасываем P и выходим.
    • Если её нет, либо она лежит ниже P, то вставляем P в статус и переходим к п.2.
  2. Ищем в статусе точку L, ближайшую слева к P и находящуюся выше P.
  3. Удаляем из статуса все точки в интервале (L, P). Если L не найдена, то удаляются все точки слева от P.
  4. Сообщаем P как недоминируемый элемент.

граница Парето 3D статус

Статус может быть реализован в виде сбалансированного двоичного дерева (желательно, прошитого, возможно, уложенного в массив), тогда, как нетрудно видеть, алгоритм найдёт все недоминируемые точки за O(NlogN) время. Была написана реализация на C++, позволяющая реализовать статус в виде политики, передаваемой параметром шаблона, либо воспользоваться std::set или любым совместимым аналогом.

Граница Парето в 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)-время (например, с помощью блочной или поразрядной сортировок).