10.2.3. Поиск

Большие размеры баз знаний и пространства состояний, необходимые для решения практических символьных задач, обусловливают обязательное применение стратегии поиска либо так называемых релевантных фактов, содержащихся в базе знаний, либо путей решения в пространстве состояний задачи. На рис. 10.6 изображены различные виды поиска, включая чисто случайный поиск и весьма специфический эвристический поиск (эвристика предполагает использование знаний по определенной проблеме с целью придать поиску направленный характер). Хотя на этой упрощенной диаграмме стратегии поиска разделены на конкретные категории, однако фактически такого четкого разграничения провести невозможно. Чем менее направленным является поиск, тем большее время требуется для достижения цели. С другой стороны, чем более целенаправленным

Рис. 10.5. Элементы исчисления предикатов.

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

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

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

Рис. 10.6. Иерархия стратегий поиска,

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

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

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

Рис. 10.7, а — поиск с помощью направленного графа; 6 — дерево поиска,

системах параллельной обработки, которые будут обсуждаться в разд. 10.4.

До этого места в изложении процедуру решения проблемы и процесс проведения рассуждений представляли как последовательность событий, выполняемую из начального состояния в направлении состояния (состояний) цели. Другой способ, которым иногда пользуются, исходит из заданной цели и выполняется в обратном порядке, при этом стараются удовлетворить начальным условиям. В обратной процедуре проведения рассуждений, известной среди специалистов по ИИ как способ рассуждений «от цели к фактам», сначала находят одно или более состояний, которые могут привести к определению цели, и проверить, достигнуто ли соответствие с начальным состоянием (состояниями). Если нет, то поиск продолжается. Для систем продукций это означает, что в этом случае части «тогда» согласуются между собой и соответственно части «если» запускаются в действие (например, если часть «тогда» используется для нахождения более отдаленной вершины). Конкретно выбор либо процедуры от «цели к фактам», либо процедуры «от фактов к цели» определяется прежде всего двумя факторами — соотношением случаев ветвления с переходом назад по телу программы и случаев ветвления с переходом вперед, а также соотношением числа состояний цели и числа начальных состояний. Другими словами, если сформированное дерево поиска в конкретной проблемной области разветвляется в значительно большей степени при прямой процедуре поиска, чем при обратной процедуре поиска, то в этом случае процедура «от цели к фактам» будет более целесообразной. Если разветвление в обоих направлениях приблизительно одинаково, решающее значение приобретат число состояний. Процедура «от цели к фактам» выглядит более привлекательной при решении задач синтеза сложных объектов, когда существует широкий спектр исходных объектов, на основе которых приводится синтез. Примером служит задача определения того, какие характеристики материала необходимы для оптимального изготовления конкретного устройства. Здесь лучше было бы начать процедуру поиска с состояния цели (требований к устройству), чем с поисков наборов характеристик для всех возможных материалов.

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

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

прекрасным примером этого; в противном случае шахматные задачи не могли бы решаться с помощью компьютеров. Как упомянуто выше, варьирование объемами информации может быть использовано для продуманного управления выше обсуждавшимися схемами поиска. Такие методики, как индексация, факторизация, сопоставление с образцом относят к категории эвристических методов общего назначения; однако их роль в ограничении сложных процедур поиска сравнительно невелика, тем более что они часто делают необходимым использование существенно более сложных эвристических методов, по сравнению с указанными выше методиками общего назначения. При индексировании используются заранее установленные схемы присвоения индексов, описывающих состояние задачи, а также задающих процесс запоминания правил, применяемых к каждому из состояний задачи (при этом требуется, чтобы эти правила могли быть связаны с индексом данного состояния). Из области хранения данных об определенном состоянии задачи впоследствии можно вызвать индекс этого состояния, что в свою очередь позволяет вызвать все правила, которые могли быть использованы. Более привлекательной выглядит операция факторизации. Если база знаний может быть разделена на большие множества данных, мало пересекающиеся между собой, то при рассмотрении соответствующей информации о проблемной области целые секции могут быть исключены. Например, если рассматриваемый вопрос связан с диагностикой легочных заболеваний, то для системы не требуется поиск части ее базы знаний, связанной с процедурами при проведении реальных хирургических операций на легком. Ограничение поиска также может быть достигнуто с помощью метода сопоставления с образцом, аналогичного традиционным задачам сравнения, где операция сопоставления используется для проверки того, что были найдены правильная форма, слово и т. д. Сопоставление с образцом часто используется в задачах распознавания речи, понимания естественного языка, распознавания образов; все они будут обсуждаться в разд. 10.3.

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

Рис. 10.8. Поиск «наилучшего первого».

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

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