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

Воспользуемся в качестве оценочной следующей простойфункцией:Est1(V) = d(V) + k(V) , гдеd(V) – глубина вершины V, или число ребер дерева на пути от этой вершины к начальной вершине;k(V) – число фишек позиции-вершины V, стоящих не на «своем» месте (фишка стоит не на «своем»месте, если ее позиция отлична от позиции в целевом состоянии).На рис.7 показано дерево, построенное алгоритмом эвристического перебора с указаннойоценочной функцией. Оценка каждой вершины приведена рядом с ней внутри кружка. Отдельностоящие цифры, как и раньше, показывают порядок, в котором строились вершины. Двойнойрамкой обведена найденная целевая вершина, она построена двенадцатой.Видно, что поскольку каждый раз выбор вершины с минимальной оценкой производитсявнутри всего построенного к текущему моменту дерева перебора, то раскрываемые друг за другомвершины могут располагаться в отдаленных друг от друга частях дерева.

Применяемая оценочнаяфункция такова, что при прочих равных преимущество имеет менее глубокая вершина.Решение задачи длиною в пять ходов найдено в результате раскрытия 6 и построения 13вершин – это существенно меньше, чем при использовании слепого перебора (соответствующиечисла были: 26 и 46, 18 и 35). Таким образом, использование эвристической информации приводитк существенному сокращению перебора.Существует несколько критериев оценки качества работы алгоритмов перебора. Один изних называется целенаправленностью и вычисляется как P = L / N , гдеL – длина найденного пути до цели (она равна глубине целевой вершины), аN – общее число вершин, построенных в ходе перебора.P = 1, если строятся только вершины решающего пути, в остальных случаях P < 1, вообще, этавеличина тем меньше, чем больше строится бесполезных вершин.

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

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

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

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