Шпора (Шпоры к первому коллоквиуму), страница 16

Функции отличаются лишь вторымслагаемым, и можно показать, что значение второй функции всегда (т.е. для всех состояний),больше значения первой функции: Est1(V) ≤ Est2(V) , что равнозначно k (V) ≤ s (V) .Действительно, во второй функции вклад каждой фишки в общую оценку-сумму s(V) либо равен 0(фишка стоит уже на «своем» месте), либо не меньше 1 (в противном случае), в первой жефункции этот вклад в k(V) соответственно либо равен 0, либо равен 1.Из последнего неравенства следует, что условие допустимости достаточно доказать толькодля второй функции Est2. Справедливость нужного условияs(V) ≤ h*(V) следует из следующего соображения.

Если бы фишки не мешали друг другу и моглидвигаться до «своего» места по кратчайшему пути, как если бы других фишек на квадрате небыло, то сумма длин таких путей для всех фишек была бы в точности равна значению s(V) . Насамом же деле фишки редко когда могут двигаться по кратчайшей траектории из-за того, что наней расположены другие фишки, поэтому длина (стоимость) оптимального решения h*(V) будет неменьше s(V).Заметим, что s(V) не учитывает должным образом трудность обмена местами двухсоседних фишек, а поэтому ее эвристическая сила в принципе может быть повышена. В рядеслучаев эвристическая сила некоторой оценочной функции может быть повышена просто путемумножения на положительную константу, большую единицы, однако часто такое повышениеосуществимо только за счет отказа от допустимости алгоритма. Например, если для игры в восемьв качестве второй составляющей эвристической функции взять h(V) = 2•s(V), то в ряде случаевтакая функция будет убыстрять поиск и позволит решать более трудные задачи, но условиедопустимости перестанет выполняться (так как для начального состояния на рис.15: h*(V) ≤ 2•s(V)).Вообще в случае, когда верно неравенство h1(V) ≤ h2(V) для всех вершин пространствасостояний, не являющихся целевыми, А*-алгоритм, использующий эвристическую составляющуюh2(V), называется более информированным, чем А*-алгоритм с функцией h1(V).

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

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

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

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

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

Алгоритм становитсянесостоятельным, если у эвристической функции имеется несколько локальных экстремумов.Бывают и другие случаи бесперспективности «подъема на холм»: если поверхность-множествозначений функции имеет равнинный участок («плато») или же участки узкого и длинноговозвышения (в виде горного «хребта»), и процесс поиска вывел как раз на них. Таким образом,этот алгоритм имеет ограниченную применимость, но иногда возникающие проблемы можноразрешить, построив более подходящую эвристическую функцию.Эвристический перебор на ЛиспеПриведем текст лисповской функции 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 устанавливает глубину дочерних вершин и вычисляет ихэвристическую оценку:(defun ADD_DEPTH_EST (Dn Slist)(cond((null Slist) ())(t (cons(list (caar Slist) (cadar Slist) Dn(EST(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 ('left 2 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 – сумма числа фишек, стоящих не на «своих» местах, и длины пути (глубины)оцениваемого состояния в дереве поиска.(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;; исключаем в дереве поиска тривиальные циклы, т.е.