Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ
Посмотреть оригинал

ЭКСПОНЕНЦИАЛЬНАЯ СЛОЖНОСТЬ ПОИСКА НА ДЕРЕВЕ РЕШЕНИЙ И МЕТОДЫ ЕЕ РЕДУЦИРОВАНИЯ

В результате освоения данной главы обучающийся будет:

знать

• методологические принципы применения антропоморфных методов в искусственном интеллекте;

уметь

• применять полученные знания о методах редуцирования дерева решений к практическим ситуациям;

владеть

• современными технологиями сокращения размерности пространства поиска в базах знаний большого размера.

Наивный логический поиск и задачи реального мира

Модель наивного логического вывода

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

Логический вывод из правила, состоящего из условий, составленных триплетами «субъект — предикат — объект» вида с (х,-, pjy г/,), представляет собой решение системы уравнений с количеством неизвестных, равным числу переменных в правиле. Одну часть уравнений образуют пары х,-=уг если переменная используется более чем в одном условии правила, вторую — уравнения х, = значение, г/, = значение, получаемые подстановкой в условия правила подходящих фактов / = (s, р, о). Наивный вывод состоит из следующих шагов.

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

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

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы