Эффективные генераторы

Эвристика для решения задач

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

Даже когда группа Р велика, как это обычно бывает в слож­ных процессах решения, генератор решений может рассматривать на ранней стадии те части Р, которые скорее всего бесплодны. Например, многие проблемы имеют следующую форму: группа решений включает все элементы Р со свойством А, свойством В и свойством С. Нет генераторов, которые будут создавать элемен­ты, обладающие всеми тремя свойствами. Однако могут сущест­вовать генераторы, которые создают элементы, обладающие двумя какими-то свойствами из этих трех. То, какой генератор будет вы­бран, зависит от того, какие требования наиболее сложны, и от относительной стоимости выработки решений. Если большинство элементов отвечает А, тогда обосновано создание элементов С и В, так как можно ожидать, что А скоро появится. Если элементы с А редки, лучше создавать элементы, которые имеют свойство А.

«Логик-теоретик» дает нам четкий пример этого типа эврис­тики. Вспомним, что задача «логика-теоретика» заключается в поисках доказательств. Доказательство представляет собой список логических выражений, удовлетворяющих следующим требо­ваниям:

A. Начало списка включает известные теоремы (любое число их).

B. Все другие выражения в списке являются прямыми и истинными следствиями выражений, приведенных выше.

C. Последнее выражение списка является выражением, которое доказывается.

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

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

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

Дата добавления: 2014-11-06