Алгоритмы точного вычисления гиперобъема - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:43:49Z

rollbackEdits.php mass rollback

185.220.100.241 в 03:18, 1 сентября 2022

2022-09-01T03:18:53Z

Joshik в 12:23, 20 июня 2012

2012-06-20T12:23:00Z

Joshik в 12:07, 20 июня 2012

2012-06-20T12:07:05Z

Joshik в 12:01, 20 июня 2012

2012-06-20T12:01:57Z

Joshik в 11:58, 20 июня 2012

2012-06-20T11:58:40Z

194.85.160.133 в 11:53, 20 июня 2012

2012-06-20T11:53:36Z

Joshik в 11:48, 20 июня 2012

2012-06-20T11:48:56Z

178.67.53.106: /* Алгоритм Hypervolume by Slicing Objectives (HSO) */

2012-06-18T21:11:27Z

‎Алгоритм Hypervolume by Slicing Objectives (HSO)

Joshik: орфографические ошибки

2012-06-18T06:43:17Z

орфографические ошибки

Внесённые изменения

← Предыдущая		Версия 16:43, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	{{В разработке}}		{{В разработке}}

← Предыдущая		Версия 03:18, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	{{В разработке}}		{{В разработке}}

@@ Строка 17: / Строка 17: @@
 Самый простой алгоритм нахождения гиперобъема базируется на идее комбинаторной [[формула включения-исключения|формулы включения-искючения]].
-Все множество <tex>X</tex> представляется в виде объединения <tex>n</tex> гиперкубов (<tex>X^i</tex>), соответствующих отдельным точкам <tex>x^i</tex>.
+Все множество <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>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>.
+Алгоритм 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>(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>.
+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) ==
@@ Строка 46: / Строка 46: @@
 Заметим, что после сортировки и расслоения первая часть содержит все исходные <tex>n</tex> точек множества <tex>X</tex>, вторая - все, помимо точки с минимальной первой координатой, вдоль которой происходит расслоение, и т.д., а последняя часть содержит только одну точку с максимальной этой координатой.
-После этого все полученные части расслаиваются уже по второй координате, далее все полученные - по третьей и т.д. В итоге исходное множество разбивается на несколько непересекающихся гиперкубов и остается их найти суммарный гиперобъем. Заметим, что расслаивание части можно прекратить в тот момент, когда в нее входит только одна точка и посчитать объем гиперкуба, образованного проекцией этой точки на оставшиеся координаты.
+После этого все полученные части расслаиваются уже по второй координате, далее все полученные - по третьей и т.д. В итоге исходное множество разбивается на несколько непересекающихся гиперпараллелепипедов и остается их найти суммарный гиперобъем. Заметим, что расслаивание части можно прекратить в тот момент, когда в нее входит только одна точка и посчитать объем гиперпараллелепипеда, образованного проекцией этой точки на оставшиеся координаты.
 Описанный процесс можно реализовать как в виде рекурсивной процедуры, расслаивающей множество вдоль очередной координаты и вызывающей себя рекурсивно для каждой части и следующей координаты, так и нерекурсивно, если поддерживать множество всех текущих частей и на очередной итерации разбивать их все вдоль очередной координаты.
@@ Строка 84: / Строка 84: @@
 == Сведение к задаче KMP (Klee's Measure Problem) ==
-Задача KMP состоит в нахождении объема объединения прямоугольных гиперпараллелепипедов в <tex>d</tex>-мерном пространстве. Как показано в описании алгоритма IEA, исходная задача легко сводится к этой, если каждой точке поставить в соответствие гиперкуб с одной вершиной в центре координат, а противоположной - в этой точке.
+Задача 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>-ой координаты, то можно легко посчитать суммарный гиперобъем. Как раз для эффективного пересчета используется такая структура, как КД-дерево.
+Возьмем гиперплоскость, перпендикулярную оси <tex>d</tex>-ой координаты, будем ее двигать по этим значениям от минимального до максимального и рассматривать проекцию всех гиперпараллелепипедов на эту гиперплоскость. Заметим, что между точками проекция меняться не будет, а в каждой точке будут появляться или исчезать проекции некоторых гиперпараллелепипедов. Поэтому, если уметь эффективно пересчитывать объем проекции при каждом появлении/исчезновении и прибавлять это значение, умноженное на расстояние между последовательными значениями <tex>d</tex>-ой координаты, то можно легко посчитать суммарный гиперобъем. Как раз для эффективного пересчета используется такая структура, как КД-дерево.
 Теперь изложим идею алгоритма на примере трехмерного пространства.

@@ Строка 28: / Строка 28: @@
 == Алгоритм LebMeasure ==
-Алгоритм LebMeasure<ref>Bringmann K., Friedrich. T.: An Efficient Algorithm for Computing Hypervolume Contributions. Evolutionary Computation, Vol. 18, No. 3, pp 383-402, MIT Press. (2010)</ref> обрабатывает точки множества <tex>X</tex> по очереди. Для каждой очередной точки <tex>x</tex> находится объем некоторого максимального по включению гиперкуба, доминируемого эксклюзивно только этой точкой <tex>x</tex> и она заменяется на некоторое множество ''порожденных'' точек, которые доминируют оставшуюся область, доминировавшуюся до этого точкой <tex>x</tex>.
+Алгоритм 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>.
@@ Строка 41: / Строка 41: @@
 Под ''Objectives'' в названии данного алгоритма имеются в виду координаты пространства <tex>\mathbb{R}^d</tex>.
-Если алгоритм LebMeasure по очереди рассматривает все точки, то алгоритм HSO<ref>Zhou X., Sun C., Mao N., Li W.: Generalization of HSO algortihms for computing hypervolume for mutiobjective optimization problems, IEEE Congress on Evolutionary Computation (2007)</ref> рассматривает по очереди все координаты, сводя задачу к меньшей на единицу размерности.
+Если алгоритм LebMeasure по очереди рассматривает все точки, то алгоритм HSO<ref>Zhou X., Sun C., Mao N., Li W.: Generalization of HSO algortihms for computing hypervolume for mutiobjective optimization problems, IEEE Congress on Evolutionary Computation. (2007)</ref> рассматривает по очереди все координаты, сводя задачу к меньшей на единицу размерности.
 Изначально все точки сортируются по первой координате. Значения этой координаты используются для ''расслоения'' (разрезания) всего множества на <tex>n</tex> частей, внутри каждой из которых при движении вдоль первой координаты форма ''разреза'' (гиперплоскости), проходящего перпендикулярно оси первой координаты, не меняется. Таким образом, для подсчета объема каждой части необходимо найти объем разреза, и умножить на длину части вдоль первой координаты. При этом получившийся разрез имеет на единицу меньшую размерность.
@@ Строка 86: / Строка 86: @@
 Задача 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)
+Существует несколько алгоритмов решения задачи 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>.

@@ Строка 28: / Строка 28: @@
 == Алгоритм LebMeasure ==
-Алгоритм LebMeasure<ref>K. Bringmann, T. Friedrich.: An Efficient Algorithm for Computing Hypervolume Contributions. Evolutionary Computation, Vol. 18, No. 3, pp 383-402, MIT Press. (2010)</ref> обрабатывает точки множества <tex>X</tex> по очереди. Для каждой очередной точки <tex>x</tex> находится объем некоторого максимального по включению гиперкуба, доминируемого эксклюзивно только этой точкой <tex>x</tex> и она заменяется на некоторое множество ''порожденных'' точек, которые доминируют оставшуюся область, доминировавшуюся до этого точкой <tex>x</tex>.
+Алгоритм LebMeasure<ref>Bringmann K., Friedrich. T.: An Efficient Algorithm for Computing Hypervolume Contributions. Evolutionary Computation, Vol. 18, No. 3, pp 383-402, MIT Press. (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>.
@@ Строка 86: / Строка 86: @@
 Задача 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>N. Beume.: S-Metric calculation by considering dominated hypervolume as Klee’s measure problem. Evolutionary Computation, 17(4), pp 477–492. (2009)</ref><ref>N. Beume, G. Rudolph.: 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)
+Существует несколько алгоритмов решения задачи 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>. Рассмотрим его.

@@ Строка 12: / Строка 12: @@
 В частности, если <tex>X = \{x\}</tex>, то <tex>S(X) = \prod \limits_{i=1}^{d} x_i</tex>.
-Задача: найти точное значение гиперобъема <tex>S(X)</tex> множества из <tex>n</tex> точек <tex>d</tex>-мерного пространоства.
+Задача: найти точное значение гиперобъема <tex>S(X)</tex> множества из <tex>n</tex> точек <tex>d</tex>-мерного пространства.
 == Алгоритм включения-исключения (Inclusion-Exclusion Algorithm, IEA) ==
@@ Строка 28: / Строка 28: @@
 == Алгоритм LebMeasure ==
-Алгоритм LebMeasure<ref>K. Bringmann, T. Friedrich.: An Efficient Algorithm for Computing Hypervolume Contributions. Evolutionary Computation, Vol. 18, No. 3, pp 383-402, MIT Press. (2010)</ref> обрабатывает точки множества <tex>X</tex> по очереди. Для каждой очередной точки <tex>x</tex> находится объем некоторого максимального по включению гиперкуба, доминируемого эксклюзивно только этой точкой <tex>x</tex> и она заменяется на некоторое множество ''порожденных'' точек, которые доминируют оставшуюся область, доминировшуюся до этого точкой <tex>x</tex>.
+Алгоритм LebMeasure<ref>K. Bringmann, T. Friedrich.: An Efficient Algorithm for Computing Hypervolume Contributions. Evolutionary Computation, Vol. 18, No. 3, pp 383-402, MIT Press. (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>.
@@ Строка 93: / Строка 93: @@
 Теперь изложим идею алгоритма на примере трехмерного пространства.
-В трехмерном пространстве сканирующая гиперплоскость превращается в обычную плоскость. Будем считать, что она всегда располагается перепендикулярно оси <tex>OZ</tex> и двигается от минимальных значений по этой оси до максимальных. В каждый момент проекция всех параллелепипедов на эту плоскость представляет собой множество прямоугольников и необходимо уметь обрабатывать следующие три запроса:
+В трехмерном пространстве сканирующая гиперплоскость превращается в обычную плоскость. Будем считать, что она всегда располагается перпендикулярно оси <tex>OZ</tex> и двигается от минимальных значений по этой оси до максимальных. В каждый момент проекция всех параллелепипедов на эту плоскость представляет собой множество прямоугольников и необходимо уметь обрабатывать следующие три запроса:
 # добавить прямоугольник
 # удалить прямоугольник
@@ Строка 135: / Строка 135: @@
 Рассмотрим теперь как именно будет устроено разделение пространства на области КД-деревом для эффективного его использования.
-Возьмем проекции всех параллелепипедов на плоскость, перепендикулярную оси <tex>OZ</tex> - множество прямоугольников <tex>V</tex>. Рассмотрим все <tex>x</tex>-координаты границ прямоугольников и разобьем ось <tex>OX</tex> на <tex>2\sqrt{n}</tex> промежутков так, чтобы в каждом из них было не более <tex>\sqrt{n}</tex> границ. Получившиеся <tex>2\sqrt{n}</tex> полос разобьем горизонтальными линиями на итоговые области по отдельности следующим образом. Для каждой полосы у всех прямоугольников, имеющих вертикальную границу в этой полосе, возьмем все горизонтальные границы (их будет не более <tex>2\sqrt{n}</tex>), а среди всех горизонтальных границ, пересекающих область, возьмем каждую <tex>\sqrt{n}</tex>-ую. Таким образом, в итоге получим не более <tex>4\sqrt{n}</tex> областей в каждой верикальной полосе.
+Возьмем проекции всех параллелепипедов на плоскость, перпендикулярную оси <tex>OZ</tex> - множество прямоугольников <tex>V</tex>. Рассмотрим все <tex>x</tex>-координаты границ прямоугольников и разобьем ось <tex>OX</tex> на <tex>2\sqrt{n}</tex> промежутков так, чтобы в каждом из них было не более <tex>\sqrt{n}</tex> границ. Получившиеся <tex>2\sqrt{n}</tex> полос разобьем горизонтальными линиями на итоговые области по отдельности следующим образом. Для каждой полосы у всех прямоугольников, имеющих вертикальную границу в этой полосе, возьмем все горизонтальные границы (их будет не более <tex>2\sqrt{n}</tex>), а среди всех горизонтальных границ, пересекающих область, возьмем каждую <tex>\sqrt{n}</tex>-ую. Таким образом, в итоге получим не более <tex>4\sqrt{n}</tex> областей в каждой вертикальной полосе.
 Полученные области обладают следующими свойствами:
@@ Строка 156: / Строка 156: @@
 Все эти свойства следуют из свойств разбиения на области и логарифмической высоты дерева.
-Наконец, получаем итоговый алгоритм. Идем сканирующей плоскостью, перепендикулярной оси <tex>OZ</tex>, добавляя или удаляя прямоугольники из КД-дерева. При этом каждый раз пересчитываем площадь объединения всех текущих прямоугольников и, складывая эти величины, умноженные на соответствующую разницу <tex>z</tex>-координат, получаем общий объем.
+Наконец, получаем итоговый алгоритм. Идем сканирующей плоскостью, перпендикулярной оси <tex>OZ</tex>, добавляя или удаляя прямоугольники из КД-дерева. При этом каждый раз пересчитываем площадь объединения всех текущих прямоугольников и, складывая эти величины, умноженные на соответствующую разницу <tex>z</tex>-координат, получаем общий объем.
 Каждая операция добавления или удаления прямоугольников требует изменения <tex>O(\sqrt{n} \log n)</tex> полей <tex>Cover</tex>, а также операций добавления или удаления прямоугольника в <tex>O(\sqrt{n})</tex> листьев, каждая из которых требует <tex>O(\log n)</tex> времени. Итого, на одну операцию добавления или удаления требуется <tex>O(\sqrt{n} \log n)</tex> времени, суммарно таких операций <tex>O(n)</tex>, и получается, что весь алгоритм работает за <tex>O(n \sqrt{n} \log n)</tex>. При этом на хранение всей информации требуется <tex>O(n\sqrt{n}) </tex> памяти - каждый лист может хранить <tex>O(\sqrt{n})</tex> прямоугольников.

@@ Строка 2: / Строка 2: @@
 == Постановка задачи ==
-<tex>x = (x_1, x_2, ..., x_d; x_i \ge 0) \in R^d</tex> - точка в <tex>d</tex>-мерном пространстве.
+<tex>x = (x_1, x_2, ..., x_d; x_i \ge 0) \in \mathbb{R}^d</tex> - точка в <tex>d</tex>-мерном пространстве.
 Точка <tex>x</tex> доминирует точку <tex>y</tex> (<tex>x \succ y</tex>), если <tex>\forall i : x_i \ge y_i, \exists j : x_j > y_j</tex>.
-<tex>X = (x^1, x^2, ..., x^n) \subset R^d</tex> - множество из <tex>n</tex> точек в <tex>d</tex>-мерном пространстве таких, что <tex>\nexists i \neq j : x_i \succ x_j</tex> - никакая точка не доминируется другой точкой из этого множества.
+<tex>X = \{x^1, x^2, ..., x^n\} \subset \mathbb{R}^d</tex> - множество из <tex>n</tex> точек в <tex>d</tex>-мерном пространстве таких, что <tex>\nexists i \neq j : x_i \succ x_j</tex> - никакая точка не доминируется другой точкой из этого множества.
-<tex>S(X) = \mu (\bigcup \limits_{x \in X} \{y | x \succ y\}) </tex> - гиперобъем множества <tex>X</tex>.
+<tex>S(X) = \mu (\bigcup \limits_{x \in X} \{y | x \succ y\}) </tex> - гиперобъем множества <tex>X</tex>, где <tex>\mu</tex> - мера Лебега.
 В частности, если <tex>X = \{x\}</tex>, то <tex>S(X) = \prod \limits_{i=1}^{d} x_i</tex>.
@@ Строка 28: / Строка 28: @@
 == Алгоритм LebMeasure ==
-Алгоритм LebMeasure обрабатывает точки множества <tex>X</tex> по очереди. Для каждой очередной точки <tex>x</tex> находится объем некоторого максимального по включению гиперкуба, доминируемого эксклюзивно только этой точкой <tex>x</tex> и она заменяется на некоторое множество ''порожденных'' точек, которые доминируют оставшуюся область, доминировшуюся до этого точкой <tex>x</tex>.
+Алгоритм LebMeasure<ref>K. Bringmann, T. Friedrich.: An Efficient Algorithm for Computing Hypervolume Contributions. Evolutionary Computation, Vol. 18, No. 3, pp 383-402, MIT Press. (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>.
@@ Строка 34: / Строка 34: @@
 Обработка точек продолжается, пока все точки не будут обработаны. Таким образом, время работы алгоритма напрямую зависит от количества порожденных точек. Легко заметить, что таких точек не более, чем <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> точка, что показано в [1]. Правда, если в этом примере точки обрабатываются в обратном порядке, то суммарное количество обработанных точек линейно зависит от <tex>n</tex> и <tex>d</tex>. Тем не менее, существуют примеры, для которых любой порядок обработки приводит к экспоненциальной зависимости числа порожденных точек от размерности пространства <tex>d</tex> и эта зависимость близка к <tex>n^d</tex> [1].
+К сожалению, эта верхняя оценка является достижимой. Например, если исходное множество <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> <ref name="while">
 == Алгоритм Hypervolume by Slicing Objectives (HSO) ==
-Под ''Objectives'' в названии данного алгоритма имеются в виду координаты пространства <tex>R^d</tex>.
+Под ''Objectives'' в названии данного алгоритма имеются в виду координаты пространства <tex>\mathbb{R}^d</tex>.
-Если алгоритм LebMeasure по очереди рассматривает все точки, то алгоритм HSO рассматривает по очереди все координаты, сводя задачу к меньшей на единицу размерности.
+Если алгоритм LebMeasure по очереди рассматривает все точки, то алгоритм HSO<ref>Zhou X., Sun C., Mao N., Li W.: Generalization of HSO algortihms for computing hypervolume for mutiobjective optimization problems, IEEE Congress on Evolutionary Computation (2007)</ref> рассматривает по очереди все координаты, сводя задачу к меньшей на единицу размерности.
 Изначально все точки сортируются по первой координате. Значения этой координаты используются для ''расслоения'' (разрезания) всего множества на <tex>n</tex> частей, внутри каждой из которых при движении вдоль первой координаты форма ''разреза'' (гиперплоскости), проходящего перпендикулярно оси первой координаты, не меняется. Таким образом, для подсчета объема каждой части необходимо найти объем разреза, и умножить на длину части вдоль первой координаты. При этом получившийся разрез имеет на единицу меньшую размерность.
@@ Строка 79: / Строка 80: @@
 }}
-Таким образом, на этот алгоритм получена более низкая оценка времени работы, чем на предыдущий, и это подтверждается на практике [1].
+Таким образом, на этот алгоритм получена более низкая оценка времени работы, чем на предыдущий, и это подтверждается на практике <ref name ="while"/>.
 == Сведение к задаче KMP (Klee's Measure Problem) ==
@@ Строка 85: / Строка 86: @@
 Задача KMP состоит в нахождении объема объединения прямоугольных гиперпараллелепипедов в <tex>d</tex>-мерном пространстве. Как показано в описании алгоритма IEA, исходная задача легко сводится к этой, если каждой точке поставить в соответствие гиперкуб с одной вершиной в центре координат, а противоположной - в этой точке.
-Существует несколько алгоритмов решения задачи KMP, самый оптимальный из которых использует идеи сканирующей гиперплоскости, [[Статистики на отрезках. Корневая эвристика|корневой эвристики]] и КД-дерево, и позволяет решать задачу за время <tex>O(n^{d/2}\log n)</tex>. Рассмотрим его.
+Существует несколько алгоритмов решения задачи 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>N. Beume.: S-Metric calculation by considering dominated hypervolume as Klee’s measure problem. Evolutionary Computation, 17(4), pp 477–492. (2009)</ref><ref>N. Beume, G. Rudolph.: 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)
 Для начала изложим идею сканирующей гиперплоскости. Рассмотрим всевозможные значения <tex>d</tex>-ой координаты у точек множества <tex>X</tex>.
@@ Строка 91: / Строка 93: @@
 Теперь изложим идею алгоритма на примере трехмерного пространства.
-Будем считать, что сканирующая плоскость двигается перепендикулярно оси <tex>OZ</tex>. В каждый момент проекция всех параллелепипедов на эту плоскость предствляет собой множество прямоугольников и необходимо уметь обрабатывать следующие три запроса:
+В трехмерном пространстве сканирующая гиперплоскость превращается в обычную плоскость. Будем считать, что она всегда располагается перепендикулярно оси <tex>OZ</tex> и двигается от минимальных значений по этой оси до максимальных. В каждый момент проекция всех параллелепипедов на эту плоскость представляет собой множество прямоугольников и необходимо уметь обрабатывать следующие три запроса:
 # добавить прямоугольник
 # удалить прямоугольник
@@ Строка 180: / Строка 182: @@
 == Источники ==
-# 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)
+<references/>

@@ Строка 75: / Строка 75: @@
 продолжаем доказательство теоремы по индукции:
-<center><tex>f(n, d) = {n + d - 2 \choose d - 1} = \sum \limits_{i = 1}^{n} {n + d - 2 + i \choose d - 2} = \sum \limits_{k = n}^{1} {n + d + 2 - (n - k + 1) \choose d - 2} = \sum \limits_{k = 1}^{n} {k + d - 3 \choose d - 2} = \sum \limits_{k = 1}^{n}{k + (d - 1) - 2 \choose (d - 1) - 1} = \sum \limits_{k = 1}^{n}{f(k, d - 1)}</tex></center>
+<center><tex>f(n, d) = {n + d - 2 \choose d - 1} = \sum \limits_{i = 1}^{n} {n + d - 2 - i \choose d - 2} = \sum \limits_{k = n}^{1} {n + d + 2 - (n - k + 1) \choose d - 2} = \sum \limits_{k = 1}^{n} {k + d - 3 \choose d - 2} = \sum \limits_{k = 1}^{n}{k + (d - 1) - 2 \choose (d - 1) - 1} = \sum \limits_{k = 1}^{n}{f(k, d - 1)}</tex></center>
 }}