PDF-лекции, страница 16

Этозначит, что более информированный алгоритм осуществляет более направленный, а значит, болееэффективный (при прочих равных) поиск целевой вершины. Таким образом, понятиеинформированности отражает один из аспектов понятия эвристической силы оценочной функции припоиске в пространстве состояний.Итак, желательно подобрать такую эвристическую функцию h(V), которая была бы нижнейграницей h*(V) (чтобы гарантировать допустимость алгоритма) и была бы как можно ближе к h*(V)(чтобы обеспечить эффективность поиска). К сожалению, существуют задачи, для которых нельзя найтиоценочную функцию, обеспечивающую во всех случаях как эффективность, так и допустимостьэвристического поиска. Поэтому часто приходится останавливаться на эвристических функциях,сокращающих поиск во многих случаях ценой отказа от гарантии найти оптимальный решающий путь.Заметим, что в идеальном случае, когда известна оценка h*(V), и она используется в качествеh(V), А*-алгоритм находит оптимальный решающий путь сразу, без раскрытия ненужных вершин.Упрощенные варианты эвристического перебораСильным упрощением базового алгоритма эвристического поиска с произвольной оценочнойфункцией является алгоритм «подъема на холм».

Этот алгоритм при каждом раскрытии вершиныпроизводит упорядочение (по значению оценочной функции) только порожденных дочерних вершин, ивыбирает для последующего раскрытия дочернюю вершину с наименьшей оценкой (а не вершину снаименьшей оценкой среди всех нераскрытых вершин дерева поиска, как в базовом алгоритме).Очевидно, что такой локальный выбор среди только что построенных дочерних вершин реализоватьгораздо проще, чем глобальный выбор вершины во всем дереве перебора.Идея этого алгоритма аналогична идее известного вне области искусственного интеллектаметода «подъема на гору», применяемого для поиска максимума (или минимума) функции. Для того,чтобы в конечном счете найти максимум функции, на каждом шаге метода производится движение внаправлении наибольшей крутизны функции. Для определенного класса функций (имеющихединственный максимум и некоторые другие свойства роста) такое использование локальнойинформации, т.е.

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

Поиск продолжается всегдаот той дочерней вершины, которая имеет меньшее значение эвристической функции (при этом случай,когда вершин с одинаковой минимальной оценкой несколько, является нежелательным).Алгоритм «подъема на холм» дает тот же результат, что и базовый алгоритм эвристического поиска втех случаях, когда оценочная функция обладает определенными свойствами, в частности, имеет один(глобальный) экстремум. Алгоритм становится несостоятельным, если у эвристической функцииимеется несколько локальных экстремумов. Бывают и другие случаи бесперспективности «подъема нахолм»: если поверхность-множество значений функции имеет равнинный участок («плато») или жеучастки узкого и длинного возвышения (в виде горного «хребта»), и процесс поиска вывел как раз наних.

Таким образом, этот алгоритм имеет ограниченную применимость, но иногда возникающиепроблемы можно разрешить, построив более подходящую эвристическую функцию.Эвристический перебор на Лиспе (игра «8»)Приведем текст лисповской функции HEURISTIC_SEARCH, реализующей эвристическийперебор в пространстве состояний с использованием эвристической оценочной функции EST(зависящей от конкретной поисковой задачи). Вычисляемая для каждого состояния эвристическаяоценка хранится как четвертый элемент списка-описания состояния, а третий элемент этого спискаявляется глубиной состояния в дереве поиска.

Заметим, что на шаге 3, выбирая из списка Open первыйэлемент-вершину, мы тем самым выбираем вершину с минимальной оценкой, поскольку список Openвсегда упорядочен по неубыванию оценок вершин-состояний, хранящихся в нем (это обеспечиваетсявспомогательной функцией MERGE).(defun HEURISTIC_SEARCH(StartState)(prog (Open Closed CurrentDeslist ;список дочерних вершин;Reflist ;список указателей;Depth ;глубина текущей вершины;);Шаг 1:;(setq Open (list (list 'S0 StartState 0(EST (list StartState 0)))));Шаг 2:; НS(cond((null Open) (return())));Шаг 3:;(setq Current (car Open))(setq Open (cdr Open))(setq Closed (cons Current Closed))(setq Depth (caddr Current));Шаг 4:;(cond((IS_GOAL Current)(return (SOLUTION Current Reflist))));Шаг 5:;(setq Deslist (OPENING Current)); Исключение повторных вершин-состояний;(setq Deslist (RETAIN_NEW Deslist))(cond((null Deslist) (go НS) ));Шаг 6:;(setq Open (MERGE (SORT(ADD_DEPTH_EST(add1 Depth) Deslist))Open))(setq Reflist(append(CONNECT Deslist Current)Reflist))(go HS) ))Данная функция использует вспомогательные функции OPENING, SOLUTION, IS_GOAL,CONNECT, EST (которые зависят от конкретной поисковой задачи), а также три вспомогательныефункции: RETAIN_NEW, ADD_DEPTH_EST и MERGE.Вспомогательная функция RETAIN_NEW оставляет в списке дочерних состояний Dlist толькоте, которые не порождались ранее – тем самым исключается зацикливание при поиске в произвольномграфе.

Вспомогательная функция SORT упорядочивает (по неубыванию эвристической оценки) списокдочерних вершин, к элементам которого добавлена информация о глубине в дереве поиска и об оценке.Определения этих двух функций мы не рассматриваем.Функция ADD_DEPTH_EST устанавливает глубину дочерних вершин и вычисляет ихэвристическую оценку:52(defun ADD_DEPTH_EST (Dn Slist)(cond((null Slist) ())(t (cons(list (caar Slist) (cadar Slist) Dn(ESTIMATE(list (cadar Slist) Dn)) )(ADD_DEPTH_EST Dn (cdr Slist)) ) )) )Функция MERGE выполняет слияние двух упорядоченных (по неубыванию эвристическойоценки) списков состояний в результирующий упорядоченный список:(defun MERGE (L1 L2)(cond((null L1) L2)((null L2) L1)((gt (car (cdddar L1)) (car (cdddar L2)))(cons(car L2) (MERGE L1 (cdr L2))))(t(cons(car L1) (MERGE (cdr L1) L2))) ))Игра в восемь (Лисп)Граф-пространство состояний для головоломки-игры в восемь достаточно велик (в игре впятнадцать фишек он на порядок больше), поэтому хотя в принципе применимы алгоритмы слепогопоиска, предпочтителен все же эвристический поиск.

Опишем нужные для HEURISTIC_SEARCHвспомогательные лисп-функции: IS_GOAL, EST, OPENING, SOLUTION, CONNECT - для игры ввосемь. Состояние задачи (конфигурация игры) представляется списком из следующих элементов: идентификатор состояния (используются атомы S1, S2, S3, … , генерируемыевстроенной лисп-функцией gensym); собственно описание состояния – список из номеров фишек, записанныхпоследовательно по рядам квадрата; число-глубина состояния-вершины в дереве перебора; числовая эвристическая оценка состояния.В описание состояния включается также – в качестве первого элемента списка – обозначениетого оператора движения пустой клетки, который привел к данному состоянию. Этот элемент нужен,чтобы исключить тривиальные повторы состояний при раскрытии вершин. Операторы будутобозначаться соответственно именами-атомами right, left, up, down; а "пустышка" (пустаяклетка) – символом #.

Отметим, что эвристическая оценка используется только в алгоритмеэвристического перебора, а глубина вершины – в алгоритмах эвристического перебора и ограниченногоперебора вглубь.Для примера, приведенного на рис. 1 в основной части текста День 10, лекции № 19, № 20,начальное состояние S0 имеет такой вид: (? 2 8 3 1 6 4 7 # 5). Символ «?» означает, чтооператора, который привел к данному состоянию, нет.

При обращении к функции HEURISTIC_SEARCHс таким параметром на Шаге 1 в описание состояния S0 будут добавлены: этот идентификатор,информация о глубине (0) и эвристической оценке (4), затем будет сформирован список Open:((S0 (? 2 8 3 1 6 4 7 5 #) 0 4))Дочерние вершины S0:(S1 ('right 2 8 3 1 6 4 7 5 #))(S2 ('left2 8 3 1 6 4 # 7 5))(S3 ('up2 8 3 1 # 4 7 6 5))будут построены (именно в таком порядке) на Шаге 5 функцией OPENING.

Список этих вершин станетзначением переменной Deslist.На шаге 6 в эти описания будет добавлена информация о глубине вершин (1) и их эвристическихоценках (6, 6, 4) – в функции ADD_DEPTH_EST.Описанные ниже лисп-функции для игры в восемь пригодны и для игры в пятнадцать, так какразмер стороны игрового квадрата, равный 3, используется в них как глобальная переменная(переменная Size). Другая глобальная переменная (Goalstate), хранит описание целевогосостояния (без идентификатора, глубины и эвристической оценки). Значение оценочной функции EST –сумма числа фишек, стоящих не на «своих» местах, и длины пути (глубины) оцениваемого состояния вдереве поиска.53(defun IS_GOAL(State)(equal (cdadr State) Goalstate ))(defun EST (S)(prog(Len G N E1 E2)(setq Len (cadr S)) (setq N 0)(setq S (cdar S)) (setq G Goalstate);одновременный просмотр списков-описаний;заданного и целевого состояний:ES (cond((null S) (return (+ (- N 1) Len)) ))(setq E1 (car S)) (setq S (cdr S))(setq E2 (car G)) (setq G (cdr G))(cond((neq E1 E2) (setq N (add1 N))((eq E1 '#) (setq N (add1 N)))(go ES) ))(defun OPENING (State)(prog(Op St Dlist K I J El); выделение составных элементов описания состояния;(setq St (cadr State))(setq Op (car St)) (setq St (cdr St))(setq State St) (setq K 0); поиск порядкового номера К "пустышки" в списке;OP (setq El (car St))(setq K (add1 K))(cond ((neq El '#) (setq St(cdr St)) (go OP) )); вычисление номера ряда и номера столбца "пустышки";(setq I(add1(mod K Size))) (setq J (rem K Size)); поочередно проверка возможности движения «пустышки»;; вправо/влево/вверх/вниз; за счет анализа оператора Op;; исключаем в дереве поиска тривиальные циклы, т.е.

возврат;; после применения двух операторов в исходное состояние;(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)54(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) дочерним вершинам-состояниям.