Лекция 14 Стратегия неинформационного поиска



Скачати 93.97 Kb.
Дата конвертації27.12.2016
Розмір93.97 Kb.




Лекция 14

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

14.1. Поиск в ширину

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

Поиск в ширину можно реализовать путём вызова процедуры Tree-Search (дерево поиска) с пустой периферией, которая представляет собой последовательную очередь (First-In-First-OutFIFO), гарантирующую первоочередное развёртывание узлов, которые должны посещаться первыми. В очереди FIFO предусматривается вставка всех вновь сформированных преемников в конец очереди, а это означает, что поверхностные узлы развёртываются прежде, чем более глубокие. На рис.14.1 показан ход поиска в простом бинарном дереве.

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

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







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

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

(14.1)

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

При составлении этой таблицы предполагалось, что в секунду формируется 10000 узлов, а для каждого узла требуется 100 байтов памяти.
Таблица 14.1. Оценки потребности во времени и объёме памяти для стратегии поиска в ширину, полученные при следующих начальных условиях: коэффициент ветвления ; скорость формирования узлов/секунда; объём памяти байтов/узел


Глубина

Количество узлов

Время

Память

2

1100

0,11 секунды

1 мегабайт

4

111100

11 секунд

106 мегабайтов

6



19 минут

10 гигабайтов

8



31 час

1 терабайт

10



129 суток

101 терабайт

На основании данных таблицы 14.1 можно сделать вывод о том, что при использовании стратегии поиска в ширину наиболее сложной проблемой является обеспечение потребности в памяти. Так при ожидании решения важной задачи с глубиной 8 затраты времени, равные 31 часу, не кажутся значительными, но лишь немногие компьютеры имеют терабайт оперативной памяти. К счастью, существуют другие стратегии поиска, которые требуют меньший объём памяти.

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

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

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

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


14.3.Поиск со скольжением в глубину дерева

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

Эту стратегию можно реализовать в процедуре Tree-Search-поиск по дереву – любой метод поиска фрагмента данных с помощью очереди LIFO (Last-In-First-Out).

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












Рис.14.2.Ход поиска в глубину в бинарном дереве. Узлы, которые были развёрнуты и не имеют потомков в этой периферии, могут быть удалены из памяти; эти узлы обозначены чёрным цветом. Предполагается, что узлы на глубине 3 не имеют преемников и единственным целевым узлом является М.

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

Процедура поиска в глубину характеризуется скромными потребностями в памяти - необходимо хранить информацию для единственного пути от корня до листового узла, наряду с оставшимися неразвёрнутыми сестринскими узлами для каждого узла пути. После развёртывания некоторого узла, он может быть удалён из памяти, поскольку были полностью исследованы все его потомки (см. рис.14.2). Для пространства состояний с коэффициентом ветвления и максимальной глубиной процедура поиска в глубину требует хранения только узлов. Используя такие же предположения, как и в табл.14.1, и допуская, что узлы, находящиеся на той же глубине, что и целевой узел, не имеют преемников, получаем, что при глубине для поиска в глубину требуется 80 килобайт вместо 1 терабайта, т.е. потребность в пространстве уменьшается примерно в 10 миллионов раз.

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

преемник должен быть развёрнут следующим. Таким образом, требуется только памяти, а не .

Недостатком поиска в глубину является то, что в нём может быть сделан неправильный выбор и переход в тупиковую ситуацию, связанную с прохождением вниз по очень длинному (или даже бесконечному пути) пути, в то время как другой вариант мог бы привести к решению, находящемуся недалеко от корня дерева поиска. Например, на рис.14.2 процедура поиска в глубину потребовала бы исследования всего левого поддерева, даже если бы целевым узлом был узел , находящийся в правом поддереве. Если же целевым узлом был также узел , менее приемлемый по сравнению с узлом , то процедура поиска в глубину возвратила бы в качестве решения именно его. Это означает, что процедура поиска в глубину не является оптимальной. Кроме того, при неограниченной глубине левого поддерева, когда оно не содержит решения, процедура поиска в глубину является бесконечной во времени, т.е. данный алгоритм - не полный.

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

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

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






База даних захищена авторським правом ©lecture.in.ua 2016
звернутися до адміністрації

    Головна сторінка