4. Исследование альтернативных возможностей

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

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

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

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

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

Рис. 4.1. Поиск связан с методами исследования древовидных структур, которые довольно часто описывают предметную область. Проблемы управления связаны с тем, каким образом система решения задачи переключается между своими под процессами

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

На рис. 4.2 изображена диаграмма преследуемых нами целей. Как видно, под общим заголовком "поиск" расположились три вопроса. Первый, основные методы поиска, охватывает такие классические понятия, как поиск в глубину и поиск в ширину, а также различные методы поиска максимума и процедуры поиска оптимального пути. Далее общий вопрос поиска посредством наложения ограничений будет обсуждаться с использованием специального случая задачи распространения меток линий по контурному рисунку. И наконец, имеется еще разыгрывание игр с помощью ЭВМ, в котором понятие поиска приобретает особое значение.