Камерон Хьюз - Параллельное и распределенное программирование на С++

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

вопросы события

факты вре м я

предположения заблуждения

убеждения цель

утверждени я обоснование

заключения

Безусловно, с когнитивными структурами данных можно сочетать и другие типы данных, но приведенные выше являются характеристиками программ, которые используют такие рациональные программные компоненты, как агенты. Эти абстрактные типы обычно реализуются как типы данных, объявленные с помощью ключевых слов structили class.Напри м ер, так.

struct question{

class justification{

//...

//...

string RequiredInformation;

time EventTime;

target_object QuestionDomain;

bool Observed;

string Tense;

bool Present;

string Mood;

//...

//... };

};

Шаблонные и контейнерные С++-классы можно использовать для организации таких когнитивных структур данных, как знания, например, так.

class preliminary_knowledge{ //.. .

map Opinion;

map SimpleKnowledge;

set Argument; //.- .

};

Под методами рассуждений (см. рис. 12.1) пони м ают дедукцию, индукцию и абдукцию. (Краткое описание этих методов приведено в параграфе 12.1.) Несмотря на то что в агентно-ориентированной архитектуре требуется их использование, не существует конкретных ссылок на то, как они реализуются. Делукция, индукция и абдукция относятся к процессам высокого уровня. Подробности реализации этих процессов — личное дело разработчика ПО. Рассуждение — это процесс выведения логического заключения на основании посылок, истинность которых предполагается или точно установлена. Не существует единственно правильного способа реализации процесса рассуждений, ино г да называе м о г о машиной (и л и м еха н из м о м) логического вывода. При этом на практике приме н яется н еско л ько распростра н е н ных способов реализации это г о процесса. Напри м ер, можно испо л ьзовать методы прямого построения цепочки (рассуждений от исходных посылок к целевой гипотезе) или обратного построения цепочки (рассуждений от целевой гипотезы к исходным посылкам). Нашли здесь применение методы анализа целей и средств, а также такие алгоритмы обхода графов, как «поиск вглубь» (Depth First Search — DFS) и «поиск в ширину» (Breadth First Search — BFS). Существует также целал совокупность методов доказательства теорем, которые можно использовать для реализации методов рассуждений и механизмов логического вывода. Здесь важно отметить, что класс агента может иметь один или несколько методов рассуждений. Описание самых основных способов их реализации приведено в табл. 12.3.

Таблица 12.3. Основные способы реализации методов рассуждений

Обратное построение цепочки Управляемый целями метод, в котором процесс начинается с предположения, утверждения или гипотезы и стремится найти подтверждающие доказательства

Прямое построение цепочки Управляемый данными метод, который начинается с анализа имею щ ихся данных или фактов и приходит к определенным выводам

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

Эти методы достаточно понятны и широко доступны во многих библиотеках, оболочках и языках программирования. Эти методы являются «строительными блоками» для базовых методов рассуждений. Чтобы понять, как происходит процесс рассуждения, используем одно из правил генерирования вывода, а именно молус поненс (правило отделения), и построим простой метод рассуждения. Возьмем следующее утверждение. Если существует автобусный маршрут из Детройта в Нью-Йорк, то Джон поедет в отпуск. Если мы выясним, что автобусный маршрут из Детройта в Нью-Йорк действительно существует, то будем знать, что Джон поедет в отпуск. Правило молус поненс имеет следующий формат.

P Q P

Q

Здесь:

P = Если су щ ествует автобусный маршрут из Детройта в Нью-Йорк, Q = Джон поедет в отпуск.

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

Толедо-Кливленд Детройт-Чикаго Янгстаун-Нью-Йорк

Кливленд-Колумбус Цинциннати-Детройт Детройт-Толедо

Колумбус-Нью-Йорк Цинциннати-Янгстаун

Каждый из этих маршрутов представляет обязательство, взятое на себя компанией ABC Bus Company. Если наш агент получит доступ к расписанию автобусных маршрутов этой компании, то приведенный выше список маршрутов можно будет использовать для представления некоторой части убеждений нашего агента. Возникает вопрос: как перейти от списка маршрутов к убеждениям? Для начала попробуем разработать простую структуру утверждений.

struct existing_trip{

//. . .

string From;

time Departure;

string То;

time Arrival;

//.. .

};

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

set BusTripKnowledge ;

Если определенный автобусный маршрут содержится в множестве BusTripKnowledge, то наш агент убежден в том, что в указанное время автобус непременно отправится по этому маршруту из пункта отправления в пункт назначения. Итак, мы можем зафиксировать любой маршрут в соответствии с заданной структурой.

//...

existing__trip Trip;

Trip. From. append (" Toledo " ) ;

Trip.To.append( «Cleveland») ;

Trip.Departure(«4:3 О») ;

Trip.Arrival(«5:45») ;

BusTripKnowledge. insert(Trip) ;

//...

Если мы поместим каждый маршрут в множество BusTripKnowledge,то убеждения нашего агента об автобусных перевозках компании ABC Bus Company будут полностью описаны. Обратите внимание на то, что прямого маршрута из Детройта в Нью-Йорк не существует. Но Джон может добраться в Нью-Йорк из Детройта более сложным путем, осуществив следующие переезды автобусом:

из Детройта в Толедо; из Толедо в Кливленд; из Кливленда в Кол^мбус; из Колумбуса Нью-Йорк.

Поэтому, несмотря на то, что компания ABC Bus Company не предоставляет прямого маршрута (из пункта А в пункт Б), она позволяет совершить переезд с большим количеством промежуточных остановок. Задача состоит в следую щ ем: как об этом может узнать наш агент? Агент на основе своих знаний об автобусных маршрутах должен обладать некоторым алгоритмом генерирования вывода о том, су щ ествует ли маршрут из Детройта в Нью-Йорк. Мы используем простой цепной метод. Просматриваем элементы множества BusTripKnowledgeи находим первый маршрут из Детройта— из Детройта в Чикаго. Опрашиваем атрибут Тоэтого элемента. Если бы он был равен значению «Нью-Йорк», процесс поиска был бы прекращен, поскольку мы нашли нужный маршрут. В противном случае сохраняем найденный (промежуточный) маршрут в стеке. Затем ищем маршрут с атрибутом From,равным «Чикаго».При этом может оказаться, что таких маршрутов не прелусмотрено вообще. Поскольку далее хранить элемент множества, соответствующий маршруту «Детройт-Чикаго», нет никакого смысла, мы удаляем его из стека, сделав пометку, что этот маршрут уже был рассмотрен. Затем повторяем поиск маршрута с отправлением из Детройта. Находим такой маршрут: «Детройт-Толедо». Проверяем, не равен ли его атрибут Тозначению «Нью-Йорк»,и поскольку наши надежды не оправдались, сохраняем этот элемент в стеке. Затем ищем маршрут с атрибутом From,равным «Толедо».Находим маршрут «Толедо-Кливленд» и также помещаем его на хранение в стек. После этог опросматриваем маршруты в надежде найти элемент, у которого атрибут Fromбыл бы равен значению «Кливленд».Для каждого найденного маршрута проверяем значение атрибута То.Если он равен значению " Нью-Йорк», то промежуточные маршруты, помещенные в стек, представляют в целом маршрут из Детройта в Нью-Йорк, начало которого находится на «дне» стека, а его конечный пункт — в вершине. Если мы пройдем по всему списку маршрутов и не найдем ни одного с атрибутом То,равным значению «Нью-Йорк»,или иссякнут возможные варианты проверки атрибута То дляверхнего элемента стека, то мы, извлекал верхний элемент из стека, будем искать следующий элемент, значение атрибута Fromкоторого совпадает со значением атрибута Тоэлемента, расположенного в вершине стека. Этот процесс повторяется до тех пор, пока стек не опустеет или мы все-таки не най дем нужный маршрут. Для определения, существует ли маршрут из пункта А в пункт Б, используется в данном случае упрощ енный метод DFS (Depth First Search — «поиск вглубь»).