Оптические вычисления - Арратуна Р.
Скачать (прямая ссылка):
проведено "от цели к фактам" вследствие исключительно большого числа
путей, ведущих к победе.
Для многих практических задач пространство состояний является настолько
большим, что обычно жертвуют поиском гарантированных оптимальных решений
в пользу применения специальных стратегий и тактики ограничения процесса
поиска и удовлетворяются хорошим решением, отказываясь от наилучшего
решения. Процесс поиска в шахматных задачах является
Глава 10. Оптика и символьные вычисления
287
прекрасным примером этого; в противном случае шахматные задачи не могли
бы решаться с помощью компьютеров. Как упомянуто выше, варьирование
объемами информации может быть использовано для продуманного управления
выше обсуждавшимися схемами поиска. Такие методики, как индексация,
факторизация, сопоставление с образцом относят к категории эвристических
методов общего назначения; однако их роль в ограничении сложных процедур
поиска сравнительно невелика, тем более что они часто делают необходимым
использование существенно более сложных эвристических методов, по
сравнению с указанными выше методиками общего назначения. При
индексировании используются заранее установленные схемы присвоения
индексов, описывающих состояние задачи, а также задающих процесс
запоминания правил, применяемых к каждому из состояний задачи (при этом
требуется, чтобы эти правила могли быть связаны с индексом данного
состояния). Из области хранения данных об определенном состоянии задачи
впоследствии можно вызвать индекс этого состояния, что в свою очередь
позволяет вызвать все правила, которые могли быть использованы. Более
привлекательной выглядит операция факторизации. Если база знаний может
быть разделена на большие множества данных, мало пересекающиеся между
собой, то при рассмотрении соответствующей информации о проблемной
области целые секции могут быть исключены. Например, если рассматриваемый
вопрос связан с диагностикой легочных заболеваний, то для системы не
требуется поиск части ее базы знаний, связанной с процедурами при
проведении реальных хирургических операций на легком. Ограничение поиска
также может быть достигнуто с помощью метода сопоставления с образцом,
аналогичного традиционным задачам сравнения, где операция сопоставления
используется для проверки того, что были найдены правильная форма, слово
и т. д. Сопоставление с образцом часто используется в задачах
распознавания речи, понимания естественного языка, распознавания образов;
все они будут обсуждаться в разд. 10.3.
Можно ввести количественные коэффициенты, описывающие процесс ограничения
поиска, с этой целью используют эвристические или оценочные функции
определенных видов. Как показано на рис. 10.6, этот случай относят к
классу эвристики частного назначения. Эвристическая функция дает значения
весового или стоимостного коэффициента для каждой из вершин, что служит в
определенной степени мерой "качества" пути достижения решения вплоть до
данной вершины. Для различных проблемных областей будут иметься разные
возможности для реализации таких функций, отсюда и появляется термин
"частного назначения". Наиболее часто применяются концепции измерения
качества пути, основанные на метрических представле-
288 Часть IV. Символьные вычисления и искусственный интеллект
ниях расстояния до вершины или степени трудности поиска цели, а также
выражаемые разностью путей между текущей вершиной и вершиной цели. Как
уже упомянуто выше, в любом случае приходится искать компромисс между
возможной экономией времени поиска, достигаемой за счет применения
эвристических функций, и затратами времени на вычисления самих функций;
т. е. сложные функции могут обеспечить прекрасное управление процессом
поиска, но время, необходимое для их вычисления, может быть больше, чем
время, которое потребовалось бы для реализации случайной процедуры
поиска.
Если задана функция меры качества, описывающая пути поиска решения, то
процесс поиска может проводиться по методу "первого наилучшего". Согласно
данной методике, в качестве вершин, из которых предстоит расширить поиск
цели, выбирают вершины, обладающие наилучшей мерой качества. Например,
можно считать, что числа, записанные рядом с каждой из вершин на рис.
10.8, представляют собой значения эвристической функции, так что чем
меньше соответствующее число, тем целесообразнее продолжить поиск именно
из этой вершины. Соответственно поиск по методу "первого наилучшего"
будет происходить следующим образом:
ACGHBDKEFIJL.
10.2.4. Сравнительные характеристики символьных и цифровых вычислений
Надеемся, что читатель уже получил общее представление о том, что
составляет суть символьных вычислений. Уровень понимания данного вопроса
еще более углубится, если провести сравнение возможностей символьных
вычислений и более известных цифровых. На рис. 10.9 для удобства в двух
колонках приведен перечень их свойств, так что сравнение можно провести
достаточно наглядно. Результаты сравнения обсуждаются ниже.
