Эвристические алгоритмы vs приближённые алгоритмы

[avli]

Всем привет!

Сегодня озадачился вопросом, в каких отношениях с математической или, возможно, философской точки зрения находятся эвристические и приближённые алгоритмы? Корректно ли включать класс эвристических алгоритмов в приближённые? Корректно ли оценивать качество эвристических алгоритмов с помощью коэффициента аппроксимации и т.д.

Заранее спасибо.

[mserg]

«Эвристический» и «приближенный» - это, так сказать, перпендикулярные понятия. Так, эвристический алгоритм может быть точным или приближенным. Или «наоборот», приближенный алгоритм может использовать эвристики или может не использовать.

Если допустить некоторую вольность обобщения, то можно сказать, что эвристика имеет вероятностную природу. Отдавая предпочтения при поиске более вероятному направлению, можно достичь цели эффективнее. Эффективность эвристики обычно проверяются на множестве тестовых примеров.

«Приближенный» же предполагает, что в жертву может быть принесено «качество» поиска, или даже некоторые ограничения могут быть нарушены.

Нужно отметить, что классификация алгоритмов на «эвристический», «приближенный», и т.п. применима только для самых примитивных случаев. Когда задача, в том или ином виде, подвергается декомпозиции, то подзадачи могут решаться как точными, так и приближенными алгоритмами, с использованием эвристик или без оных.

[Esp_]

mserg в сообщении #762938 писал(а):

Или «наоборот», приближенный алгоритм может использовать эвристики или может не использовать.

mserg в сообщении #762938 писал(а):

Нужно отметить, что классификация алгоритмов на «эвристический», «приближенный», и т.п. применима только для самых примитивных случаев. Когда задача, в том или ином виде, подвергается декомпозиции, то подзадачи могут решаться как точными, так и приближенными алгоритмами, с использованием эвристик или без оных.

Вы не путайте человека.
На самом деле приближенные и эвристические алгоритмы - это одно и то же.
Существует формальное определение, что такое корректный алгоритм и что такое некорректный алгоритм.

Ваше второе утверждение вообще непонятно, причем тут декомпозиция вообще? Алгоритм - это черный ящик.

[mserg]

Есть такая программа cbc – решение частично-целочисленных задач линейного программирования.

В этой программе, например, есть эвристики:
* Выбор узла и направления ветвления
* Поиск допустимого решения в некоторых узла дерева поиска, не делая ветвлений
Т.е. точное решение можно искать с помощью эвристик. Если выключить эвристики, что-нибудь нетривиальное решить не получится.

И в этой же программе есть два параметра, который позволяет решать задачу приближенно:
* Абсолютная допустимая погрешность
* Относительная допустимая погрешность
Если выключить эвристики, и задать «ненулевые» погрешности, то будет приближенный неэвристический алгоритм.

Эвристики в пакеты оптимизации включаются на основе тестов. Обычно есть много-много тестовых задач (часто взятых из реальной жизни), и на них экспериментируют в поиске работоспособных эвристик. Практически эвристика строится как бы в виде (чуть ли не вероятностной) гипотезы, а потом проверяется на множестве задач.

Таким образом, на «самом деле», «приближение» (погрешность) и эвристика (критерий выбора направления поиска) – это две разные характеристики алгоритма, друг с другом несравнимые.

Что касается формальных математических изысков, я давно все забыл. Может быть там слова «эвристический» и «приближенный» используются как синонимы. Но на практике, это не так.

[Esp_]

mserg в сообщении #769235 писал(а):

Таким образом, на «самом деле», «приближение» (погрешность) и эвристика (критерий выбора направления поиска) – это две разные характеристики алгоритма, друг с другом несравнимые.

Я понял, о чем вы. Но это не есть формальные рассуждения. Вроде бы на интуитивном уровне это как-то понятно, но формально провести грань между эвристикой и не эвристикой невозможно. Поэтому, единственная грань, которая здесь может быть проведена (помимо точности алгоритма) - это его корректность.

Ваши примеры по получению конкретных значений а.п. и о.п. тоже основаны на эвристике о том, что если сложить чуть меньше чисел, то получится "чуть меньше" ответ.

[bin]

mserg в сообщении #762938 писал(а):

«Эвристический» и «приближенный» - это, так сказать, перпендикулярные понятия. Так, эвристический алгоритм может быть точным или приближенным. Или «наоборот», приближенный алгоритм может использовать эвристики или может не использовать.

Cогласен:

Цитата:

Эвристический алгоритм — алгоритм, использующий различные разумные соображения без строгих обоснований (М.Гэри, Д.Джонсон, Вычислительные машины и труднорешаемые задачи, М.: Мир, 1982, C.155.)

Приближенный алгоритм может иметь строгое доказательство корректности, т.е. гарантию, что результат его работы будет иметь погрешность, не превышающую определенной величины от точного решения. Приближенный алгоритм может и не иметь такого доказательства, тогда он будет и приближенным, и эвристическим. Эвристический алгоритм может во всех известных случаях выдавать точный результат, но нет гарантии, что он не ошибется в новом случае. На практике бывает и так, что автору алгоритма неохота возиться с доказательством, и он публикует алгоритм как эвристический