Главная arrow книги arrow Копия Глава 3. Решение проблем посредством поиска arrow Резюме
Резюме

•    При поиске в глубину для развертывания выбирается самый глубокий неразвернутый узел в дереве поиска. Этот поиск не является ни полным, ни оптимальным, и характеризуется временной сложностью и пространственной сложностью О (bт), где т— максимальная глубина любого пути в пространстве состояний.

•    При поиске с ограничением глубины на поиск в глубину налагается установленный предел глубины.

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

•    Двунаправленный поиск способен чрезвычайно уменьшить временную сложность, но он не всегда применим и может потребовать слишком много пространства.

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

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