4430
правок
Задача о размещении объектов: различия между версиями
Материал из WEGA
Задача о размещении объектов (посмотреть исходный код)
Версия от 12:05, 24 апреля 2018
, 24 апреля 2018→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 24: | Строка 24: | ||
Алгоритм | Алгоритм <math>\gamma \;</math>-аппроксимации представляет собой полиномиальный алгоритм, который в задаче минимизации гарантированно дает допустимое решение со значением ''не более'' <math>\gamma \; z^*</math>, где <math>z^* \;</math> - значение оптимального решения, а <math>\gamma \ge 1 \;</math>. Если <math>\gamma = 1 \;</math>, алгоритм дает оптимальное решение. В задаче минимизации алгоритм дает решение со значением ''не менее'' <math>\gamma \; z^*</math>, где <math>0 \le \gamma \le 1 \;</math>. | ||
