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

Один из нихназывается целенаправленностью и вычисляется как P = L / N , гдеL – длина найденного пути до цели (она равна глубине целевой вершины), аN – общее число вершин, построенных в ходе перебора.P = 1, если строятся только вершины решающего пути, в остальных случаях P < 1, вообще, эта величинатем меньше, чем больше строится бесполезных вершин. Таким образом, этот критерий показывает,насколько дерево, построенное при переборе, вытянуто, а не кустисто. К сожалению, величина P зависитот длины решающего пути, что затрудняет порой сравнение алгоритмов. Другой критерий оценки,фактор эффективного ветвления, зависит от длины решающего пути гораздо меньше.47Ясно, что алгоритм эвристического поиска с хорошо подобранной оценочной функциейобнаруживает решение задачи быстрее алгоритмов слепого перебора.

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

по тому, насколько они убыстряют поиск, делают его эффективным. Заметим,что эвристическая сила функции должна учитывать общий объем вычислительных затрат при поиске,поэтому кроме числа раскрытых и построенных вершин важен и такой фактор, как сложностьвычисления самой оценочной функции.Для игры в восемь можно предложить еще одну эвристическую функцию:Est2(V) = d(V) + s(V) .Первое слагаемое d(V) этой функции имеет тот же смысл, что и для функции Est1.

Второе слагаемоеполучается, если для каждой из восьми фишек подсчитать сумму двух расстояний – по вертикали игоризонтали – между клетками, где находится эта фишка в оцениваемом и целевом состояниях, а затемподсчитать общую сумму s(V) таких расстояний для всех восьми фишек (тем самым получим«суммарное расстояние» всех фишек от их целевого положения).Например, для начальной конфигурации на рис.1 расстояние текущего положения фишки сномером 8 от ее положения в целевой конфигурации равно 1 и по вертикали, и по горизонтали, а суммаих равна 2. Общая же сумма таких расстояний для всех фишек равна 5 (фишки 3, 4, 5, 7 стоят уже на«своем» месте, поэтому их вклад в суммарное расстояние равен 0).

Интуитивно ясно, и это можнопоказать на примерах, что новая эвристическая функция имеет большую эвристическую силу, т.е. болееэффективно направляет поиск к цели.48.Рис.10 2 8 31 6 44 7 51 2 8 32 2 8 33 2 8 31 6 46 7 5 51 6 46  7 51  44 7 6 54 2 8 35 2 8 3 1 47 6 51 4 6 7 6 556 2  351 8 47 6 57  8 38 2 8 39  2 310 2 3 2 1 47 6 57 1 47  6 51 8 45 7 6 51 8 47 7 6 5611 1 2 3 8 45 7 6 512 1 2 313 1 2 38  47 6 57 8 47  6 55Допустимость алгоритма эвристического перебораВажным является вопрос, может ли алгоритм эвристического перебора с оценочной функцийобщего вида (т.е. выбираемой произвольно) гарантировать нахождение решающего пути за конечноечисло шагов в тех случаях, когда решение существует (как алгоритм поиска вширь).

Понятно, что такойуверенности нет прежде всего для задач с бесконечными пространствами состояний. Вообще же,нередка ситуация, когда эвристика, сильно сокращающая перебор для большинства начальныхсостояний, в то же время для других начальных конфигураций либо не может уменьшить необходимуюпереборную работу (и решение задачи может искаться даже дольше, чем с использованием слепогометода), либо вовсе не может обеспечить обнаружение решающего пути.Математическое исследование алгоритма эвристического поиска – условий, гарантирующихнахождение им решения – было проведено для эвристических оценочных функций специального вида и49для более сложной задачи, чем до сих пор рассматриваемая задача поиска любого решающего пути доцелевой вершины.Предположим, что на множестве дуг пространства состояний определена функция стоимости:с(VA, VB) – стоимость дуги-перехода от вершины VA к вершине VB .Определим также стоимость любого пути в графе-пространстве как сумму стоимостей входящих в путьдуг.

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

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

Были доказаны важные свойства этого алгоритма, прежде всего,утверждение о его допустимости.Алгоритм перебора называют допустимым (или состоятельным), если для произвольного графаон всегда заканчивает свою работу построением оптимального пути к цели, при условии, что такой путьсуществует.Пусть h*(V) – стоимость оптимального пути из произвольной вершины V в целевую вершину.Верна следующая теорема о допустимости А-алгоритма:А-алгоритм, использующий некоторую эвристическую функцию вида (*), гдеg(V) – стоимость пути от начальной вершины до вершины V в дереве перебора, аh(V) – эвристическая оценка оптимального пути из вершины V в целевую вершину,является допустимым, если h(V)  h*(V) для всех вершин V пространства состояний.А-алгоритм эвристического поиска, применяющий функцию h(V), удовлетворяющую этомуусловию, получил название А*-алгоритма.Практическое значение этой теоремы в том, что для допустимости А-алгоритма достаточнонайти какую-либо нижнюю грань функции h*(V) и использовать ее в качестве h(V) – тогдаоптимальность найденного алгоритмом решения будет гарантирована.Если взять тривиальную нижнюю грань, т.е.

установить h(V) = 0 для всех вершин пространствасостояний, то допустимость будет обеспечена. Однако этот случай соответствует полному отсутствиюкакой-нибудь эвристической информации о задаче, и оценочная функция Est не имеет никакойэвристической силы, т.е. не сокращает возникающий перебор. А*-алгоритм ведет себя при этоманалогично поиску вширь.Точнее, при Est(V) = g(V) (где g(V) – стоимость пути от начальной вершины до вершины V ),мы получаем алгоритм, известный как алгоритм равных цен (или Алгоритм Дейкстры).

Алгоритмравных цен представляет собой более общий вариант метода перебора в ширину, при котором вершиныраскрываются в порядке возрастания стоимости g(V) , т.е. в первую очередь раскрывается вершина изсписка нераскрытых вершин, для которой величина g имеет наименьшее значение.Если же, кроме того, положить стоимость с(VA, VB) = 0 для всех дуг пространства состояний, тоА*-алгоритм просто превращается в неэффективный слепой поиск вширь.Обе предложенные для игры в восемь эвристические функции Est1(V) и Est2(V) удовлетворяютусловию допустимости А*-алгоритма. Первое их слагаемое d(V) есть стоимость пути к вершине V пристоимости всех дуг с(VA, VB) = 1. Функции отличаются лишь вторым слагаемым, и можно показать, чтозначение второй функции всегда (т.е.

для всех состояний), больше значения первой функции: Est1(V) Est2(V) , что равнозначно k (V)  s (V) .50Действительно, во второй функции вклад каждой фишки в общую оценку-сумму 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). Показано, что если этифункции статичны (т.е. не изменяются в процессе поиска), то более информированный алгоритмраскрывает всегда меньшее число вершин, прежде чем находит путь минимальной стоимости.