Точно Не проект 2 / Не books / Источник_1

та. Тогда необходимо удалить соответствующую вершину из списка CLOSED и вставить ее в список OPEN с учетом значения оценочной функции. Кроме этого, если в процессе раскрытия очередной вершины будет установлено, что ее дочерние вершины уже включены в список OPEN, то выполняется сравнение оценочных функций вершин, уже имеющихся в списке OPEN, и вновь полученных дочерних вершин. Если оценочные функции вновь полученных дочерних вершин меньше, то они заменяют уже имеющиеся вершины в списке OPEN. Приведем определение функции

A-SEARCH:

(defun a-search(start goal)

;поместить в open стартовую вершину, описываемую

;подсписком со структурой ( s s 0 h)

(setq open (cons start nil)) ; инициализация closed

(setq closed nil)

(loop ; цикл

(cond ((null open)(return ’неудача)) ; на графе нет пути

(t

;запомнить первый подсписок списка open (setq n (first open))

;удалить n из open

(setq open (remove n open :test #'equal)) ; внести n в closed

(setq closed (cons n closed))

;проверить, является ли (first n) целевой вершиной

(if (eq (first n) goal) (return ’удача))

;внести в open дочерние вершины и удалить

;их при необходимости из closed

(put-in-list (list-children n))

;печать промежуточных результатов

(terpri)

(princ ”closed=”)(prin1 closed) (terpri)

(princ ”open=”) (prin1 open)))))

Вэтом определении функция LIST-CHILDREN возвращает а-список дочерних вершин для вершины (first n), которая при вызове LIST-CHILDREN является первым подсписком списка OPEN.

(defun list-children (n) (setq L nil)

(dolist (temp graph L) ; выполнить действия для каждого

;подсписка из graph

;переставить первый и второй элементы temp

(setq rtemp (rev temp))

;выяснить, содержит ли temp дочернюю вершину для (first n)

(t (setf open (del (first dv) open))

(setf closed (del (first dv) closed)) (setf open (add (first dv) open)) (put-in-list (rest dv)))))

Функция DEL(V L) выполняет удаление подсписка V, представляющего вершину графа состояний, из списка L. Удаление выполняется, если оценочная функция для удаляемой вершины V меньше либо равна значению оценочной функции вершины из списка L:

(defun del(v l)

(cond ((null l) nil) ; завершение рекурсии

; проверка вхождения v в l

((and (eq (first v)(first(first l)))

; сравнение оценочных функций

(<= (fourth v)(fourth (first l))))

(setf l (cdr l)))

(t (append (list(car l)) (del v (cdr l))))))

Вставка дочерних вершин в упорядоченный список OPEN выполняется с помощью функции ADD(V L):

(defun add(v l)

(cond ((null l) (cons v l)) ; выход из рекурсии

;сравнить значения оценочных функций

((<= (fourth v)(fourth (first l)))

; если меньше, то вставить вершину v в l (setf l (cons v l)))

(t (append (list(car l)) (add v (cdr l))))))

Функция MEMBER1(V L) определяется следующим образом:

(defun member1 (v l) (cond ((null l) nil)

((eq v (first(first l))) t)

(t (member1 v (rest l)))))

Если функция A-SEARCH завершает поиск сообщением “УДАЧА”, то восстановить путь из исходной вершины в целевую вершину можно с помощью функции BACK-WAY, описанной в предыдущем параграфе.

Рассмотрим выполнение эвристического поиска на примере графа состояний, который изображен на рисунке 2.9. Найдем путь из стартовой вершины S в целевую вершину G. Для этого выполним вызовы:

(a-search ’(s s 0 14) ’g)

(back-way ’g ’s))

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

Рассмотрим сопоставление с образцом, представляя образец и сопоставляемые с ним факты (данные) в виде списков языка Лисп. Простейшие возможности сопоставления реализуются встроенными предикатами Лиспа, например EQ, EQL, EQUAL. Если необходимо осуществлять сопоставление произвольных s-выражений, то следует определить отдельную функцию. Для начала определим функцию, выполняющую сопоставление одноуровневых списков.

К сопоставлению образца и данных можно предъявлять различные требования. Пусть символ ‘?’ в образце отождествляется с любым элементом из списка данных, а символ ‘$’ – с произвольным числом (возможно нулевым) элементов списка данных. Символы ‘?’ и ‘$’ рассматривают как универсальные символы подстановки, которым может быть сопоставлен любой элемент или сегмент списка, соответственно. Обозначим сопоставимость двух выражений знаком :=:, и сформулируем простые правила сопоставления [39]:

ОБРАЗЕЦ :=: ДАННЫЕ

; один из списков исчерпан

((or (null p)(null d)) nil)

;правило 3 и правило 4 ((or (equal (car p) ’?)

(equal (car p) (car d))) (match (cdr p)(cdr d)))

;правило 5 и 6 ((eq (car p) ’$)

(cond ((match (cdr p) d) t) ((match p (cdr d)) t))) ))

Здесь предварительное условие для правил 3 – 6 – (ДАННЫЕ NIL) и (ОБРАЗЕЦ NIL) – записано перед правилом 3 в виде:

((or (null p)(null d)) nil)

Если один из списков p или d исчерпан, то это исключает применение последующих правил, и функция MATCH возвращает NIL.

Функцию MATCH можно легко расширить, чтобы она могла сопоставлять списки с вложенными подсписками. Для этого достаточно добавить в текст функции следующее правило:

;правило 7 - сопоставление списков,включающих подсписки

((and (not (atom (car p)))

(not (atom (car d))) (match (car p)(car d)))

(match (cdr p) (cdr d)) )

В этом случае функция MATCH будет обеспечивать сопоставление более сложных символьных структур. Например,

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

‘$’. Например, ?V или $V. В первом случае в переменную V подставляется произвольный символ данных, во втором – сегмент списка данных.

Расширим возможности функции MATCH так, чтобы она могла запоминать подстановки в переменных. Например:

(match ’(AVTO ?MODEL ?YEAR) '(AVTO ford 1998)) T model ford

year 1998

Сопоставления с конструкциями ?V или $V могут быть реализованы с помощью двух новых функций – CAR-LETTER и CDR-NAME. Функция CAR-LETTER обеспечивает выделение первой литеры из имени очередного атома образца, а функция CDR-NAME формирует имя переменной из оставшихся литер:

(defun car-letter (x) (car (coerce (string x) ’list)))

(defun cdr-name (x)

(intern (coerce (cdr (coerce (string x) ’list)) ’string)))

Здесь x – атом образца, который с помощью вызова (string x) преобразуются в строку. Затем из строки выделяются первая литера (функция carletter) и все оставшиеся литеры (функция cdr-name), которые образуют имя переменной. Полученное имя переменной с помощью функции INTERN включается в список имён символов. Функция INTERN проверяет, есть ли символ с данным именем в списке имен символов. Если такой символ имеется, то функция возвращает ссылку на имя этого символа, если нет, то добавляет новый символ в список имен и возвращает ссылку на него.

Добавим в функцию МАТСН правило, обеспечивающее сопоставление очередного элемента данных с параметром вида ?V:

;правило 8

((and (atom (car p))

(eq (car-letter (car p)) #\?) (match (cdr p)(cdr d)))

(set (cdr-name (car p)) (car d) t)

В соответствии с правилом сначала убеждаемся, что очередной элемент образца представляет собой атом, начинающийся с литеры #\?, а также проверяем сопоставимость хвостовых частей образца и данных. Если указанные проверки выполняются успешно, то переменной присваивается значение очередного элемента списка данных.

Для обработки параметра образца вида $V введем в функцию МАТСН дополнительное правило: