Шпора (Шпоры к первому коллоквиуму), страница 17
Описание файла
Файл "Шпора" внутри архива находится в папке "Шпоры к первому коллоквиуму". PDF-файл из архива "Шпоры к первому коллоквиуму", который расположен в категории "". Всё это находится в предмете "искусственный интеллект" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 17 страницы из PDF
возврат;; после применения двух операторов в исходное состояние;(cond((and (neq Op 'left) (< J Size))(ADD_STATE 'right K (add1 K)) ))(cond((and (neq Op 'right) (> J 1))(ADD_STATE 'left K (sub1 K)) ))(cond((and (neq Op 'down) (> I 1))(ADD_STATE 'up K (- K Size)) ))(cond((and (neq Op 'up) (< I Size))(ADD_STATE 'down K (+ K Size)) ))(return Dlist) ))При раскрытии используется вспомогательная функция ADD_STATE, добавляющая всписок дочерних вершин список-описание новой вершины из 2 элементов: идентификатора этойвершины (его генерирует функция gensym) и списка номеров фишек.
В ADD_STATEприменяется встроенная лисп- функция NTH, выбирающая из заданного списка элемент суказанным порядковым номером.(defun ADD_STATE (Op K1 K2)(push(list(gensym)(cons Op(cond((< K1 K2)(EXCHANGE State 1 '# K1 (NTH K2 State)K2))(t (EXCHANGE State 1(NTH K2 State)K2 '# K1))) ))Dlist))Рекурсивная функция EXCHANGE, используемая в ADD_STATE, формирует новоесостояние игры путем перестановки заданных элементов исходного состояния-списка List(переменная K служит для просмотра этого списка, при обращении к функции ее значение равно1).(defun EXCHANGE (List K Elem1 K1 Elem2 K2)(cond((eql K K1) (cons Elem2(EXCHANGE(cdr List)(add1 K)Elem1 K1 Elem2 K2) ))((eql K K2)(cons Elem1 (cdr List)) )) )Функция CONNECT формирует список указателей от текущей вершины-состояния Curr кзаданным (в списке Dlist) дочерним вершинам-состояниям.
Каждый указатель естьтрехэлементный список из идентификатора родительской вершины, идентификатора дочернейвершины и названия связывающего их оператора.(defun CONNECT (Dlist Curr)(prog (D Di Ci Rlist)C (setq D (car Dlist)) (setq Dlist (cdr Dlist))(setq Di (car D)) (setq Ci (car Curr))(setq Rlist(cons (list Ci Di (caadr D))Rlist))(cond ((null Dlist) (return Rlist) ))(go C) ))Функция SOLUTION, выделяя решающий путь, строит последовательность (названий)операторов, преобразующих начальное состояние в целевое (ее аргумент Reflist – список всехуказателей-связей между состояниями).
Для поиска указателя к очередной вершине решающегопути функция использует вспомогательную функцию LOOK_FOR .(defun SOLUTION (Goal Reflist)(prog (Sollist ;список, в котором строится решение;Gi Edge)(setq Gi (car Goal))S (cond((eq Gi 'S0) (return Sollist) ))(setq Edge (LOOK_FOR Gi Reflist))(setq Sollist (cons(caddr Edge) Sollist))(setq Gi (car Edge))(go S) ))(defun LOOK_FOR (Id List)(cond((null List) (quote error))((eq ID (cadar List)) (car List))(t(LOOK_FOR Id (cdr List)) )) )В заключение приведем блок, инициализирующий эвристический поиск решения игры ввосемь.
В самом его начале устанавливаются значения параметров встроенной функции gensym.(prog(Goalstate Initstate Size)(setq *gensym-prefix* 'S)(setq *gensym-count* 1)(setq Size 3)(setq Goalstate '(1 2 3 8 # 4 7 6 5))(setq Initstate '(? 2 8 3 1 6 4 7 # 5))(HEURISTIC_SEARCH Initstate)).