25
правок
Изменения
Нет описания правки
Самый простой алгоритм нахождения гиперобъема базируется на идее комбинаторной [[формула включения-исключения|формулы включения-искючения]].
Все множество <tex>X</tex> представляется в виде объединения <tex>n</tex> гиперкубов гиперпараллелепипедов (<tex>X^i</tex>), соответствующих отдельным точкам <tex>x^i</tex>.
После этого объем всего множества вычисляется по формуле: <center> <tex> S(X) = \sum \limits_{I \in 2^n} (-1)^{|I|+1} S(\bigcap \limits_{ j \in I} X^j) </tex> </center>
Объем пересечения гиперкубов гиперпараллелепипедов легко считается как произведение по каждой координате минимального значения этой координаты среди всех точек, которым соответствуют гиперкубыгиперпараллелепипеды.
Таким образом, в этом алгоритме перебираются все подмножества точек множества <tex>X</tex>, для каждого множества находится гиперобъем пересечения соответствующих гиперкубовгиперпараллелепипедов, и он прибавляется с соответствующим знаком к ответу.
Время работы этого алгоритма составляет <tex>O(n 2^n)</tex>.
== Алгоритм LebMeasure ==
Алгоритм LebMeasure<ref>Bringmann K., Friedrich. T.: An Efficient Algorithm for Computing Hypervolume Contributions. Evolutionary Computation, Vol. 18, No. 3, MIT Press, pp 383-402. (2010)</ref> обрабатывает точки множества <tex>X</tex> по очереди. Для каждой очередной точки <tex>x</tex> находится объем некоторого максимального по включению гиперкубагиперпараллелепипеда, доминируемого эксклюзивно только этой точкой <tex>x</tex> и она заменяется на некоторое множество ''порожденных'' точек, которые доминируют оставшуюся область, доминировавшуюся до этого точкой <tex>x</tex>.
Например, если изначально было четыре точки в трехмерном пространстве <tex>(6, 7, 4), (9, 5, 5), (1, 9, 3), (4, 1, 9)</tex>, то точка <tex>(6, 7, 4)</tex> эксклюзивно доминирует куб параллелепипед с одним концов в <tex>(6, 7, 4)</tex>, а другим - в <tex>(4, 5, 3)</tex>. После добавления объема этого куба параллелепипеда к ответу, точка <tex>(6, 7, 4)</tex> порождает три точки: <tex>(4, 7, 4), (6, 5, 3), (6, 7, 3)</tex>. При этом точка <tex>(6, 5, 4)</tex> доминируется точкой <tex>(9, 5, 5)</tex> и сразу удаляется из множества <tex>X</tex>.
Обработка точек продолжается, пока все точки не будут обработаны. Таким образом, время работы алгоритма напрямую зависит от количества порожденных точек. Легко заметить, что таких точек не более, чем <tex>n^d</tex>, поскольку каждая координата каждой порожденной точки равна соответствующей координате некоторой точки исходного множества <tex>X</tex>.
К сожалению, эта верхняя оценка является достижимой. Например, если исходное множество <tex>X</tex> имеет вид: <tex>(1, n, n, ..., n), (2, n - 1, n - 1, ..., n - 1), ..., (n, 1, 1, ..., 1)</tex>, и точки обрабатываются именно в этом порядке, то всего будет обработано <tex>n^{d-1}</tex> точка, что показано в <ref name = "while"/>. Правда, если в этом примере точки обрабатываются в обратном порядке, то суммарное количество обработанных точек линейно зависит от <tex>n</tex> и <tex>d</tex>. Тем не менее, существуют примеры, для которых любой порядок обработки приводит к экспоненциальной зависимости числа порожденных точек от размерности пространства <tex>d</tex> и эта зависимость близка к <tex>n^d</tex> <ref name="while">
While, L., Hingston, P., Barone, L., Huband, S.: A Faster Algorithm for Calculating Hypervolume. IEEE Transaction on Evolutionary Computation, Vol.10, No. 1, pp 29–38 . (2006)</ref>.
== Алгоритм Hypervolume by Slicing Objectives (HSO) ==
Заметим, что после сортировки и расслоения первая часть содержит все исходные <tex>n</tex> точек множества <tex>X</tex>, вторая - все, помимо точки с минимальной первой координатой, вдоль которой происходит расслоение, и т.д., а последняя часть содержит только одну точку с максимальной этой координатой.
После этого все полученные части расслаиваются уже по второй координате, далее все полученные - по третьей и т.д. В итоге исходное множество разбивается на несколько непересекающихся гиперкубов гиперпараллелепипедов и остается их найти суммарный гиперобъем. Заметим, что расслаивание части можно прекратить в тот момент, когда в нее входит только одна точка и посчитать объем гиперкубагиперпараллелепипеда, образованного проекцией этой точки на оставшиеся координаты.
Описанный процесс можно реализовать как в виде рекурсивной процедуры, расслаивающей множество вдоль очередной координаты и вызывающей себя рекурсивно для каждой части и следующей координаты, так и нерекурсивно, если поддерживать множество всех текущих частей и на очередной итерации разбивать их все вдоль очередной координаты.
== Сведение к задаче KMP (Klee's Measure Problem) ==
Задача KMP состоит в нахождении объема объединения прямоугольных гиперпараллелепипедов в <tex>d</tex>-мерном пространстве. Как показано в описании алгоритма IEA, исходная задача легко сводится к этой, если каждой точке поставить в соответствие гиперкуб гиперпараллелепипед с одной вершиной в центре координат, а противоположной - в этой точке.
Существует несколько алгоритмов решения задачи KMP<ref name = "overmars">Overmars M.H., Yap C.K.: New upper bounds in Klee’s measure problem. SIAM Journal on Computing 20(6), pp 1034–1045. (1991)</ref><ref>Beume N.: S-Metric calculation by considering dominated hypervolume as Klee’s measure problem. Evolutionary Computation, 17(4), pp 477–492. (2009)</ref><ref>Beume N., Rudolph G.: Faster S-metric calculation by considering dominated hypervolume as Klee’s measure problem. In Proc. Second International Conference on Computational Intelligence (IASTED ’06), pp 233–238. (2006)</ref>, самый оптимальный из которых использует идеи сканирующей гиперплоскости, [[Статистики на отрезках. Корневая эвристика|корневой эвристики]] и КД-дерево, и позволяет решать задачу за время <tex>O(n^{d/2}\log n)</tex>. Рассмотрим его.
Для начала изложим идею сканирующей гиперплоскости. Рассмотрим всевозможные значения <tex>d</tex>-ой координаты у точек множества <tex>X</tex>.
Возьмем гиперплоскость, перпендикулярную оси <tex>d</tex>-ой координаты, будем ее двигать по этим значениям от минимального до максимального и рассматривать проекцию всех гиперкубов гиперпараллелепипедов на эту гиперплоскость. Заметим, что между точками проекция меняться не будет, а в каждой точке будут появляться или исчезать проекции некоторых гиперкубовгиперпараллелепипедов. Поэтому, если уметь эффективно пересчитывать объем проекции при каждом появлении/исчезновении и прибавлять это значение, умноженное на расстояние между последовательными значениями <tex>d</tex>-ой координаты, то можно легко посчитать суммарный гиперобъем. Как раз для эффективного пересчета используется такая структура, как КД-дерево.
Теперь изложим идею алгоритма на примере трехмерного пространства.
