Costas-Tyros_rus_MS

RefNumber), ChainDB:key_insert(BTREE, Key, RefNumber).

insert_info( _, _, _).

База данных это наполняющаяся система. Как любая наполняющаяся система, она имеет два компонента: цепь папок, каждая содержит данные, которые необходимо хранить; и алфавитный спи сок, который указывает на различные папки и позволяет потенциальному пользователю узнать, где хранится желаемая информация. В примере базы данных, цепь папок называется Contacts; каждая папка имеет следующую форму: email(string, string, string). Первый аргумент email хранит название контакта, второй содержит электронное письмо, и третий информирует о типе контакта, имеющимся с ассоциированным с этой записью базы данных объектом.

Предикат chain_insertz сохраняет папку в цепь Contacts и возвращает RefNumber на его место положение. RefNumber будет сохранён в алфавитном порядке в BTree.

Чтобы найти электронное письмо Contact, соответствующее заданному Name, ищут в BTree, для того, чтобы найти ссылку; обладая номером ссылки, получить папку просто.

data_base_search(Name, Contact, Tipo) : dbase(ChainDB, BTREE), ChainDB:key_search(BTREE, Name, Ref),

ChainDB:ref_term(Ref, Term),

Term= email(Name, Contact, Tipo), !. data_base_search(_Name, "none", "none").

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

141

Глава 22: Книги и статьи

В этой главе я поговорю о некоторых книгах по Прологу и техникам программирования. Вы заме тите, что книги несколько стары, и больше не печатаются. Одна причина этого в том, что люди не по купают техническую литературу так часто, как раньше, так как большинство студентов надеются по лучить материал вроде этого руководства из интернета. Другая причина в том, что многие великие компьютерные учёные были увлечены Прологом в восьмидесятые и девяностые. Эти учёные написа ли книги, которые сложно переплюнуть. Например, я не могу найти современной книги, которая бы приблизилась к [Coelho/Cotta].

22.1.Грамматика

Пролог превосходен в обработке языков, написании компиляторов и подготовке документов. Фактически, этот язык был изобретён с расчётом на обработку естественных языков. Большинство книг работают со стандартным Прологом, который несколько отличается от Visual Prolog. В то время как стандартный Пролог был разработан для быстрых прототипов маленьких приложений и для про

верки идей, Visual Prolog используется в крупных коммерческих и промышленных критических сис темах. Веллесли Баррос (Wellesley Barros), например, разработал и запрограммировал в Visual Prolog

крупную систему для администрирования госпиталя. Будьте уверены, что в подобной системе нельзя позволить себе аварии из за ошибок типа. В критических ситуациях, проверки и объявления типов очень важны. В любом случае, несмотря на то, что вы программируете в Visual Prolog, вы можете из влечь пользу из идей, представленных в книгах, основанных на стандартном Прологе. Старая книга, которую вы можете найти в вашей местной библиотеке, была написана аргентинским ученым Веро

никой Дал (Veronica Dahl) (см. [Abramson/Dahl]), одной из величайших современных лингвистов. Доктор Седрик де Карвало (Cedric de Carvalho) написал компилятор Пролога, который генерирует

байт код Java. Этот компилятор позволит вам писать в Прологе апплеты. Его компилятор ещё не до конца встал на ноги, но вы легко можете его усовершенствовать. Между тем, вы многое изучите о компиляции, грамматическом разборе, Java, и т. д. Вы можете начать читать статьи Седрика в [Cedric et all]. Вы также можете портировать компилятор, написанный в Visual Prolog 5.2, в Visual Prolog 6.2. Адрес:

http://netProlog.pdc.dk

Другая книга по обработке естественных языков со множеством интересных подходов к грамма тическому формализму это [Pereira/Shieber]. Эта книга более дидактична, чем [Abramson/Dahl]. На самом деле, [Abramson/Dahl] написана для специалистов, а [Pereira/Shieber] говорит со студентами, которые ещё только учатся сложному искусству обработки языков. Книга, не специализирующаяся на обработке естественных языков, но дающая хорошее введение в неё, это [Sterling and Shapiro]. Если вы хотите иметь продвинутую книгу по этой теме, хорошим выбором является книга [Gazdar/Mellish].

22.2.Базыданных

Дэвид Уоррен (David Warren), компьютерный учёный, является главным сторонником использо вания Пролога как движка для баз данных. Книга [Warren] больше не печатается, но вы должны дос тать копию с рук, если вы хотите изучать базы данных. Она классическая.

Дэвид Уоррен руководит командой, разрабатывающей XSB – Пролог, ориентированный на базы данных, в Stony Brook University. Хотя я не думаю, что эта версия Пролога используема для серьёзных приложений, так как она полагается на иные инструменты для построения GUI, не компилируется (написать красивое приложение в XSB нелегко), и не типизирована, я очень рекомендую посетить страницу XSB. Там вы найдёте множество хороших идей о базах данных и Прологе, и инструментах для их разработки. Адрес

http://www.cs.sunysb.edu/~sbProlog/xsb page.html

142

Между прочим, XSB предлагает набор инструментов для экспорта его функциональности в дру гие языки. Таким образом, если вам нравятся его особенности, вы можете вызвать DLL на языке XSB из Visual Prolog! Страница XSB показывает, как вызвать DLL из Visual Basic. Вы можете использовать тот же подход, чтобы вызвать её из Visual Prolog.

22.3.Техникипрограммирования

Если вам было сложно разбираться с такими понятиями, как рекурсивное программирование,

операции со списками, отсечения, недетерминированное программирование и parsing – грамматиче­ ский разбор/парсинг – вам надо прочитать книгу The Art of Пролог (см. [Sterling and Shapiro]). Идеи,

представленные в этой книге, легко могут быть перенесены в Visual Prolog. В Visual Prolog вы даже можете улучшить оригинальные программы. Например, один из моих студентов сумел создать диа граммы для электрических цепей, описанных в главе 2 [Sterling and Shapiro].

Моя самая любимая книга по Пролог это Prolog by Example, [Coelho/Cotta]. Это вроде FAQ: авторы ставят проблему и показывают решение. Это также антология. Проблемы и решения были предло жены и решены великими компьютерными учёными. Эта книга заслуживает нового издания. Попы тайтесь, (и очень сильно!), достать копию с рук. Если вы не можете получить копию, попросите раз решения авторов и сделайте ксерокопию.

143

Часть II

Искусственный Интеллект

144

Глава 23: Поиск

Патрик Генри Уинстон (Patrick Henry Winston), автор очень известной книги о языке LISP, начал своё исследование искусственного интеллекта с поиска, утверждая, что поиск вещь повсеместная. Точнее не скажешь. На самом деле: всё, от планирования движений роботов до нейросетей, может быть сведено к поиску. Значит, давайте, подобно Уинстону, начнём своё изучение искусственного интеллекта с поиска.

23.1.Состояния

Применительно к искусственному интеллекту, выражение problem solving – решение проблем относится к анализу того, как компьютеры могут использовать поиск для решения проблем в чётко определённых доменах. Один вопрос поднимается из этого определения: Что интеллектуальная про грамма проверяет в своём поиске решения проблемыы? Она проверяет лабиринт состояний, соеди нённых операторами, которые приводят к изменению особенностей.

У объекта есть состояния, то есть набор особенностей, который определяет его положение в данный момент. Например, Евклид определял точку как сущность, имеющую лишь одну особенность

– местоположение. Следовательно, состояние точечного объекта задаётся его координатами. Одна ко, обычно для определения состояния объекта используютя и другие особенности, кроме местопо ложения:

Цвет: Красный, зелёный, синий, и т. д.

Целостность сообщает, является ли объект целым или неоправленным. Позиция задаёт направление, в котором повёрнут объект. Сохранность говорит о том, защищён ли объект от разрушения.

Каждая особенность имеет один или несколько атрибутов, а также значений этих атрибутов. На пример, местоположение имеет три атрибута, которые являются координатами точки; в двухмерном пространстве атрибуты местоположения могут иметь значения декартова произведения ; сле довательно, кортеж (50, 200) задаёт верные значения для местоположения. Если короче, то можно сказать, что состояние – это запечатление в некий момент времени. Каждый атрибут, который можно изменять для решения проблемы, называется степенью свободы. Значит, точка в трёхмерном про странстве имеет три степени свободы.

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

23.2.Дерево поиска

Дерево поиска – это распространённая диаграмма, на которой каждое состояние изображается помеченным узлом (идентификатор внутри круга), а каждый возможный переход из одного состоя ния в другое описан веткой инвертированного дерева. На рис. 23.1 вы можете увидеть изображение дерева поиска.

На рис. 23.1, узлы b, c, d, t, f, g, h, i, j, k и m являются состояниями, через которые может пройти объект. Ветки, соединяющие два узла, это операторы, которые вызывают переход из одного состоя ния в другое. Например, ветка под номером 3 на рис. 23.1 – это оператор, который вызывает изме нения состояния b в e. Когда узел X может быть достигнут из другого узла Y использованием только одного оператора, говорят, что X – дочь Y, или что Y – мать X. Таким образом, узел с является доче рью b, так как c можно достичь, используя оператор 1. Когда у узла нет дочери, он называется лист ком.

Более конкретный пример поможет вам понять идеи, которые мы изучили выше. Две чёрных фишки, наподобие тех, что используются в шашках, и две белых фишки разложены так, как показано на рисунке. Чёрные фишки отделены от белых пустым местом. Нужно расположить чёрные фишки

145

между белых. Доступны два оператора: (1) Подвинуть фишку на пустое место и (2) перепрыгнуть че рез фишку на пустое место. Рисунок справа показывает пошаговое решение этой проблемы.

Взадаче, которую мы хотим решить, интересующие нас объекты ограничены четырьма фишками

ипустым местом. Относительные позиции фишек и пустого места определяют состояние. Начальное состояние E1 показано в верхней части рисунка. Цель E5 находится в нижней части рисунка.

Рисунок 23.1 Дерево поиска

Рисунок 23.2 Головоломка

На рис. 23.2 вы можете увидеть дерево поиска для вышеописанной головоломки. Можно ска зать, что состояния подобны городам на карте, а операторы подобны дорогам, соединяющим горо да. Задача решена, когда найден путь, ведущий от корня к цели, и самый очевидный способ найти путь – это ходить от города к городу, пока не будет найден путь, соответствующий цели. Этот процесс называется поиском.

146

23.3.Поиск вширину1

Поиск называется исчерпывающим, если он гарантирует создание всех достижимых состояний до того, как завершиться с неудачей. Один из способов совершить исчерпывающий поиск – это гене рировать все узлы на определённом уровне до того, как продвигаться к следующему уровню дерева; этот метод называется поиском в ширину, и удостоверяет, что пространство возможных операций будет систематически рассмотрено.

На дереве на рис. 23.1 поиск начинается с рассмотрения секции (c d e), содержащей узлы, рас положенные на расстоянии одной ветки от корня. Затем переходят к секции (f g h i j), располо женной на расстоянии двух веток от корня. Наконец, механизм поиска посещает секцию (k m). Про грамма, совершающая операцию поиска, обладает параметром, называемом очередь, содержащим список предполагаемых путей. Каждый путь представлем в виде списка узлов, где узел имеет вид r(integer, string).

implement main domains

node= r(integer, string). path= node*.

queue= path*.

class facts

operator:(integer, string, string).

class predicates

bSearch:(queue, path) determ (i, o). nextLevel:(path, path) nondeterm (i, o). solved:(path) determ. prtSolution:(path).

clauses

classInfo("main", "breath"). solved(L) : L= [r(_, "k")|_].

prtSolution(L) :

foreach P= list::getMember_nd(list::reverse(L)) do stdio::write(P), stdio::nl

end foreach.

operator(1, "b", "c"). operator(2, "b", "d"). operator(3, "b", "e"). operator(4, "c", "f"). operator(5, "c", "g"). operator(6, "c", "h"). operator(7, "e", "i"). operator(8, "e", "j"). operator(9, "g", "k"). operator(10, "g", "m").

bSearch([T|Queue],Solution) :

1 В оригинале заголовок главы выглядит как Breadth First Strategy. Это название этой стратегии поиска, употребляемое в англоязычной литературе по данной теме, насколько я могу судить. Я заменил на используемое в русскоязычной теории алгоритмов.

147

if solved(T) then Solution= T

else Extentions= [Daughter || nextLevel(T, Daughter)], ExtendedQueue= list::append(Queue, Extentions), bSearch(ExtendedQueue, Solution) end if.

nextLevel([r(Branch, N)|Path], [r(Op, Daughter),r(Branch, N)|Path]): operator(Op, N, Daughter),

not(list::isMember(r(Op, Daughter),Path)).

run(): console::init(),

if bSearch([[r(0, "b")]], L) then prtSolution(L) else stdio::write("No solution!"), stdio::nl end if.

end implement main /* breath*/ goal mainExe::run(main::run).

Изначально Queue содержит единственный путь, который начинается и заканчивается в корне:

bSearch([[r(0, "b")]], L)

Так как этот путь не ведёт к цели, он расширяется до каждой дочери “b”, и расширения дописы ваются в конец очереди:

bSearch([ [r(1, "c"),r(0, "b")], [r(2, "d"),r(0, "b")], [r(3, "e"),r(0, "b")]], L)

Пока что робот посетил только один узел, а именно “b”. Затем в конец очереди дописываются расширения узла “c”.

bSearch([ [r(2, "d"),r(0, "b")], [r(3, "e"),r(0, "b")],

[r(4, "f"),r(3, "c"),r(0, "b")], [r(5, "g"),r(3, "c"),r(0, "b")], [r(6, "h"),r(3, "c"),r(0, "b")]], L)

Узел “d” посещён, но, так как дочерей у него нет, он просто удаляется из очереди.

bSearch([ [r(3, "e"),r(0, "b")],

[r(4, "f"),r(3, "c"),r(0, "b")], [r(5, "g"),r(3, "c"),r(0, "b")], [r(6, "h"),r(3, "c"),r(0, "b")]], L)

Дочери “e” дописываются в конец очереди:

bSearch([ [r(4, "f"),r(3, "c"),r(0, "b")], [r(5, "g"),r(3, "c"),r(0, "b")], [r(6, "h"),r(3, "c"),r(0, "b")], [r(7, "i"), r(3, "e"),r(0, "b")], [r(8, "j"), r(3, "e"),r(0, "b")]], L)

Узел “f”, не имеющий продолжения, удаляется из очереди, а в её конец добавляются дочери

“g”.

bSearch([ [r(6, "h"),r(3, "c"),r(0, "b")], [r(7, "i"), r(3, "e"),r(0, "b")],

148

[r(8, "j"), r(3, "e"),r(0, "b")],

[r(9, "k"), r(5, "g"),r(3, "c"),r(0, "b")], [r(10, "m"), r(5, "g"),r(3, "c"),r(0, "b")]], L)

Узлы “h”, “i” и “j” по очереди посещены и удалены из Queue. Поиск заканчивается, когда алго ритм находит путь

[r(9, "k"), r(5, "g"),r(3, "c"),r(0, "b")]

Процедура

prtSolution(L) :

foreach P= list::getMember_nd(list::reverse(L)) do stdio::write(P), stdio::nl

end foreach.

разворачивает этот путь и распечатывает каждый его элемент. Конечный результат на экране приведён ниже.

r(0,"b")

r(1,"c")

r(5,"g")

r(9,"k")

D:\vipro\aityros\aiprogs\breath\Exe>pause Press any key to continue...

Теперь вы готовы попробовать применить алгоритм на настоящей задаче, например, в нашей го ловоломке.

implement slide domains

node= r(string, stt). path= node*.

queue= path*. piece= e;b;w.

stt= st(piece, piece, piece, piece, piece). class predicates

bSearch:(queue, path) determ (i, o). nextLevel:(path, path) nondeterm (i, o). solved:(path) determ. prtSolution:(path).

operator:(string, stt, stt) nondeterm (o, i, o). clauses

classInfo("breath", "1.0").

solved(L) : L= [r(_, st(w,b,b,w,e))|_]. prtSolution(L) :

foreach P= list::getMember_nd(list::reverse(L)) do stdio::write(P), stdio::nl

end foreach.

operator("slide", st(e,A,B,C,D), st(A,e,B,C,D)). operator("jump", st(e,A,B,C,D), st(B,A,e,C,D)). operator("slide", st(A,e,B,C,D), st(A,B,e,C,D)). operator("slide", st(A,e,B,C,D), st(e,A,B,C,D)). operator("jump", st(A,e,B,C,D), st(A,C,B,e,D)).

149

operator("slide",st(A,B,e,C,D),st(A,e,B,C,D)). operator("slide",st(A,B,e,C,D),st(A,B,C,e,D)). operator("jump",st(A,B,e,C,D),st(e,B,A,C,D)). operator("jump",st(A,B,e,C,D),st(A,B,D,C,e)). operator("slide",st(A,B,C,e,D),st(A,B,e,C,D)). operator("jump",st(A,B,C,e,D),st(A,e,C,B,D)). operator("slide",st(A,B,C,e,D),st(A,B,C,D,e)). operator("slide",st(A,B,C,D,e),st(A,B,C,e,D)). operator("jump",st(A,B,C,D,e),st(A,B,e,D,C)).

bSearch([T|Queue],Solution) :

if solved(T) then Solution= T

else Extentions= [Daughter || nextLevel(T, Daughter)], ExtendedQueue= list::append(Queue, Extentions), bSearch(ExtendedQueue, Solution) end if.

nextLevel([r(Branch, N)|Path], [r(Op, Daughter),r(Branch, N)|Path]) : operator(Op, N, Daughter),

not(list::isMember(r(Op, Daughter),Path)).

run(): console::init(),

if bSearch([[r("0", st(w,w,e,b,b))]], L) then prtSolution(L) else stdio::write("No solution!"), stdio::nl end if.

end implement slide

goal mainExe::run(slide::run).

Напечатанное компьютером решение головоломки приведено ниже.

r("0",st(w(),w(),e(),b(),b()))

r("slide",st(w(),e(),w(),b(),b()))

r("jump",st(w(),b(),w(),e(),b()))

r("slide",st(w(),b(),e(),w(),b()))

r("jump",st(w(),b(),b(),w(),e()))

D:\vipro\aityros\aiprogs\slide\Exe>pause

Pressione qualquer tecla para continuar. . .

23.4.Поисквглубину1

Проанализируйте рис. 23.1. Поиск в глубину, после посещения “b” перемещается к его левой до чери “c”. После посещения “c” он идёт к “f”. Только после посещения всех наследников “c” поиск в глубину посещает “g”. Чтобы реализовать эту стратегию, всё, что вам нужно сделать – это дописы вать потомка текущего узла в начало Queue, вместо дописывания его в конец. Вот единственная не обходимая модификация предыдущей программы:

dSearch([T|Queue],Solution) : if solved(T) then Solution= T

else Extentions= [Daughter || nextLevel(T, Daughter)], ExtendedQueue= list::append(Extentions, Queue), dSearch(ExtendedQueue, Solution) end if.

1Название этого раздела, так же, как и предыдущего, не является его переводом с английского оригинала.

Воригинале раздел 23.4 называется Depth First Strategy

150