page_type: concept
Приближенные алгоритмы
Для некоторых задач нет открытого алгоритма решения способного выполниться за разумное время. В таких случаях может быть допустимо применение алгоритмов которые выдают приближенный к корректному результат но работают за приемлемое время.
Критерием для таких алгоритмов являются скорость работу и близость решения к оптимальному.
Приближенные алгоритмы используются для решения NP-полных задач, обычно в таких случаях следуют подходу жадных алгоритмов.
Ссылки
- Грокаем алгоритмы. Адитья Бхаргава. Питер. 2018. Глава 8. Жадные алгоритмы. Задача о покрытии множества. Приближенные алгоритмы