Главная
страница 1



Лекция 15

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

Общий подход, называемый поиском по первому наилучшему совпадению,

*представляет собой разновидность общего алгоритма Tree-Search или Graph-Search, в котором узел развёртывания выбирается на основе функции оценки, f(n). По традиции для развёртывания выбирается узел с наименьшей оценкой, поскольку такая оценка измеряет расстояние до цели. Поиск по первому наилучшему совпадению можно реализовать в рамках общей инфраструктуры поиска с помощью очереди по приоритету – структуры данных, в которой периферия поиска поддерживается в возрастающем порядке fзначений.

Название «поиск по первому наилучшему совпадению»(best first search) узаконено традицией, но неточно. Если бы действительно можно было бы развернуть наилучший узел первым, то не было бы необходимости в поиске как таковом; решение задачи представляло бы собой прямое шествие к цели. Единственное, что в этом случае необходимо сделать – выбрать узел, который представляется наилучшим в соответствии с функцией оценки. Если функция оценки оказывается малопригодной, то поиск может зайти в тупик.

Существует целое семейство алгоритмов «поиска по первому наилучшему совпадению» с различными функциями оценки. Ключевым компонентом этих алгоритмов является эвристическая функция h(n) – оценка стоимости наименее дорогостоящего пути от узла n до целевого узла.

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


Жадный «поиск по первому наилучшему совпадению»

При жадном «поиске по первому наилучшему совпадению» оценка узлов производится с использованием только эвристической функции f(n)=h. Задача поиска маршрута в Румынии решается на основе эвристической функции определения расстояния по прямой hSLD(Straight Line Distance – SLD). Поскольку целью является Бухарест , то необходимо знать расстояния по прямой от каждого прочего города до Бухареста

На рис.1 показан процесс применения жадного поиска по первому наилучшему совпадению с использованием значений hSLD для определения пути от Арада до Бухареста. Первым узлом, подлежащим развёртыванию из узла Arad, является узел Sibiu, поскольку город Сибиу находится ближе к Бухаресту, чем города Зеринд или Тимишоара. Следующим узлом, подлежащим развёртыванию, является узел Fagaras, поскольку теперь ближайшим к Бухаресту является город Фэгэраш. Узел Fagaras, в свою очередь, обеспечивает формирование узла Bucharest, который является целевым.

Использованный алгоритм позволяет найти решение рассмотренной задачи без развёртывания какого-либо узла, не находящегося в пути решения. Это означает, что стоимость такого поиска является минимальной. Но само найденное решение не оптимально: путь до Бухареста через города Сибиу и Фэгэраш на 32 километра длиннее, чем через города Рымнику-Выдча и Питешти.

Процедура минимизации h(n) восприимчива к фальстартам (при её использовании иногда приходится отменять начальные этапы). Рассмотрим задачу поиска пути от города Яссы до города Фэгэраш. Эта эвристическая функция подсказывает, что в первую очередь должен быть развёрнут узел города Нямц, Heamt, поскольку он является ближайшим к узлу Fagaras , но этот путь становится тупиковым. Решение состоит в том, чтобы отправиться вначале в город Васлай (этот этап, согласно данной эвристической функции, фактически уводит дальше от цели), а затем продолжать движение через Урзичени, Бухарест и, наконец, в Фэгэраш. Поэтому в данном случае применение указанной эвристической функции вызывает развёртывание ненужных узлов. Более того, если не будет предусмотрено обнаружение повторяющихся состояний, то решение так никогда не будет найдено – процедура поиска станет совершать возвратно-поступательные движения между узлами Neamt и Iasi .

«Жадный поиск по первому наилучшему совпадению» напоминает «поиск в глубину» в том отношении, что к цели постоянно следуют по единственному пути, а возвращаются к предыдущим узлам только в случаях попадания в тупик. Поэтому данные алгоритмы не являются оптимальными. К тому же он является не полным, поскольку способен отправиться по бесконечному пути, да так и не вернуться, чтобы опробовать другие возможности. При этом в наихудшем случае оценки временной и пространственной сложности составляют O(bm), где m-максимальная глубина пространства поиска. Правильный выбор эвристической функции может существенно сократить такую сложность.


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

Поскольку функция позволяет определить стоимость пути от начального узла до го узла, а функция определяет оценку стоимости наименее дорогостоящего пути от узла до цели, то справедливо следующее утверждение:



это оценка стоимости наименее дорогостоящего пути решения, проходящего через узел .

Таким образом, при осуществлении попытки найти наименее дорогостоящее решение, разумнее всего вначале проверить узел с наименьшим значением



Если эвристическая функция удовлетворяет некоторым условиям, то поиск становится и полным, и оптимальным.

Анализ оптимальности поиска является несложным, если этот метод используется в сочетании с алгоритмом Tree-Sеarch. В таком случае поиск является оптимальным при условии, что никогда не переоценивает стоимость достижения цели. Допустимые эвристические функции являются по своей сути оптимистическими функциями, поскольку возвращают значения стоимости решения задачи, меньшие по сравнению с фактическими значениями стоимости. А поскольку точная стоимость достижения узла , из этого непосредственно следует, что функция никогда не переоценивает истинную стоимость достижения решения через узел .

Примером допустимой эвристической функции является функция определения расстояния по прямой . Поскольку кратчайший путь между любыми двумя точками определяется соединяющей эти точки прямой, возможность переоценки длины пути исключается. На рис.1 показан процесс поиска пути в Бухарест с помощью дерева. Значения вычисляются на основании стоимостей этапов, показанных на рис.1, а значения приведены в табл.1
Таблица1.Значения - расстояния по прямой до Бухареста

Обозначе-

ние узла


Название

города


Расстояние по прямой

до Бухареста




Обозначение

узла


Название

города


Расстояние

по прямой

до Бухареста


Arad

Арад

366

Mehadia

Мехадия

241

Ducharest

Бухарест

0

Ntamt

Нямц

234

Craiova

Крайова

160

Oradea

Орадия

380

Drobeta

Дробета

242

Pitesti

Питешти

100

Eforie

Эфорие

161

RimnicuVilcea

Рымнику-Вылча

193

Fagaras

Фэгэраш

176

Sibiu

Сибиу

253

Giurgiu

Джурджу

77

Timisoara

Тимишоара

329

Hirsova

Хыршова

151

Urziceni

Урзичени

80

Iasi

Яссы

226

Vaslui

Васлуй

199

Lugoj

Лугож

244

Zerind

Зиренд

374


а)Начальное состояние


366=0+366

б)После развёртывания узла Arad






393=140+253 447=118+329 449=75+374


в)После развёртывания узла Sibiu




447=118+329 449=75+374





646=280+366 415=239+176 671=291+380 413=220+193


г) После развёртывания узла Rimnicu Vilcea








447=118+329 449=75+374








646=280+366 415=239+176 671=291+380
526=366+160 417=317+100 553=300+253

д) После развёртывания узла Fagaras







447=118+329 449=75+374








591=338+253 450=450+0 526=366+160 417=317+100 553=300+253
е)После развёртывания узла Pitesti






447=118+329 449=75+374





646=280+366 671=118+329




591=338+253 450=450+0 526=366+160 553=300+253





417=417+0 615=455+160 607=414+193


Рис.1. Этапы поиска пути в Бухарест. Узлы отмечены значениями . Значения - это расстояния по прямой до Бухареста, приведенные в табл.1.
Следует отметить, что узел Bucharest впервые появляется в периферии на этапе , показанном на рис.1,д., но не выбирается для развёртывания, поскольку его -стоимость (450) выше, чем стоимость узла Pitesti (417). Эту ситуацию можно описать так, что может существовать решение, при котором путь проходит через город Питешти со стоимостью, достигающей 417, поэтому алгоритм не останавливается на решении со стоимостью 450. Приведенный пример свидетельствует, что поиск с использованием алгоритма Tree-Search является оптимальным, если функция допустима. Предположим, что на периферии поиска

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



.

Рассмотрим периферийный узел , который находится в оптимальном пути решения, например узел Pitesti (рис. 1,д). Если решение существует, то всегда должен быть такой узел. Если функция не переоценивает стоимость завершения этого пути решения, то справедлива следующая формула:



Таким образом, имеет место следующее неравенство:



поэтому узел не развёртывается и поиск должен вернуть оптимальное решение.

При организации поиска вместо алгоритма Tree-Search иногда используется алгоритм Graph-Search (алгоритм поиска в графе). Этот алгоритм получается путём модификации алгоритма Tree-Search включением в него структуры данных , называемой «закрытым списком», в котором хранится каждый развёрнутый узел.(Периферию, состоящую из неразвёрнутых узлов, иногда называют «открытым списком»). Если текущий узел совпадает с любым узлом из «закрытого списка», то не развёртывается, а отбрасывается. При решении задач с многими повторяющимися состояниями алгоритм Graph-Search является намного более эффективным по сравнению с алгоритмом Tree-Search.

Вопрос о том, оптимален ли поиск по этому алгоритму, остаётся сложным. В базовом варианте алгоритма Graph-Search всегда отбрасывается вновь обнаруженный путь и оставляется первоначальный. Очевидно, если вновь обнаруженный путь короче первоначального, то алгоритм Graph-Search упускает оптимальное решение. Этого можно избежать при использовании поиска по критерию стоимости, когда отбрасывается наиболее дорогостоящий из любых двух найденных путей к одному и тому же узлу. Сопровождение необходимой для этого дополнительной информации связано с определёнными трудностями, но гарантирует оптимальность.

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

Если представить себе треугольник, образованный узлами и целью, ближайшей к узлу , то приведенное неравенство будет соответствовать характерному для треугольника правилу: длина любой стороны треугольника не может превышать сумму длин двух других сторон.

Из определения преемственности следуют два важных вывода:

Поиск с использованием алгоритма Graph-Search является оптимальным, если функция преемственна. Эвристическая функция является преемственной, поскольку расстояние по прямой между узлами не больше

Если функция преемственна, то значения функции вдоль любого пути являются неубывающими.

Доказательство второго утверждения непосредственно вытекает из определения преемственности. Предположим, что узел преемник узла ; в таком случае для некоторого справедливо выражение и имеет место такая формула:

На основании этого можно сделать вывод, что последовательность узлов, развёрнутых в поиске с использованием алгоритма Graph-Search, находится в неубывающем порядке значений . Поэтому первый целевой узел, выбранный для развёртывания, должен представлять собой оптимальное решение, поскольку все дальнейшие узлы будут, по меньшей мере, столь же дорогостоящими.

Тот факт, что стоимости вдоль любого пути являются неубывающими, означает также, что могут быть очерчены контуры равных стоимостей в пространстве состояний, полностью аналогичные контурам равных высот на топографических картах. Внутри контура, обозначенного на рис.2 как 400, все узлы имеют значения и т.д. Поскольку в поиске развёртывается периферийный узел с наименьшей стоимостью, можно видеть, как поиск распространяется из начального узла, добавляя узлы в виде концентрических полос с возрастающей стоимостью.

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



в поиске развёртываются все узлы со значением ;

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

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

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

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

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

O


z




T

L

M

D

S

R


C

P

F

G

B

U

H

E

V

I

N

Рис.2. Карта Румынии, на которой показаны контуры, соответствующие , при условии, что Arad является начальным состоянием. Узлы в пределах данного конкретного контура имеют стоимости, меньшие или равные значению стоимости контура

420

380

400

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



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



Смотрите также:
Лекция 15 Информационный поиск и исследование пространства состояний
168.53kb.
1 стр.
Информационный поиск
123.86kb.
1 стр.
Информационный поиск в семантическом проектном репозитории
81.19kb.
1 стр.
Исследование позитронных и позитрониевых состояний в кристалле
117.35kb.
1 стр.
Отчёт за 2005 год Проект: Поиск и
42.78kb.
1 стр.
Лекция №1 2 Лекция №2 8 Лекция №3. 13 Лекция №4 14 Лекция №24 Лекция №7 24 Конспект лекций по курсу
316.67kb.
1 стр.
Лекция 4 Исчисления. Формальные системы
167.97kb.
1 стр.
Equation Chapter 1 Section 1Бифуркации Андронова-Хопфа
70.28kb.
1 стр.
Ядов В. А. Социологическое исследование: методология программа методы
3591.32kb.
26 стр.
Программа курса «физика» IV семестр
31.02kb.
1 стр.
Введение в информационный поиск
29.45kb.
1 стр.
Лекция №8 Линейные пространства
290.79kb.
1 стр.