1632
правки
Изменения
м
{{В разработке}} Гиперобъем является индикатором Парето-фронта, набирающим в последнее время популярность<ref>[http://www.mpi-inf.mpg.de/~tfried/paper/2009GECCO.pdf Friedrich T., Horoba C., Neumann F. — Multiplicative Approximations and the Hypervolume Indicator (2009)]</ref><ref>[http://www.mpi-inf.mpg.de/~tfried/paper/2010GECCO_Hyp.pdf Friedrich T., Bringmann K. — The Maximum Hypervolume Set Yields Near-optimal Approximation (2010)]</ref>. Важной составляющей многих оптимизирующих алгоритмов, использующих индикатор гиперобъема, является вычисление вклада одного элемента Парето-фронта. К сожалению, даже вычисление минимального вклада (Minimal Contribution, MINCON) и нахождение соответствующего ему элемента (Least Contributor, LC) являются трудными задачами. Более того, даже аппроксимации этих задач являются NP-трудными<ref>[http://www.mpi-inf.mpg.de/~tfried/paper/2009EMO.pdf Bringmann K., Friedrich T. Approximating the least hypervolume contributor: NP-hard in general, but fast in practice (2009)]</ref>.
== Источники ==# Bringmann K., Friedrich T. Approximating the least hypervolume contributor: NP-hard in general, but fast in practice (2009)<references />
rollbackEdits.php mass rollback
== Используемые обозначения ==
|definition=
Задача #MON-CNF – задача нахождения числа удовлетворяющих подстановок для монотонной булевой формулыфункции, записанной в КНФ, <tex>f = \bigwedge \limits_{k=1}^n \bigvee \limits_{i \in C_k} x_i</tex>,
где клозы <tex> C_k \subseteq {\{1,...,d\}}</tex>.
За <tex>\Box(a_1, \ldots, a_d)</tex> будем обозначать прямоугольный гиперпараллелепипед <tex>[0, a_1] \times \ldots \times [0, a_d]</tex>.
Пусть <tex>f = \bigwedge \limits_{k=1}^n \bigvee \limits_{i \in C_k} x_i</tex> – монотонная булева формула функция в КНФ, <tex> C_k \subseteq {\{1,...,d\}}</tex>.
Построим параллелепипеды <tex>A_k = \Box(a_1^k, \ldots, a_d^k, 2^d + 2) \subseteq \mathbb{R}^{d+1}</tex> для каждого клоза формулы, при этом
}}
