Лекции №17, №18 08. 11. 2011. Реализация на Лиспе и Плэнере алгоритма поиска вглубь - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Лекции №17, №18 08. 11. 2011. Реализация на Лиспе игры «8» Эвристический... 1 92.02kb.
Программа «Системы корпоративного управления» 1 50.59kb.
Искусственный интеллект – Севастополь, реализация эс на Плэнере 1 37.92kb.
М. В. Синьков, А. И. Закидальский, Е. А. Цыбульская 1 64.61kb.
Модификация схемы bm25 с помощью генетического алгоритма. С. 1 59.3kb.
Информационные системы и технологии 1 43.22kb.
7. 1 Claude Shannon (1938 г. Сша)- главный вклад реализация булевой... 1 309.52kb.
1. Конструкторская часть 4 16 1212.84kb.
4. Перечень экзаменационных тем Дисциплина «Алгоритмы и их сложность» 1 69.64kb.
Описание алгоритма хэширования 1 103.25kb.
Лекции по йоге, бесплатно скачать, аудио лекции, видео лекции, бесплатно... 1 172.13kb.
Электронная библиотека (ЭБ) 1 41.65kb.
Направления изучения представлений о справедливости 1 202.17kb.

Лекции №17, №18 08. 11. 2011. Реализация на Лиспе и Плэнере алгоритма поиска вглубь - страница №1/1


Искусственный интеллект – IV курс – День 10, лекции № 17, № 18 08.11.2011.

Реализация на Лиспе и Плэнере алгоритма поиска вглубь (основная функция)

Поиск вглубь на Лиспе и Плэнере


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

Поиск вглубь на Лиспе


Лисп-функция LIMITED_DEPTH_SEARCH поиска вглубь имеет два аргумента: кроме начального состояния StartState в число ее аргументов включена граничная глубина LimDepth. Предполагается, что в каждом списке-описании состояния, кроме идентификатора состояния и собственно описания состояния задачи, содержится также третий элемент – глубина этого состояния-вершины в дереве поиска. Проверка на окончание алгоритма (шаг 5 базового алгоритма), для упрощения программы производится в середине цикла.
(defun LIMITED_DEPTH_SEARCH (StartState LimDepth)

(prog (Open Closed Current

Deslist ;список дочерних вершин;

Reflist ;список указателей;

Depth ;глубина текущей вершины; )

;Шаг 1: занесение начальной вершины (ее глубина равна 0):;

;в список нераскрытых вершин:;

(setq Open (list (list 'S0 StartState 0)))

;Шаг 2:;

LS (cond ((null Open) (return ())))

;Шаг 3:; (setq Current (car Open))

(setq Open (cdr Open))

(setq Closed (cons Current Closed))

;Определение глубины текущей вершины:;

(setq Depth (caddr Current))

(cond ((IS_GOAL Current) ;/Шаг 5/;

(return (SOLUTION Current Reflist))))

;Шаг 3’:;(cond ((eql Depth LimDepth) (go LS)))

;Шаг 4:Раскрытие вершины, исключение повторных вершин и;

; модификация списков указателей и нераскрытых вершин:;

(setq Deslist (OPENING Current))

(setq Deslist (RETAIN_NEW Deslist))

(cond ((null Deslist) (go LS)))

(setq Open (append (ADD_DEPTH (add1 Depth) Deslist) Open))

(setq Reflist (append (CONNECT Deslist Current) Reflist))

(go LS) ))


Эта функция, как и функция эвристического поиска HEURISTIC_SEARCH, использует вспомогательные функции OPENING, SOLUTION, IS_GOAL, CONNECT (которые зависят от конкретной поисковой задачи), а также вспомогательные функции: RETAIN_NEW и ADD_DEPTH (упрощенный вариант функции ADD_DEPTH_EST).

Поиск вглубь на Плэнере


Плэнер-функция DEРTH_FIRST_SEARCH выполняет поиск вглубь от заданного состояния St, но без ограничения глубины (чтобы ограничить глубину, необходимо добавить в эту функцию дополнительный аргумент – граничную глубину, и несколько простых действий). Функция использует встроенный бэктрекинг языка Плэнер.

Значением этой функции является список всех состояний-вершин, лежащих на решающем пути от St до целевой вершины. Как и в случае реализации программ поиска на Лиспе, вспомогательные функции OPENING и IS_GOAL зависят от конкретной решаемой задачи: первая реализует раскрытие заданной вершины-аргумента и выдает как свое значение список дочерних вершин; вторая является предикатом, проверяющим, является ли исследуемая вершина-аргумент целевой.


[define DEРTH_FIRST_SEARCH (lambda (St)

[prog (Dst очередная раскрываемая вершина;

Reslist список, в котором строится решающий путь;)

[set Dst .St] [set Reslist (.St)]

DS [set Dst [among [OPENING .Dst]]]

[cond ([memb .Dst .Reslist] [fail])]

[set Reslist (!.Reslist .Dst)]

[cond ([IS_GOAL .Dst] [return .Reslist])

(t [go DS])] ])]


Из программных средств управления бэктрекингом (напомним, что в языке Плэнер он называется режимом возвратов) в приведенном тексте используется только функция among, организующая точку выбора альтернатив (развилку). В соответствующей строке программы с меткой DS, являющейся началом внутреннего цикла, раскрывается очередная вершина, из получившихся дочерних вершин образуется развилка (точка бэктрекинга) и выбирается одна из вершин развилки. Затем проверяется, содержится ли выбранная вершина-состояние в списке Reslist, и если это не так, то она добавляется в этот список, где последовательно формируется решающий путь. Далее проверяется, не является ли выбранная вершина целевой, и в зависимости от результата этой проверки либо поиск успешно заканчивается, либо производится переход на начало цикла – для того, чтобы, раскрывая текущую вершину, идти вглубь дерева поиска (каждый шаг цикла соответствует шагу вниз в дереве поиска).

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

Отметим, что плэнерская функция fail, инициирующая автоматический процесс возврата, в рассмотренной функции DEРTH_FIRST_SEARCH применя­ется только для предотвращения зацикливания, когда порожденная дочерняя вершина уже содержится в списке Reslist. В этом случае происходит возврат к текущей развилке для выбора следующей дочерней вершины. Возврат же к предыдущей по времени возникновения развилке (т.е. точке бэктрекинга, организованной на предыдущем шаге цикла и лежащей на один шаг вверх в дереве перебора) инициируется самой функцией among в двух следующих случаях. Во-первых, когда список порожденных дочерних вершин оказался пуст, а во-вторых, когда уже перепробованы все установленные в развилке варианты (дочерние вершины) и все они оказались неуспешными.

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

Если сравнивать эту плэнер-функцию с основной лисп-функцией для эвристического поиска, то нетрудно заметить, что встроенный механизм бэктрекинга позволяет обойтись без многих вспомогательных структур – списков открытых и закрытых вершин, списка указателей между вершинами и др., а также без операций по их модификации. Не используются также вспомогательные функции SOLUTION, CONNECT.

Кроме достоинств, заключающихся в упрощении программирования слепого перебора вглубь, встроенный бэктрекинг имеет и недостатки, главные из которых – «жесткость» и неэффективность.



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

Решение задач и искусственный интеллект





Умные большему учатся у дураков, чем дураки у умных. Катон Старший
ещё >>