СТРАТЕГИИ НЕИНФОРМИРОВАННОГО ПОИСКА

Проведем оценку поиска в ширину с использованием четырех критериев, описанных в предыдущем разделе. Вполне очевидно, что этот поиск является полным — если самый поверхностный целевой узел находится на некоторой конечной глубине d, то поиск в ширину в конечном итоге позволяет его обнаружить после развертывания всех более поверхностных узлов (при условии, что коэффициент ветвления Ь является конечным). Самый поверхностный целевой узел не обязательно является оптимальным; формально поиск в ширину будет оптимальным, если стоимость пути выражается в виде неубывающей функции глубины узла. (Например, такое предположение оправдывается, если все действия имеют одинаковую стоимость.)
До сих пор приведенное выше описание поиска в ширину не предвещало никаких неприятностей. Но такая стратегия не всегда является оптимальной; чтобы понять, с чем это связано, необходимо определить, какое количество времени и какой объем памяти требуются для выполнения поиска. Для этого рассмотрим гипотетическое пространство состояний, в котором каждое состояние имеет Ъ преемников. Корень этого дерева поиска вырабатывает Ъ узлов на первом уровне, каждый из которых вырабатывает еще Ъ узлов, что соответствует общему количеству узлов на втором уровне, равному Ь2. Каждый из них также вырабатывает Ъ узлов, что приводит к получению Ь3 узлов на третьем уровне, и т.д. А теперь предположим, что решение находится на глубине d. В наихудшем случае на уровне d необходимо развернуть все узлы, кроме последнего (поскольку сам целевой узел не развертывается), что приводит к выработке bd+1-b узлов на уровне d+1. Это означает, что общее количество выработанных узлов равно:
Ъ + Ь2 + Ь3 + ... + bd + (bd+1-b) = 0(bd+1)
Каждый выработанный узел должен оставаться в памяти, поскольку он либо относится к периферии, либо является предком периферийного узла. Итак, пространственная сложность становится такой же, как и временная (с учетом добавления одного узла, соответствующего корню).
Поэтому исследователи, выполняющие анализ сложности алгоритма, огорчаются (или восхищаются, если им нравится преодолевать трудности), столкнувшись с экспоненциальными оценками сложности, такими как 0(bd+1). В табл. 3.1 показано, с чем это связано. В ней приведены требования ко времени и к объему памяти при поиске в ширину с коэффициентом ветвления Ь=10 для различных значений глубины решения d. При составлении этой таблицы предполагалось, что в секунду может быть сформировано 10 ООО узлов, а для каждого узла требуется 1000 байтов памяти. Этим предположением приблизительно соответствуют многие задачи поиска при их решении на любом современном персональном компьютере (с учетом повышающего или понижающего коэффициента 100).
На основании табл. 3.1 можно сделать два важных вывода. Прежде всего, при поиске в ширину наиболее сложной проблемой по сравнению со значительным временем выполнения является обеспечение потребностей в памяти. Затраты времени, равные 31 часу, не кажутся слишком значительными при ожидании решения важной задачи с глубиной 8, но лишь немногие компьютеры имеют терабайт оперативной памяти, который для этого требуется. К счастью, существуют другие стратегии поиска, которые требуют меньше памяти.
Второй вывод состоит в том, что требования ко времени все еще остаются важным фактором. Если рассматриваемая задача имеет решение на глубине 12, то (с учетом принятых предположений) потребуется 35 лет на поиск в ширину (а в действительности на любой неинформированный поиск), чтобы найти ее решение. Вообще говоря, сё3 задачи поиска с экспоненциальной сложностью невозможно решить с помощью неинформированных методов во всех экземплярах этих задач, кроме самых небольших.
Таблица 3.1. Потребности во времени и объеме памяти для поиска в ширину. Приведенные здесь данные получены при следующих предположениях: коэффициент ветвления — Ь=10; скорость формирования — 10 ООО узлов/секунда; объем памяти — 1000 байтов/узел







Материалы

Яндекс.Метрика