Я читал о некоторых алгоритмах геометрической маршрутизации, там написано, что при использовании эвристик в версии основного алгоритма это может повысить производительность, но лишает асимптотической оптимальности.
Почему это так? Должны ли мы предпочесть асимптотическую оптимальность лучшей производительности? Существуют ли прототипические случаи, когда следует предпочесть асимптотическую оптимальность? Известны ли какие-то ориентиры?
Я думаю, вы спрашиваете о проблемах оптимизации, когда эвристики работают быстро, но могут не достигать полностью оптимального решения, тогда как действительно оптимальные алгоритмы поиска решения могут работать намного медленнее в худшем случае, хотя они всегда дают полностью оптимальное решение. Если да, то вот некоторая информация. В общем, решение использовать эвристический алгоритм часто зависит от того, насколько хорошо он аппроксимирует оптимальное решение «на практике», достаточно ли это типичное качество решения для вас, и считаете ли вы, что ваш конкретный экземпляр проблемы попадает в классификацию или нет. Категория проблем, с которыми приходится сталкиваться на практике. Если вам интересно, вы можете найти алгоритмы аппроксимации для NP-полных задач. Есть некоторые проблемы, когда оценка решения, найденного эвристикой, находится в пределах постоянного множителя (1 + эпсилон) оценки оптимального решения, и вы можете выбрать эпсилон; однако обычно время работы увеличивается по мере уменьшения эпсилон.
Я предполагаю, что они говорят об использовании (не-допустимых) эвристик для алгоритмов аппроксимации. Например, задача о коммивояжере является NP-полной, однако существуют эвристические приближенные методы, которые намного быстрее, чем известные алгоритмы для NP-полных задач, но гарантируют лишь несколько процентов от оптимального.
