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

Текст из файла (страница 6)

continue(P,tr(B,F/G,[T1,TT]),Extr,Tree1,no,Is_solv,Solve):-

insert(T1,TT,NTT),

opt_f(NTT,F1),

propag(P,tr(B,F1/G,NTT),Extr,Tree1,Is_solv,Solve).

continue(P,tr(B,F/G,[T1,TT]),Extr,Tree1,never,Is_solv,Solve):-

opt_f(TT,F1),

propag(P,tr(B,F1/G,TT),Extr,Tree1,Is_solv,Solve).

suc_list(_,[],[]).

suc_list(G0,[B/C|BB],TT):-

G is G0+C,

h(B,H), % Эвристика h(B)

F is G+H,

suc_list(G0,BB,TT1),

insert(l(B,F/G),TT1,TT).

/**************************************************

*Вставка дерева Т в список деревьев ТТ с сохранением

* упорядоченности по f-оценкам

***************************************************/

insert(T,TT,[T|TT]):-

f(T,F),

opt_f(TT,F1),

F=<F1,!.

insert(T,[T1|TT],[T1|TT1]):-

insert(T,TT,TT1).

/******Проверка принадлежности элемента списку******/

member(X,[X|Q]).

member(X,[H|Q]):-member(X,Q).

/******* Получение f-оценки *********/

f(l(_,F/_),F). % f-оценка листа

f(tr(_,F/_,_),F). % f-оценка дерева

opt_f([T|_],F):- % наилучшая f-оценка для

f(T,F). % списка деревьев

opt_f([],Fmax):- % нет деревьев:

max_f(Fmax). % плохая f-оценка

min(X,Y,X):-

X=<Y,!.

min(X,Y,Y).

/********************************************************

* База фактов тестового примера:

* состояние дуг исходного графа after;

* функция h оценки удаленности вершин от целевой вершины;

* целевая вершина – goal;

* максимальное значение max_f(Fmax) оценки функции f

**********************************************************/

after(s,a,2). % База фактов:

after(s,e,2). % Исходный граф

after(a,b,2).

after(b,c,2).

after(c,d,3).

after(e,f,5).

after(f,g,2).

after(d,t,3).

after(g,t,2).

after(b,v,1). %Тупиковая вершина

goal(t). % Целевая вершина

h(a,5). % Значение эвристической

h(e,7). % функции h для оценки вершин

h(b,4).

h(f,4).

h(t,0).

h(d,3).

h(g,2).

h(c,4).

h(v,1).

max_f(20). % Макимальное значение f-оценки

% Пример запроса к программе%

?-evripoisk(s,Path).

Path=[t,g,f,e,s] ->;

Path=[t,d,c,b,a,s] ->;

no

/*********************************************************/

ЗАДАНИЕ. Написать и отладить программу эвристического поиска на графе. Проверить выполнение программы, используя трассировку.

П Р И Л О Ж Е Н И Е 1

1. КОМАНДЫ РЕДАКТОРА.

Редактор ARITY/PROLOG включает 9 рабочих буферов и один буфер обмена (Сlipboard). Переход из одного буфера в другой осуществляется с помощью функциональной клавиши F6 или с помощью опции Go to.(подменю Buffers). Кроме того, возможен переход из текущего буфера в предыдущий активный буфер с помощью функциональной клавишиF7 или с помощью опции Go to Last (подменю Buffers).

1.1. Движение курсора. "Стрелки" - движение на один символ влево/вправо или на одну строку вверх/вниз. Комбинация клавиш Ctrl+, Ctrl+ - движение на одно слово влево/вправо.

(Движение осуществляется только по словам из латинских букв, слова из русских букв считаются одним словом, даже если они разделены пробелами.)

Home - в первую позицию строки.

End - в конец текста в строке.

PgUp - на страницу вверх.

PgDn - на страницу вниз.

Ctrl+Home - в начало файла.

Ctrl+End - в конец файла.

Ctrl+G - появляется окно, в котором Вы ожете задать номер строки, на которую Вы хотите переместиться.

1.2. Удаление, копирование и восстановление. Shift+(, , Home, End, PgUp, PgDn) выделение текста для удаления, копирования. Выделение производится от текущей позиции курсора.

Замечание. SC - тмена любой команды, в том числе и выделения.

После выделения можно выполнить команды:

Shift+Del (=Cut в меню Edit) - уничтожение и перемещение в Clipboard;

F2 (=Copy в меню Edit) - опирование в Clipboard;

Del (=Clear в меню Edit) - удаление (в Clipboard текст не заносится).

Восстановление текста из Clipboard:

Shift+Ins (=Paste в меню Edit) - размещает содержимое

Clipboard в текущий файл от текущей позиции курсора.

Ctrl+R (=Undo в меню Edit) - откат. Действует в пределах строки, т.е., если Вы произвели какие-либо изменения в строке, а

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

1.3. Поиск текста и замена. Arity-редактор дает Вам возможность искать подстроку в файле, перемещаться на следующее вхождение этой подстроки в файл и искать подстроку и заменять ее на другую подстроку. Поиск осуществляется сверху вниз по файлу от текущей позиции курсора.

F4 (=Find в меню Edit) - поиск. Шаблон задается в диалоговом окне.

Замечание. Перемещение внутри диалоговых окон осуществляется с помощью клавиши Tab , а выбор опции - клавишей "пробел".

Могут быть выбраны следующие опции поиска:

Whole Word (целое слово) - при выборе этой опции редактор ищет именно данное слово, вхождения этого слова в виде подслова не будут найдены. Например, run в слове running не будет найдено. По умолчанию действует режим поиска как целых слов, так и вхождений слов в виде подслов.

Case Sensitive (различать прописные и строчные) - при выборе этой опции редактор находит заданное сочетание прописных и строчных букв.

Для нахождения следующего вхождения используется F3.

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

Ctrl+\ (=Find Selected в меню Edit) - также ищет текст в файле, но диалоговое окно не появляется. Сначала выделяется шаблон с помощьюShift+"стрелки". Затем, спользуя эту команду, можно найти все вхождения выбранного текста в файле (сверху вниз от текущей позиции курсора). По умолчанию действуют опции поиска Whole Word и Case Sensitive.

F3 (=Repeat Last Find в меню Edit) - повторяет п оследний поиск, который был осуществлен с помощью F4. Можно повторить поиск, даже если после предыдущего поиска были выполнены какие-либо другие действия (например, копирование или удаление).

F5 (=Change в меню Edit) - поиск и замена. В диалоговом окне задаются тексты поиска и замены, а также опции Whole Word и Case Sensitive, рассмотренные выше в команде поиск (F4

2. ИСПОЛЬЗОВАНИЕ БУФЕРОВ

Содержимое буфера может быть записано в файл с помощью опций Save или Save as... (подменю File), а может запоминаться автоматически при установке соответствующей опции подменю Buffers.

Save On Exit – автоматическое запоминание содержимого буфера при выходе из редактора.

Reconsult On Exit – автоматическая загрузка в базу содержимого буфера при выходе из него.

Indent – автоматически помещает курсор в позицию, с которой начиналась предыдущая строка.

Read Only – текущий буфер будет открыт только для чтения.

Эти опции подменю Buffers действуют только в пределах одного буфера. Они выбираются с помощью Enter (появится маркер). Таким образом, для каждого буфера можно задать свои опции.

Напомним, что

F6 – (=Go To... в меню Buffers) - в диалоговом окне можно задать либо номер буфера, либо выбрать буфер, перемещаясь по списку, используя Tab и "стрелки". После выбора нажать Enter.

F7 – (=Go To Last в меню Buffers) - переключает Вас в предыдущий активный буфер. Таким образом, между двумя буферами можно "ходить", используя эту опцию.

3. ФУНКЦИОНАЛЬНЫЕ КЛАВИШИ

F1 помощь

F2 копирование отмеченного текста

F3 повторение последнего "поиска" при нахождении строки в тексте

F4 нахождение строки в файле (в диалоговом окне надо указать строку поиска)

F5 замена найденной подстроки на новую подстроку

F6 выбор буфера

F7 переход в предыдущий активный буфер из текущего буфера

F8 переход из главного окна в окно редактора и наоборот

F9 не определен

F10 выход в меню

ПРИЛОЖЕНИЕ 2

ТИПЫ ДАННЫХ ARITY/PROLOG

1. ПЕРЕМЕННЫЕ

Именем переменной может быть любая последовательность латинских букв и цифр, начинающаяся с прописной буквы или символа подчеркивания "_"; это может быть также одиночный символ подчеркивания "_", представляющий анонимную (безымянную) переменную.

Примеры переменных:

Balloon X _0039 _

Свободная (не имеющая значения) переменная может унифицироваться с любым термом, при этом она может конкретизироваться значением (в случае константы или сложного терма), либо связываться с другой переменной. Для связанной переменной в сопоставлении используется ее значение. Анонимная переменная значения не получает, с ней всегда возможно сопоставление.

2. СИМВОЛЬНЫЕ КОНСТАНТЫ ИЛИ АТОМЫ

Символьные константы могут содержать латинские буквы, цифры и специальные (прочие) символы (в том числе кириллицу). Если они начинаются с прописной буквы или цифры или содержат специальные символы, то они должны быть заключены в апострофы.

Если апостроф используется внутри атома, он удваивается.

Примеры символьных констант:

tennis '23 '0 'Paris ' 'юла' '--->' 'Mary''s'

Символьная константа всегда унифицируется с такой же символьной константой. Длина символьной константы не должна превышать 255 символов.

* Не путать символ апострофа (') с двойной кавычкой (").

3. ЦЕЛЫЕ ЧИСЛА

Целые числа могут быть положительные и отрицательные, в диапазоне от -2.147.483.648 до .147.483.647 (32 двоичных разряда со знаком).

Целое число всегда унифицируется с равным ему целым числом.

ASCII-коды символов также являются целыми числами. Они обозначаются соответствующим символом, которому предшествует одиночный обратный апостроф. Таким образом:

`a эквивалентно 97

4. ЧИСЛА С ПЛАВАЮЩЕЙ ЗАПЯТОЙ

Числа с плавающей точкой заключены в диапазоне от -1.7e308 до 1.7e308. Точность представления соответствует 15-ти десятичным разрядам.

Примеры чисел с плавающей точкой:

0.5 55.3 -83.0E21 134.2 122.34e25

Число с плавающей точкой унифицируется с равным ему числом с плавающей точкой. Однако следует помнить, что операции над числами с плавающей точкой выполняются приближенно и попытка унификации двух чисел с плавающей точкой, которые кажутся идентичными, может окончиться неудачей.

5. СТРОКИ

Строки - это текстовые константы, которые представляются в виде последовательности ASCII-символов, заключенной между знаками доллара. Размер строки не должен превышать 4096 символов.

Пример: $ He climbed and he climbed $

Пустая строка записывается $$. Если необходимо использовать знак доллара внутри строки, то его удваивают ($$).

Строка унифицируется с идентичной ей строкой, но не унифицируется с одиночным символом, даже если она единичной длины.

Строки и атомы никогда не унифицируются, даже если они содержат одинаковые символы, однако встроенный предикат == рассматривает как одинаковые строку и атом с одними и теми же символами.

Пример:

?- $russia$ == russia.

yes

6. СТРУКТУРЫ

Структура - универсальный тип данных, который используется для группировки термов или представления отношения между ними. Структура состоит из функтора и аргументов:

функтор(терм,терм,...,терм)

Число аргументов называется размерностью (арностью) структуры.

* Между функтором и левой скобкой пробел не ставится

Задайте к этой базе запросы (воспользуйтесь Help для поиска отношения "неравно").

Кто где живет?

Кто живет на земле, но не является собакой?

Кто живет и на земле, и в воде?

Пример: a1(b1(c1),b2,b3(d1,d2))

Эту структуру можно представить в виде дерева:

Структура унифицируется с другой структурой, если их функторы совпадают и аргументы попарно унифицируются.

Пример унифицируемых структур:

book(Author,Title) и book(james,$ The lonely tree $)

Пример неунифицируемых структур:

name(jones,charles) и name(jones,chuck)

В виде терма представляется любой объект программы.

Например, структура правила d:-a,b,c. может быть представлена деревом:

:-

/ \

d ^,

/ \

a ^,

/ \

b c

ЛИТЕРАТУРА

1. Ашинянц Р.А. Логические методы в искусственном интеллекте. –М.:МГАПИ, 2001. -223с.

2. Ашинянц Р.А. Логический язык программирования ПРОЛОГ. –М.:МГАПИ, 2001. -303с.

3. Клоксин У., Меллиш К. Программирование на языке Пролог. -М.: Мир, 1987. -336с.

4. Стерлинг Л., Шапиро Э. Искусство программирования на языке Пролог. -М.: Мир, 1989. -235с.

5. Братко И. Программирование на языке Пролог для искусственного интеллекта. -М.: Мир, 1990. -560с.

6. Малпас Дж. Реляционный язык Пролог и его применение. -М.: Наука, 1990. -464с.

Характеристики

Список файлов лабораторной работы