Решение задачи эйнштейна на основе

on

Определим фреймовую модель представления знаний следующим образом: 65535знание организовано в виде совокупности взаимосвязанных описаний — классов данной предметной области; 65536формальная структура для такого описания названа фреймом. Это дает возможность упаковать знания в структуры, организованные подходящим образом, сохраняя их обозримость на всех уровнях; 65537 фреймы организуются в иерархии по уровню абстракции; конкретным объектам соответствуют экземпляры фреймов; свойства общих понятий наследуются конкретным понятием в иерархии. Наследование представляет собой особый вид дедукции, что дает выигрыш в эффективности и, что более важно, облегчает построение системы фреймов — базы знаний. Такие описания выглядят гораздо более близкими к мыслительным структурам человека, нежели формализмы типа исчисления предикатов; 65538структурное описание предполагает содержание ссылок на другие фреймы, что позволяет описывать различные отношения между понятиями данной предметной области. Указанные ссылки могут иметь вид фрейма — прототипа со значениями его свойств-слотов. Сопоставление с прототипом также является механизмом, частично заменяющим обычную дедукцию, в то же время более адекватным механизму мышления человека; с фреймами связываются процедуры, описывающие те или иные специализированные для данной предметной области процессы (проблемно-логический подход, поддержка целостности базы знаний, учет взаимосвязей экземпляров различных понятий и т.п.). Таким образом, фрейм представляет собой декларативно-процедурный модуль, включающий собственно предметную область, а также дополнительную информацию о способе его интерпретации. Между различными концептуальными объектами существуют некоторые аналогии, в результате чего и фреймы, представляющие такие образы, выстраиваются в иерархическую систему с классификационными и обобщающими свойствами. При этом сложные объекты представляются комбинацией нескольких фреймов (вложенными фреймами). Свойством сети фреймов, заимствованным из семантических сетей, является наличие AKO-связей («A-Kind-Of»), которые связывают фреймы с фреймами, находящимися на уровень выше в иерархии, откуда неявно наследуются (переносятся) значения слотов. Каждый фрейм имеет уникальное имя (идентификатор) в пределах системы фреймов. ЧЕЛОВЕК AKOМлекопитающее УМЕЕТМыслить ЛЕКТОРЛЕКТОР AKOЧеловек ОБРАЗОВАНИЕВысшее ВОЗРАСТ23-60 Рис 1. Фрагмент иерархии «человек — лектор» В данном случае представлено одно звено иерархии (ЧЕЛОВЕК-ЛЕКТОР). Здесь фрейм «ЧЕЛОВЕК» является обобщающим для фрейма «ЛЕКТОР». Таким образом, фрейм «ЛЕКТОР» наследует от фрейма «ЧЕЛОВЕК» значение слота «УМЕЕТ» (а также других слотов, не показанных в примере). Цепочка наследования может быть продолжена вплоть до, например, фрейма «ЖИВОЕ СУЩЕСТВО». Такая структура позволяет систематизировать большой объем информации, оставляя ее при этом максимально удобной для использования. Кроме того, система фреймов способна отражать концептуальную основу организации памяти человека. Рассмотрим реализацию фреймовой модели представления знаний на примере решения задачи Эйнштейна. Условия задачи следующие: 1. . Есть пять домов, каждый разного цвета. 2. . В каждом доме живет один человек, отличающийся от соседа по национальности: немец, англичанин, швед, датчанин, норвежец. 3. Каждый пьет только один напиток, выращивает определенное растение и держит определенное животное. 4. Никто из 5 человек не пьет одинаковые напитки, не выращивает одинаковое растение и не держит одинаковое животное. Цель решения: определить, кому принадлежит рыба? При этом дополнительные условия следующие: 1. . Англичанин живет в красном доме. 2. . Швед держит собаку. 3. Датчанин пьет чай. 4. Зеленый дом стоит слева от белого. 5. Жилец зеленого дома пьет кофе. 6. . Человек, который выращивает ячмень, держит птицу. 7. . Жилец из среднего дома пьет молоко. 8. . Жилец из желтого дома выращивает томаты. 9. . Норвежец живет в первом доме. 10. . Тот, кто держит кошку, живет около того, кто выращивает свеклу. 11. . Человек, который содержит лошадь, живет около того, кто выращивает томаты. 12. . Тот, кто выращивает пшеницу, пьет сок. 13. . Норвежец живет около голубого дома. 14. Немец выращивает капусту. 15. . Тот, кто выращивает свеклу, живет по соседству с человеком, который пьет воду. Если трактовать условие 4 как «зеленый дом стоит непосредственно слева от белого», то задача имеет единственное решение. Причем под решением в данном случае понимается не только определение того, кому принадлежит рыба, но и полное распределение дом — человек — напиток — растение — животное, охватывающее все описанные в условии объекты. Попробуем представить предметную область задачи с помощью набора фреймов. В условии фигурируют объекты 5 классов: «дом», «человек», «напиток», «растение» и «животное». Каждому классу принадлежит 5 объектов. Таким образом, наиболее логичным решением в данном случае будет создание для каждого класса абстрактного фрейма, описывающего этот класс, а для каждого объекта, принадлежащего классу — конкретного фрейма, наследуемого от абстрактного и описывающего этот объект. На рис. 2 представлены фреймовые диаграммы классов «Дом» и «Человек». Диаграммы классов «Напиток», «Растение» и «Животное» не показаны, поскольку представляющие их фреймы достаточно тривиальны (не содержат ни одного слота). ШШШ У ШШ ДОМ Цвет Позиция ЖилецСсылка на фрейм ЧЕЛОВЕК ЧЕЛОВЕК Национальность ДомСсылка на фрейм ДОМ НапитокСсылка на фрейм НАПИТОК РастениеСсылка на фрейм РАСТЕНИЕ ЖивотноеСсылка на фрейм ЖИВОТНОЕ КРАСНЫЙ ДОМ АКОДОМ ЦветКрасный ЗЕЛЕНЫЙ ДОМ АКОДОМ ЦветЗеленый БЕЛЫЙ ДОМ АКО ДОМ Цвет Белый ЖЕЛТЫЙ ДОМ АКОДОМ ЦветЖелтый ГОЛУБОЙ ДОМ АКОДОМ ЦветГолубой АНГЛИЧАНИН АКОЧЕЛОВЕК НациональностьАнгличанин ДомКрасный ШВЕД АКОЧЕЛОВЕК НациональностьШвед ЖивотноеСобака ДАТЧАНИН АКОЧЕЛОВЕК НациональностьДатчанин НапитокЧай НОРВЕЖЕЦ АКОЧЕЛОВЕК НациональностьНорвежецНЕМЕЦ АКОЧЕЛОВЕК НациональностьНемец РастениеКапуста ссов «Дом» и «Человек» Диаграмма на рис. 2 показывает, что фреймы, представляющие конкретные объекты, наследуют слоты абстрактных фреймов, определяя значения для некоторых из них. Таким образом, часть информации, содержащейся в условии задачи, задается с помощью значений слотов. Данная информация носит декларативный характер, поскольку задается на этапе построения модели и не требует дополнительных проверок. Другая часть информации может быть заложена в модель с помощью процедур, задаваемых для фрейма и вызываемых при изменении значения его слотов. Эта информация носит характер проверяемых условий. Например, условие «жилец желтого дома выращивает томаты» может быть проверено процедурой, вызываемой при изменении значения слота «РАСТЕНИЕ» фрейма «ЖЕЛТЫЙ ДОМ». Сложнее обстоит дело с условиями типа «тот, кто держит кошку, живет около того, кто выращивает свеклу». Для проверки таких условий каждый дом должен располагать информацией о соседних домах и их обитателях. В программе, которая будет рассмотрена ниже, связь домов друг с другом реализована путем введения списка домов, учитывающего их расстановку, причем каждый «дом» имеет доступ к этому списку. Фреймовая модель очень удобна с точки зрения программной реализации, поскольку она напрямую соответствует парадигме объектно-ориентированного программирования. С точки зрения ООП, фреймы представляют собой не что иное, как классы. Слоты являются аналогом полей классов. Иерархия фреймов соответствует иерархии классов, которая строится с помощью механизма наследования. Процедуры фреймов, выполняемые при определенных условиях, можно реализовать с помощью обработчиков соответствующих событий, определенных для полей классов. Горизонтальные связи реализуются путем добавления в класс ссылок на объекты других классов, с которыми планируется взаимодействие. На рис. 3 представлена диаграмма классов, реализующих фреймовую модель предметной области (далее просто «Модель»). Ключевыми являются классы «House» и «Man», от которых наследуются классы, описывающие уже конкретные дома и конкретных людей. Классы, представляющие напитки, растения и животных, в силу своей тривиальности реализованы в виде перечислений. Программный модуль состоит из двух основных частей: набора классов, реализующих фреймовую модель, и внешнего модуля, который осуществляет генерацию наборов данных, наблюдением за «реакцией» модели и принятием необходимых решений. Вся предметная область разбита на 5 уровней: 1) уровень домов -» 2) уровень людей — 3) уровень напитков — 4) уровень растений — 5) уровень животных. Такой порядок следования уровней означает, что сначала определяется позиция дома, затем — его жилец, после чего для жильца определяются его напиток, растение и животное. В общем случае порядок уровней не играет решающей роли, но для конкретной реализации он должен быть фиксирован. Программа действует методом проб и ошибок. На самом верхнем уровне генерируется перестановка домов. Каждому дому присваеваются позиция, соответствующая его номеру в перестановке. При этом программа наблюдает за «реакцией» модели. Допустим, что в перестановке зеленый дом оказался справа от белого (по условию, зеленый дом стоит слева от белого). При присвоении зеленому дому его позиции он проверит, где в данный момент находится белый дом. Если позиция белого дома уже определена и он не стоит слева от зеленого, объект, представляющий зеленый дом, выбросит исключение, сигнализирующее о том, что произошел конфликт с условием задачи. Внешняя программа перехватит исключение, произведет откат перестановки на текущем уровне (обнулит позиции всех домов) и перейдет к генерации следующей перестановки. Если же текущая перестановка не вызвала конфликта условий, программа спустится на уровень ниже. На следующем уровне генерируется перестановка людей. После генерации каждому человеку присваивается дом из текущей перестановки домов, номер которого соответствует номеру данного человека в перестановке людей. При этом модель автоматически присваивает значения определенным атрибутам объектов в соотве ствии с условиями задачи. Допустим, внешняя программа пытается «поселить» датчанина в желтый дом, стоящий на позиции «3». Объект, представляющий датчанина, проверяет позицию желтого дома и, обнаругМдФгЖ у 9801 жив, что дом стоит посередине, присваивает атрибуту «напиток» значение «молоко», т.к. по условию жилец из среднего дома пьет молоко. При этом этот же объект проверяет, не связано ли молоко с каким-либо другим человеком. Если оказывается, что молоко уже используется для кого-то в качестве напитка, генерируется исключение. Модель самостоятельно проверяет соблюдение всех условий задачи. Внешней программе остается лишь генерировать перестановки и следить за реакцией модели. Как было описано выше, в случае, если очередная перестановка не вызвала конфликта с условиями задачи, программа спускается на уровень ниже и начинает генерацию на более низком уровне. Если же ни одна из перестановок на текущем уровне не дала положительного результата, программа возвращается на предыдущий уровень и продолжает генерацию на более высоком уровне. Таким образом, задача решается методом перебора всех возможных вариантов. С одной стороны, решение полным перебором требует в общем случае наибольших временных затрат среди существующих методов решения. С другой стороны, осуществление полного перебора гарантирует единственность решения задачи (а если решений несколько — позволяет найти их все). На рис. 4 показана