Вероятностное округление

В информатике и исследовании операций многие задачи комбинаторной оптимизации вычислительно неподатливы для решения задачи точно (т.е. для получения оптимального решения).

Многие такие задачи допускают быстрые (полиномиального времени) аппроксимационные алгоритмы — то есть алгоритмы, гарантированное возвращающие приближённое к оптимальному решение для любого входа.

Вероятностное округление — это широко используемый подход для разработки и анализа таких аппроксимационных алгоритмов. Базовая идея — использование вероятностного метода для преобразования соответствующей оптимального решения задачи линейного программирования (ЛП) в приближённое к оптимальному решению исходной задачи.

Источник: Википедия

а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ э ю я