Материал: 2488

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

Специалисты, принимающие решения, используют немонотонные рассуждения, или рассуждения здравого смысла (основывающиеся на общих элементарных знаниях). Несмотря на то, что рассуждения здравого смысла являются довольно обыденными для людей, очень трудно достигнуть требуемого уровня реализации подобных рассуждений в СППР. Тем не менее в некоторых классических ЭС, таких как MYCIN, PROSPECTOR, этот метод довольно успешно реализован для сокращения пространства поиска.

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

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

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

31

дач. Этот граф называется графом «и»/«или». Вершины этого графа представляют описания задач и подзадач. Граф «и»/«или» содержит вершины двух типов. Тип «и» соответствует задаче, решаемой при условии реализации всех ее подзадач в соответствующих вершинахпреемниках. Тип «или» соответствует задаче, решение которой возможно получить при решении одной из альтернативных подзадач в соответствующих вершинах-преемниках. На рис. 4 представлен фрагмент графа типа «и»/«или».

Рис. 4. Представление разбиения исходной задачи на подзадачи в виде графа «и»/«или»

S0

Рис. 5. Преобразование графа «и»/«или»

Исходная задача S0 разбивается на группы подзадач. Она может

32

быть решена путем решения подзадач либо S1 и S2; либо S3; S4 и S5. Вершины N, S3, M, S5 – это вершины типа «и». Штриховой линией показан вариант решающего графа исходной задачи. Решения подзадач S2, S7, S9, S10, S11 предполагают известными. Решения других подзадач неизвестны. В структуру обычно вводятся дополнительные вершины, чтобы каждое множество подзадач формировалось под своей собственной родительской вершиной. Вершина графа «и»/«или» может принадлежать к типу «и» либо «или». Поэтому исходный граф преобразуется и вводятся дополнительные вершины N и M (рис. 5), которые служат отдельными родительскими вершинами для подзадач {S1, S2} и {S4, S5}. Таким образом, вершина S0 преобразуется в вершину «или».

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

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

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

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

33

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

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

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

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

34

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

При поиске решений в больших пространствах состояний ис-

пользуются также эвристические методы и процедуры. Часто труд-

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

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

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

35