15.4. Итоги анализа систем решения проблем конструирования

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

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

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

Совершенно очевидно, что размер пространства решений влияет на проблемы конструирования значительно сильнее, чем на проблемы классификации. Даже если обратиться к простейшим игровым задачам, вроде задачи о ферзях, которая рассматривалась в одном из упражнений главы 1, то и на их примере нетрудно убедиться, что метод, который позволит решить задачу о четырех или восьми ферзях, нельзя применить, когда речь пойдет о сотне или тысяче ферзей. Проблемы классификации относятся к числу тех, с которыми следует поступать по принципу "разделяй и властвуй", особенно если пространство категорий может быть организовано иерархически.

К слову сказать, существует множество реальных задач, типа планирования поведения роботов или составления расписания мероприятий, которые включают комбинаторику, не позволяющую использовать принцип "разделяй и властвуй". Частично это объясняется отсутствием подходящей метрики, которая позволила бы оценить, насколько близко конкретный фрагмент решения подходит к общему решению задачи. План можно оценить только целиком; нельзя сказать, насколько он будет хорош по характеристикам его отдельных этапов. Подход, основанный на "библиотеке заготовок" (он использовался в системе ONCOCIN; см. главу 10), также не годится для решения большинства проблем конструирования.

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

В главе 18 будет рассмотрена система, предназначенная для идентификации трехмерных структур протеинов в растворах. Комбинаторика, связанная с просмотром всех возможных вариантов компоновки молекул, совершенно очевидно не позволяет использовать исчерпывающий поиск или обратное прослеживание на сколько-нибудь значительную глубину. Поэтому программа организована таким образом, что в ней имеется несколько баз знаний, поддерживающих разные эвристики управления поиском в пространстве решений. Такая архитектура, получившая, название системы с доской объявлений (blackboard system), обеспечивает мощный механизм реализации таких стратегий, как последовательное уточнение частичных решений и восстановление после принятия неудачных решений.

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