25
правок
Изменения
Нет описания правки
Также, из алгоритма расслоения следует, что из части с <tex>n</tex> точками будет получено по одной части для каждого <tex>i = 1...n</tex>, то есть: <center><tex>f(n, d) = \sum \limits_{i = 1}^{n}f(i, d - 1)</tex>.</center>
2)
Операции в этом дереве выполняются аналогично трехмерному случаю и каждая операция добавления или удаления в КД-дерево размерности <tex>d</tex> занимает <tex>O(n^{(d-1)/2} \log n)</tex> времени. Выполняя сканирование гиперплоскостью вдоль одной из координат получаем КД-дерево размерности <tex>d-1</tex>, в котором необходимо провести <tex>O(n)</tex> операций, то есть суммарное время работы алгоритма равно: <tex>O(n \times n^{(d-1-1)/2} \log n) = O(n^{d/2} \log n)</tex>. При этом хранение КД-дерева требует <tex>O(n^{d/2})</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)
# 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)
# 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)
# Overmars, M.H., Yap, C.K.: New upper bounds in Klee’s measure problem. SIAM Journal on Computing 20(6), pp 1034–1045. (1991)
# Klee, V.: Can the measure of S[ai, bi] be computed in less than O(n log n) steps? In: American Mathematical Monthly. Volume 84, pp 284–285. (1977)
