25
правок
Изменения
м
Нет описания правки
К сожалению, эта верхняя оценка является достижимой. Например, если исходное множество <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> точка, что показано в [1]. Правда, если в этом примере точки обрабатываются в обратном порядке, то суммарное количество обработанных точек линейно зависит от <tex>n</tex> и <tex>d</tex>. Тем не менее, существуют примеры, для которых любой порядок обработки приводит к экспоненциальной зависимости числа порожденных точек от размерности пространства <tex>d</tex> и близок к <tex>n^d</tex> [1].
== Алгоритм Hypervolume by Slicing Objectives (HSO) ==
Под ''Objectives'' в названии данного алгоритма имеются в виду координаты пространства <tex>R^d</tex>.
Если алгоритм LebMeasure по очереди рассматривает все точки, то алгоритм HSO рассматривает по очереди все координаты, сводя задачу к меньшей на единицу размерности.
Изначально все точки сортируются по первой координате. Значения этой координаты используются для ''расслоения''(разрезания) всего множества на <tex>n</tex> частей, внутри каждой из которых при движении вдоль первой координаты форма ''разреза'' перпендикулярно оси первой координаты не меняется. Таким образом, для подсчета объема каждой части необходимо найти объем разреза и умножить длину части вдоль первой координаты. При этом получившийся разрез имеет на единицу меньшую размерность.
Заметим, что после сортировки и расслоения первая часть содержит все <tex>n</tex> точек, вторая - все, помимо точки с минимальной координатой, вдоль которой происходит расслоение и т.д., а последняя часть содержит только одну точку с максимальной этой координатой.
После этого все полученные части расслаиваются уже по второй координате, далее все полученные - по третьей и т.д. В итоге исходное множество разбивается на несколько непересекающихся гиперкубов и остается найти суммарный гиперобъем. Заметим, что расслаивание части можно прекратить в тот момент, когда в нее входит только одна точка и посчитать объем гиперкуба, образованного проекцией этой точки на оставшиеся координаты.
Описанный процесс можно реализовать как в виде рекурсивной процедуры, расслаивающей множество вдоль очередной координаты и вызывающей себя рекурсивно для каждой части и следующей координаты, так и нерекурсивно, если поддерживать множество всех текущих частей и на очередной итерации разбивать их все вдоль очередной координаты.
Время работы алгоритма напрямую зависит от суммарного количества частей, на которые будет разбито исходное множество.
