Абстрактная модель поведения при решении задачи

Мы обращаемся теперь к общей теории решения задачи, с тем чтобы позже вернуться к специфическим вопросам «творческой» части спектра процесса решения задач.

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

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

Существуют различные пути классификации Процессов, исполь­зуемых людьми при решении задачи. Полезным является разли­чение процессов нахождения возможных решений (создание чле­нов Р, которые могут принадлежать к S) от процессов определения того будет ли найденное предложение фактически решением (про­веряя, относится ли к S созданный элемент Р). Мы называем процессы первого класса процессами выработки решения, а вто­рого класса — процессами проверки (верификации).

В достаточно малом лабиринте, где члены S, как только они открыты, легко могут быть опознаны как решение, нахождение решения тривиально (примером является Т-образный лабиринт для крыс с пищей на одной из дорожек). Трудности при сложном процессе поисков решения возникают в связи с комбинацией двух факторов: размеров группы возможных решений, которые долж­ны быть исследованы, и задачей установления того, действитель­но ли соответствует предложенное решение условиям задачи. Ис­пользуя нашу формальную модель решения задачи, мы можем ча­сто получать значащие меры трудности конкретных проблем и меры эффективности конкретных устройств и процессов решения задачи. Рассмотрим некоторые примеры.

Обратимся к выбору хода в шахматах. В среднем шахматист чья очередь совершать ход, осуществляет свой выбор из 20 или 30 альтернатив. Поэтому «нахождение» возможных ходов не пред­ставляет трудностей, но огромные трудности существуют при оп­ределении того, будет ли конкретный дозволенный ход хорошим ходом. Проблема не в генераторе, а в проверочном компоненте деятельности. Однако принципиальный метод для оценки хода со­стоит в рассмотрении некоторых противоположных возможных ответов, собственных ответов и т.д., только попытки оценить резуль­таты позиций после этого лабиринта возможных последователь­ностей ходов осуществляются с некоторой глубиной. Лабиринт последовательности ходов чрезвычайно велик. Если мы рассматриваем пять последовательных ходов для каждого игрока, пред­полагая в среднем 25 дозволенных продолжений на каждой сту­пени, мы находим, что Р, группа таких последовательностей хо­дов, включает около 10¹⁴ (100 миллионов миллионов) членов.

Еще один пример будет полезен для уяснения того, как раз­личные устройства сокращают количество проб, требуемых для нахождения решения задачи. Рассмотрим сейф, замок которого включает 10 независимых дисков, каждый из них пронумерован от 00 до 99. Сейф будет иметь 100¹⁰=10²⁰ или 100 биллионов возмож­ных положений дисков, только одно из которых будет открывать его. Однако если сейф неисправен и всякий раз возникает легкий щелчок, когда любой диск установлен в правильном положении, то потребуется в среднем только 50 проб, чтобы открыть сейф. 10 последовательных щелчков, предупреждающих взломщика, когда «теплее», вот и все отличие неразрешимой задачи от три­виальной.

Итак, если мы можем получить информацию, которая подска­зывает нам, какое решение испытать, и, в частности, если мы мо­жем получить информацию, которая позволяет нам раздробить большую проблему на несколько небольших задач и узнать, успеш­но ли мы решили каждую из небольших задач, — поисковая деятельность может быть значительно сокращена.

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

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

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

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

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

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

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

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

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

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

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

Простые селективные эвристики

Когда субъект, решающий задачу, сталкивается с группой альтернатив, обычный эвристический прием состоит в выявлении с самого начала возможных путей при помощи относительно доступного текста. Чтобы определить ценность этого приема, рассмот­рим лабиринт, содержащий m альтернатив в каждой узловой точ­ке и имеющий длину k. Если есть один правильный путь к цели, то для того, чтобы найти его при помощи случайных поисковых действий, потребуется в среднем 1/2m^k проб. Если эвристический тест позволит отбросить как бесполезные половину альтернатив в каждой узловой точке, тогда при случайном поиске с примене­нием этой эвристики в среднем потребуется только 1\2*(1/2m^k) Проб. Это сокращает число проб в отношении 2^k, что составит при лабиринте, включающем лишь 7 звеньев, число 128, а при лабиринте в 10 звеньев — свыше тысячи.

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

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