Отличие
ЭС от других
программных
продуктов
Области
применения
экспертных
систем
Проблемы,
возникающие
при созданииЭС.
Перспективы
разработки
Критерий
пользователя
ЭС
Подсистема
вывода
Компонент
вывода
Диалог
с ЭС. Объяснение
Разработка
стратегии
Представление
задач в пространстве
состояний
Запись
в виде графа
Метод
равных цен
Изменение
при переборе
на произвольных
графах
Использование
других эвристик
Навигация
Представление задач в пространстве состояний
Экспертные системы. Классификация экспертных систем. Разработка простейшей экспертной системы
102315
знаков
3
таблицы
0
изображений
3.3. Представление задач в пространстве состояний
3.3.1. Описание состояний
Чтобы построить описание задачи с использованием пространства состояний, мы должны иметь определенное представление о том, что собой состояния в этой задаче. В игре в пятнадцать выбор в качестве состояний различных конфигураций из фишек достаточно очевиден. Но процесс решения задачи, в котором решение ищется без реального перемещения настоящих фишек, может работать лишь с описанием конфигураций, а не с самими конфигурациями. Таким образом важным этапом построения какого- либо описания задачи с использованием пространства состояний является выбор некоторой конкретной формы описания состояний этой задачи.
В сущности любая структура величин может быть использована для описания состояний. Это могут быть строки символов, векторы, двухмерные массивы, деревья и списки. Часто выбираемая форма описания имеет сходство с некоторым физическим свойством решаемой задачи. Так, в игре в пятнадцать естественной формой описания состояний может быть массив 4х4. Выбирая форму описания состояний, нужно позаботиться и о том, чтобы применение оператора, преобразующего одно описание в другое, оказалось бы достаточно легким.
3.3.2 Операторы. Состояния и операторы.
По-видимому самый прямолинейный подход при поиске решения для игры в пятнадцать состоит в попытке перепробовать различные ходы, пока не удастся получить целевую конфигурацию. Такого рода попытка по существу связана с поиском при помощи проб и ошибок. (Мы предполагаем, что такой поиск может быть выполнен в принципе, скажем, на некоторой вычислительной машине, а не с привлечением реальной игры в пятнадцать). Отправляясь от начальной конфигурации, мы могли бы построить все конфигурации, возникающие в результате выполнения каждого из возможных ходов, затем построить следующее множество конфигураций после применения следующего хода и т.д., пока не будет достигнута целевая конфигурация.
Для обсуждения такого сорта методов поиска решения оказывается полезным введение понятий состояний и операторов для данной задачи. Для игры в пятнадцать состояние задачи- это просто некоторое конкретное расположение фишек. Начальная и целевая конфигурации представляют собой соответственно начальное и целевое состояния. Пространство состояний, достижимых из начального состояния, состоит из всех тех конфигураций фишек, которые могут быть образованны в результате допустимых правилами перемещений фишек. Многие задач имеют чрезвычайно большие (если не бесконечные) пространства состояний.
Оператор преобразует одно состояние в другое. Игру в пятнадцать естественно всего интерпретировать как игру, имеющую четыре оператора, соответствующие следующим ходам: передвинуть пустую клетку (пробел) влево, вверх, вправо, вниз. В некоторых случаях оператор может оказаться неприложимым к какому- то состоянию. На языке состояний и операторов решение некоторой проблемы есть последовательность операторов, которая преобразует начальное состояние в целевое.
Пространство состояний, достижимых из данного начального состояния, полезно представлять себе в виде графа, вершины которого соответствуют этим состояниям. Вершины такого графа связаны между собой дугами, отвечающими операторам.
Про метод решения задач, основанный на понятиях состояний и операторов, можно было бы сказать, что это подход к задаче с точки зрения пространства состояний.
Операторы приводят одно состояние в другое. Таким образом, их можно рассматривать как функции, определенные на множестве состояний и принимающие значения из этого множества. Так как наши процессы решения задач основаны на работе с описанием состояний, то мы будем предполагать, что операторы- функций этих описаний, а их значения- новые описания. В общем случае мы будем предполагать, что операторы- это вычисления, преобразующие одни описания состояний в другие.
Во все наши процедуры исследования пространства состояний входит построение новых описаний состояний, исходя из старых с последующей проверкой новых описаний состояний, с тем чтобы убедиться, не описывают ли они состояние, отвечающее поставленной цели. Часто это просто проверка того, соответствует ли некоторое описание состояния данному целевому описанию состояния, но иногда должна быть произведена более сложная проверка. Например, для игры в пятнадцать целью может быть создание конфигурации из фишек, в которой в верхних двух рядах не будет фишек с номерами, превосходящими 12. Во всяком случае, то свойство, которому должно удовлетворять описание состояния, для того чтобы это состояние было целевым, должно быть охарактеризовано исчерпывающим образом.
В некоторых задачах оптимизации недостаточно найти любой путь, ведущий к цели, а необходимо найти путь, оптимизирующий некоторый критерий (например, минимизирующий число применений операторов). С такими задачами проще всего работать, сделав так, чтобы поиск не оканчивался до сих пор, пока не будет найдено некоторое оптимальное решение.
Таким образом, мы видим, что для полного представления задачи в пространстве состояний необходимо задать:
а) форму описания состояний и, в частности, описание начального состояния;
б) множество операторов и их воздействий на описания состояний;
в) свойства описания целевого состояния.
Пространство состояний полезно представлять себе в виде направленного графа.
Похожие работы
... охватывало бы вопросы воспитания, взаимодействия учителей с родителями учеников и самими учениками, вопросы самоподготовки желающих учиться учеников, помощи отстающим и т.п. 5. РАЗРАБОТКА ШКОЛЬНОЙ ИНФОРМАЦИОННОЙ СИСТЕМЫ (ШИС) НА ОСНОВЕ IT-ТЕХНОЛОГИЙ ДЛЯ МОУ СОШ № 97 Поставленные в предыдущем разделе задачи могут быть решены путем организации широчайшего (относительно родителей, учеников и ...
... основании вышеуказанных протоколов проводится окончательная оценка соответствия средства размещения определенной категории. Средства размещения определенной категории должны соответствовать: гостиницы, мотели и пр. с количеством номеров более 50: - требованиям, определенным в таблицах приложения к системе классификации; - критериям балльной оценки (табл. 2) с учетом следующего суммарного ...
... профессиональных знаний из экспертов и проектирование базы знаний экспертной системы и ее архитектуры. Программист необходим при разработке специализированного для данной экспертной системы программного обеспечения, когда подходящего стандартного (например, оболочки для создания экспертных систем) не существует или его возможностей не достаточно и требуются дополнительные модули. В процессе ...
... системы управления (АСУ); автоматизированные системы информационного обеспечения (АСИО). Рассмотрим каждый из перечисленных в классификации типов АИС подробнее. Под автоматизированной информационно-справочной системой (АИСС) в области права будем понимать автоматизированную информационную систему, предназначенную для сбора, систематизации, хранения и поиска правовой информации по запросам ...
0 комментариев