На основании табл. 3.1 можно сделать два важных вывода. Прежде всего, при поиске в ширину наиболее сложной проблемой по сравнению со значительным временем выполнения является обеспечение потребностей в памяти. Затраты времени, равные 31 часу, не кажутся слишком значительными при ожидании решения важной задачи с глубиной 8, но лишь немногие компьютеры имеют терабайт оперативной памяти, который для этого требуется. К счастью, существуют другие стратегии поиска, которые требуют меньше памяти.

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

Таблица 3.1. Потребности во времени и объеме памяти для поиска в ширину. Приведенные здесь данные получены при следующих предположениях: коэффициент ветвления — Ь=10; скорость формирования — 10 000 узлов/секунда; объем памяти — 1000 байтов/узел

Поиск по критерию стоимости

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