Эвристика

Фон

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

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

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

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

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

Примеры

Polya

Вот некоторые другие часто используемые эвристики из книги Полиа "Как решить задачу", вышедшей в 1945 году:

• Если вам трудно понять задачу, попробуйте нарисовать картинку.
• Если вы не можете найти решение, попробуйте предположить, что у вас есть решение, и посмотреть, что можно из этого вывести ("работа назад").
• Если проблема абстрактна, попробуйте рассмотреть конкретный пример.
• Попробуйте сначала решить более общую проблему: "парадокс изобретателя": более амбициозный план может иметь больше шансов на успех.

Проблема с упаковкой

Одним из примеров, когда эвристика может быть полезной, является проблема упаковки. Задача состоит в том, чтобы упаковать несколько предметов. Существуют правила, которые необходимо соблюдать. Например, каждый предмет имеет ценность и вес. Задача состоит в том, чтобы получить наиболее ценные предметы с минимально возможным весом. Другой пример - уместить несколько предметов разного размера в ограниченном пространстве, например, в багажнике автомобиля.

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

Поэтому это эвристическое решение.

Пример проблемы упаковки. Это одномерная (с ограничениями) проблема ранца: какие коробки следует выбрать, чтобы максимизировать сумму денег и сохранить общий вес менее 15 кг? Многомерная задача может учитывать плотность или размеры коробок, последнее - типичная проблема упаковки. (Решение в этом случае - выбрать все коробки, кроме зеленой).