Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 32
Текст из файла (страница 32)
(Некоторые алгоритмы могут входить в бесконечный цикл и не возвращать никакого результата.) Мы будем оценивать производительность алгоритма с помощью четырех показателей, описанных ниже. ° ж Полнота. Гарантирует ли алгоритм обнаружение решения, если оно имеется? ° ?ь Оптимальность. Обеспечивает ли данная стратегия нахождение оптимального решения, в соответствии с определением, приведенным на с. 115? ° Ъ. Временная сложность. За какое время алгоритм находит решение? ° оь Пространственная сложность. Какой объем памяти необходим для осуществления поиска? Временная и пространственная сложность всегда анализируются с учетом определенного критерия измерения сложности задачи. В теоретической компьютерной науке типичным критерием является размер графа пространства состояний, поскольку этот граф рассматривается как явно заданная структура данных, которая является входной для программы поиска.
(Примером этого может служить карта Румынии.) В искусственном интеллекте, где граф представлен неявно с помощью начального состояния и функции определения преемника и часто является бесконечным, сложность выражается в терминах трех величин: Ь вЂ” Ъ.
коэффициент ветвления или максимальное количество преемников любого узла, с[ — глубина самого поверхностного целевого узла и гп — максимальная длина любого пути в пространстве состояний. Временная сложность часто измеряется в терминах количества узлов, вырабатываемых' в процессе поиска, а пространственная сложность — в терминах максимального количества узлов, хранимых в памяти.
Чтобы оценить эффективность любого алгоритма поиска, можно рассматривать только оь стоимость поиска, которая обычно зависит от временной сложности, но может также включать выражение для оценки использования памяти, или применять 'в. суммарную стоимость, в которой объединяется стоимость поиска и стоимость пути найденного решения. Для задачи поиска маршрута от Арада до Бухареста стоимость поиска представляет собой количество времени, затраченного на этот поиск, а стоимость решения выражает общую длину пути в километрах. Поэтому для вы- ' В некоторых работах вместо этого лля измерения временной сложности применяется количество операций развертывания узлов.
Эти два критерия различаются не больше, чем на коэффициент Ь. С точки зрения авторов, время выполнения операции развертывания узла растет пропорционально количеству узлов, вырабатываемых при этом развертывании. 128 Часть П, Решение проблем Проведем оценку поиска в ширину с использованием четырех критериев, описанных в предыдущем разделе. Вполне очевидно, что этот поиск является полным— если самый поверхностный целевой узел находится на некоторой конечной глубине с(, то поиск в ширину в конечном итоге позволяет его обнаружить после развертывания всех более поверхностных узлов (при условии, что коэффициент ветвления Ь является конечным).
Самый поверхностный целевой узел не обязательно является оптимальным; формально поиск в ширину будет оптимальным, если стоимость пути выражается в виде неубывающей функции глубины узла. (Например, такое предположение оправдывается, если все действия имеют одинаковую стоимость.) До сих пор приведенное выше описание поиска в ширину не предвешало никаких неприятностей. Но такая стратегия не всегда является оптимальной; чтобы понять, с чем это связано, необходимо определить, какое количество времени и какой объем памяти требуются для выполнения поиска. Для этого рассмотрим гипотетическое пространство состояний, в котором каждое состояние имеет Ь преемников.
Корень этого дерева поиска вырабатывает Ь узлов на первом уровне, каждый из которых вырабатывает еще Ь узлов, что соответствует общему количеству узлов на втором уровне, равному Ь'. Каждый из них также вырабатывает Ь узлов, что приводит к получению Ь' узлов на третьем уровне, и т.д. А теперь предположим, что решение находится на глубине с1. В наихудшем случае на уровне с1 необходимо развернуть все узлы, кроме последнего (поскольку сам целевой узел не развертывается), что приводит к выработке Ьв"-Ь узлов на уровне с)+1. Это означает, что обшее количество выработанных узлов равно: Ь + Ь + Ь + ...
+ Ь - 1Ь -Ь1 = О(Ь ' 1 Каждый выработанный узел должен оставаться в памяти, поскольку он либо относится к периферии, либо является предком периферийного узла. Итак, пространственная сложность становится такой же, как и временная (с учетом добавления одного узла, соответствующего корню). Поэтому исследователи, выполняюшие анализ сложности алгоритма, огорчаются (или восхищаются, если им нравится преодолевать трудности), столкнувшись с экспоненциальными оценками сложности, такими как О (Ье" ) . В табл.
3.1 показано, с чем это связано. В ней приведены требования ко времени и к объему памяти при поиске в ширину с коэффициентом ветвления Ь=10 для различных значений глубины решения с1. При составлении этой таблицы предполагалось, что в секунду может быть сформировано 10 000 узлов, а для каждого узла требуется 1000 байтов памяти. Этим предположением приблизительно соответствуют многие задачи поиска при их решении на любом современном персональном компьютере (с учетом повышаюшего или понижающего коэффициента 100).
На основании табл. 3.1 можно сделать два важных вывода. Прежде всего, сд при поиске в ширину наиболее сложной проблемой по сравнению со значительным временем выполнения является обеспечение потребностей в памяти. Затраты времени, равные 31 часу, не кажутся слишком значительными при ожидании решения важной задачи с глубиной 8, но лишь немногие компьютеры имеют терабайт оперативной памяти, который для этого требуется.
К счастью, существуют другие стратегии поиска, которые требуют меньше памяти. Второй вывод состоит в том, что требования ко времени все еше остаются важным фактором. Если рассматриваемая задача имеет решение на глубине 12, то (с учетом при- Глава 3. Решение проблем посредством поиска 129 Таблица 3.1. Потребности во времени н объеме пвмяпз для понекв в шнрнну. Приведенные здесь двн- ные получены прн елелуюшнх предположениях: коэффнпнент ветвлення — в=101 скорость формнро- ввння — 1О 000 узлов/секунда; объем памяти — 1000 байтов/узел Глубина Количество узлов Время Память 1100 !мегабайт !Об мегабзйтов 10 гигабайтов 0,11 секунды 11секунд 19 минут 31 час 111 100 4 б 8 1О 12 14 10 1.0' 1 тераблйт 101 тераблйт 10 петабайтов 10" 129 суток 35 лет 10ы 10 1 эксабайт 3523 года Поиск по критерию стоимости Поиск в ширину является оптимальным, если стоимости всех этапов равны, поскольку в нем всегда развертывается самый поверхностный неразвернутый узел.
С помощью простого дополнения можйо создать алгоритм, который является оптимальным прн любой функции определения стоимости этапа. Вместо развертывания самого поверхностного узла 2к поиск по критерию стоимости обеспечивает развертывание узла п с наименьшей стоимостью пути. Обратите внимание на то, что, если стоимости всех этапов равны, такой поиск идентичен поиску в ширину. При поиске по критерию стоимости учитывается не количество этапов, имеющихся в пути, а только их суммарная стоимость.
Поэтому процедура этого поиска может войти в бесконечный цикл, если окажется, что в ней развернут узел, имеющий действие с нулевой стоимостью, которое снова указывает на то же состояние (например, действие )900р). Можно гарантировать полноту поиска при условии, что стоимость каждого этапа больше или равна некоторой небольшой положительной константе б. Это условие является также достаточным для обеспечения оптимальности. Оно означает, что стоимость пути всегда возрастает по мере прохождения по этому пути.
Из данного свойства легко определить, что такой алгоритм развертывает узлы в порядке возрастания стоимости пути. Поэтому первый целевой узел, выбранный для развертывания, представляет собой оптимальное решение. (Напомним, что в процедуре Тхее-Яеахс)г проверка цели применятся только к тем узлам, которые выбраны для развертывания.) Рекомендуем читателю попытаться воспользоваться этим алгоритмом для поиска кратчайшего пути до Бухареста.
Поиск по критерию стоимости направляется с учетом стоимостей путей, а не значений глубины в дереве поиска, поэтому его сложность не может быть легко охарактеризована в терминах Ь и г1. Вместо этого предположим, что С вЂ” стоимость оптимального решения, и допустим, что стоимость каждого действия составляет, по меньшей мере, б.
Это означает, что временная и и!(зост)занственная сложность этого алгоритма в наихудшем случае составляет 0(Ь""'), т.е. может быть намного больше, чем Ье. Это связано с тем, что процедуры поиска по критерию стоимости нятых предположений) потребуется 35 лет на поиск в ширину (а в действительности на любой неинформированный поиск), чтобы найти ее решение. Вообще говоря, «)у задачи поиска с экспаненниальнай сложностью невозможно решить с помощью неинформированных методов ва всех экземплярах этих задач, кроме самых небольших.
Глава 3. Решение проблем посредством поиска 131 Поиск в глубину имеет очень скромные потребности в памяти. Он требует хранения только единственного пути от корня до листового узла, наряду с оставшимися неразвернутыми сестринскими узлами для каждого узла пути. После того как был развернут некоторый узел, он может быть удален из памяти, коль скоро будут полностью исследованы все его потомки (см, рис, 3.8). Для пространства состояний с коэффициентом ветвления Ь и максимальной глубиной т поиск в глубину требует хранения только Ьлн-1 узлов.
Используя такие же предположения, как и в табл. 3.1, и допуская, что узлы, находящиеся на той же глубине, что и целевой узел, не имеют преемников, авторы определили, что на глубине 0=12 для поиска в глубину требуется 118 килобайтов вместо 10 петабайтов, т.е. потребность в пространстве уменьшается примерно в 1О миллиардов раз. В одном из вариантов поиска в глубину, называемом Ъ. поиском с возвратами, используется еще меньше памяти. При поиске с возвратами каждый раз формируется только один преемник, а не все преемники; в каждом частично развернутом узле запоминается информация о том, какой преемник должен быть сформирован следующим.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
