Есть ли случай, когда эвристический подход гарантированно обеспечивает оптимальное решение?

Как сказано (например, в Википедии), эвристика дает решение, которое не гарантирует оптимального решения. Я думаю, что это верно во многих случаях, но что, если мы используем, например, эвристическую оценку стоимости (например, в алгоритме A *) для достижения решения, которое может быть доказано как оптимальное. В таком случае не следует ли нам называть этот алгоритм эвристикой?


algorithm terminology heuristics
person Barpa    schedule 21.05.2014    source источник
comment
Если существует экземпляр проблемы, в котором алгоритм завершается без предоставления оптимального решения, то алгоритм является эвристическим. Нахождение решений, оптимальность которых может быть доказана в противном случае (с использованием точного метода), не меняет эвристической природы алгоритма. Как говорит Ларсманс ниже, если можно доказать, что алгоритм гарантирует оптимальность при завершении работы при определенных технических условиях, то алгоритм является точным. Таким образом, во многом зависит от условий, которые создают проблему, классифицируется алгоритм как эвристический или нет.   -  person Ioannis    schedule 21.05.2014
comment
Итак, если я хорошо понял вас и larsmans, точный алгоритм, который использует эвристическую функцию как часть своей для отсечения бесплодных ветвей дерева поиска (которые на 100% не приводят к какому-либо оптимальному решению), нельзя было бы назвать эвристикой. Но как я могу это назвать? Может быть, точный алгоритм с эвристической функцией?   -  person Barpa    schedule 22.05.2014
comment
Я бы просто назвал это точным алгоритмом, и если вам нужно уточнить детали, то то, что вы сказали, также верно. Тот факт, что он использует эвристическую часть, делает его более эффективным на практике, не имеющим ничего общего с точностью. Даже если эвристика будет удалена, алгоритм останется точным. Кстати, точное не означает эффективное в практическом или математическом смысле. Например, перебор точным, но неэффективным методом.   -  person Ioannis    schedule 22.05.2014

Ответы (1)


arrow_upward
5
arrow_downward

Учитывая эвристическую функцию оценки стоимости, которая подчиняется определенным законам, A * представляет собой алгоритм в строгом смысле метода вычисления, который всегда дает правильный ответ на заранее определенный набор проблем. (*) Тот факт, что он использует < / em> эвристика не делает саму A * эвристикой.

(*) Бывают случаи, когда оптимальный путь между A и B может не существовать, и A * будет работать вечно; для таких задач A * - полуалгоритм.

person Fred Foo    schedule 21.05.2014