Измерение производительности решения задачи
Результатом применения любого алгоритма решения задачи является либо неудачное завершение, либо получение решения. (Некоторые алгоритмы могут входить в бесконечный цикл и не возвращать никакого результата.) Мы будем оценивать производительность алгоритма с помощью четырех показателей, описанных ниже.
• Полнота. Гарантирует ли алгоритм обнаружение решения, если оно имеется?
• Оптимальность. Обеспечивает ли данная стратегия нахождение оптимального решения, в соответствии с определением, приведенным на с. 115?
• Временная сложность. За какое время алгоритм находит решение?
• Пространственная сложность. Какой объем памяти необходим для осуществления поиска?
Временная и пространственная сложность всегда анализируются с учетом определенного критерия измерения сложности задачи. В теоретической компьютерной науке типичным критерием является размер графа пространства состояний, поскольку этот граф рассматривается как явно заданная структура данных, которая является входной для программы поиска. (Примером этого может служить карта Румынии.) В искусственном интеллекте, где граф представлен неявно с помощью начального состояния и функции определения преемника и часто является бесконечным, сложность выражается в терминах трех величин: Ъ — коэффициент ветвления или максимальное количество преемников любого узла, d — глубина самого поверхностного целевого узла и т — максимальная длина любого пути в пространстве состояний.
Временная сложность часто измеряется в терминах количества узлов, вырабатываемых в процессе поиска, а пространственная сложность — в терминах максимального количества узлов, хранимых в памяти.
Чтобы оценить эффективность любого алгоритма поиска, можно рассматривать только стоимость поиска, которая обычно зависит от временной сложности, но может также включать выражение для оценки использования памяти, или применять суммарную стоимость, в которой объединяется стоимость поиска и стоимость пути найденного решения. Для задачи поиска маршрута от Арада до Бухареста стоимость поиска представляет собой количество времени, затраченного на этот поиск, а стоимость решения выражает общую длину пути в километрах. Поэтому для вычисления суммарной стоимости нам придется складывать километры и миллисекунды. Между этими двумя единицами измерения не определен "официальный курс обмена", но в данном случае было бы резонно преобразовывать километры в миллисекунды с использованием оценки средней скорости автомобиля (поскольку для данного агента важным является именно время). Это позволяет рассматриваемому агенту найти оптимальную точку компромисса, в которой дальнейшие вычисления для поиска более короткого пути становятся непродуктивными. Описание более общей задачи поиска компромисса между различными ценностями будет продолжено в главе 16.
В данном разделе рассматриваются пять стратегий поиска, которые известны под названием неинформированного поиска (называемого также слепым поиском). Этот термин означает, что в данных стратегиях не используется дополнительная информация о состояниях, кроме той, которая представлена в определении задачи. Все, на что они способны, — вырабатывать преемников и отличать целевое состояние от нецелевого. Стратегии, позволяющие определить, является ли одно нецелевое состояние "более многообещающим" по сравнению с другим, называются стратегиями информированного поиска, или эвристического поиска; они рассматриваются в главе 4. Все стратегии поиска различаются тем, в каком порядке происходит развертывание узлов.
Поиск в ширину
Поиск в ширину — это простая стратегия, в которой вначале развертывается корневой узел, затем — все преемники корневого узла, после этого развертываются преемники этих преемников и т.д. Вообще говоря, при поиске в ширину, прежде чем происходит развертывание каких-либо узлов на следующем уровне, развертываются все узлы на данной конкретной глубине в дереве поиска.
Поиск в ширину может быть реализован путем вызова процедуры Tree-Search с пустой периферией, которая представляет собой последовательную очередь (First-In-First-Out — FIFO), гарантирующую, что прежде всего будут развернуты узлы, которые должны посещаться первыми. Иными словами, к организации поиска в глубину приводит вызов процедуры Tree-Search (problem, FIFO-Queue () ). В очереди FIFO предусмотрена вставка всех вновь сформированных преемников в конец очереди, а это означает, что поверхностные узлы развертываются прежде, чем более глубокие. На рис. 3.7 показан ход поиска в простом бинарном дереве.