25
правок
Изменения
Нет описания правки
Алгоритм LebMeasure обрабатывает точки множества <tex>X</tex> по очереди. Для каждой очередной точки <tex>x</tex> находится объем некоторого максимального по включению гиперкуба, доминируемого эксклюзивно только этой точкой <tex>x</tex> и она заменяется на некоторое множество ''порожденных'' точек, которые доминируют оставшуюся область, доминировшуюся до этого точкой <tex>x</tex>.
Например, если изначально было четыре точки в трехмерном пространстве <center><tex>(6, 7, 4), (9, 5, 5), (1, 9, 3), (4, 1, 9)</tex>, </center> то точка <tex>(6, 7, 4)</tex> эксклюзивно доминирует куб с одним концов в <tex>(6, 7, 4)</tex>, а другим - в <tex>(4, 5, 3)</tex>. После добавления объема этого куба в ответу, точка <tex>(6, 7, 4)</tex> порождает три точки: <center><tex>(4, 7, 4), (6, 5, 3), (6, 7, 3)</tex>.</center>При этом, точка <tex>(6, 5, 4)</tex> доминируется точкой <tex>(9, 5, 5)</tex> и сразу удаляется из множества <tex>X</tex>.
Обработка точек продолжается, пока все точки не будут обработаны. Таким образом, время работы алгоритмы напрямую зависит от количества порожденных точек. Легко заметить, что таких точек не более, чем <tex>n^d</tex>, поскольку каждая координата каждой порожденной точки равна соответствующей координате некоторой точки исходного множества <tex>X</tex>.
|proof=
База: <center><tex>f(n, 1) = 1</tex>.</center>
Также, из алгоритма расслоения следует, что из части с <tex>n</tex> точками будет получено по одной части для каждого <tex>i = 1...n</tex>, то есть: <center><tex>f(n, d) = \sum \limits_{i = 1}^{n}f(i, d - 1)</tex>.</center>
{{Лемма
|statement=<center><tex>{x \choose y} = {x - r \choose y} + \sum \limits_{i = 1}^{r} {x - i \choose y - 1}</tex>.</center>
|proof=Индукция по <tex>r</tex>. База: <center><tex>{x \choose y} = {x - 1 \choose y} + {x - 1 \choose y - 1}</tex>.</center>
Переход: предполагаем, что утверждение верно для <tex>r = j</tex>. Раскрываем первое слагаемое в правой части предположения, аналогично базе и получаем:
<center><tex>{x \choose y} = {x - j - 1 \choose y} + {x - (j + 1) \choose y - 1} + \sum \limits_{i = 1}^{j}{x - i \choose y - 1} = {x - (j + 1) \choose y} + \sum \limits_{i = 1}^{j}{x - i \choose y - 1}</tex>.</center>
}}
{{Лемма
|statement=<center><tex>{x \choose y} = \sum \limits_{i = 1}^{x - y + 1} {x - i \choose y - 1}</tex>.</center>
|proof=Подставляем в предыдущую лемму <tex>r = x - y</tex> и получаем:
<center><tex>{x \choose y} = {y \choose y} + \sum \limits_{i = 1}^{x - y} {x - i \choose y - 1} = {x - (x - y + 1) \choose y - 1} + \sum \limits_{i = 1}^{x - y} {x - i \choose y - 1} = \sum \limits_{i = 1}^{x - y + 1} {x - i \choose y - 1}</tex>.</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>
}}
== Источники ==
# 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)
# [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/seminars/1320.pdf 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)]
# K. Bringmann, T. Friedrich.: An Efficient Algorithm for Computing Hypervolume Contributions. Evolutionary Computation, Vol. 18, No. 3, pp 383-402, MIT Press. (2010)
# N. Beume.: S-Metric calculation by considering dominated hypervolume as Klee’s measure problem. Evolutionary Computation, 17(4), pp 477–492. (2009)
