![]() |
![]() |
Начальное состояние - состояние, с которого агент начинает решение задачи.
Пространство состояний - множество всех состояний, достижимых из начального с помощью всех допустимых последовательностей действий. Последовательность вершин, ведущих из начального состояния в другое в данном пространстве состояний, называется путем. Длиной пути будем называть количество вершин на этом пути.
Процесс нахождения целевого состояния называют стратегией поиска цели или поиском цели. Существует большое число различных стратегий поиска целей. Среди них следующие:
Стратегии слепого поиска: поиск в ширину, монотонный поиск в ширину, поиск в глубину, ограниченный поиск в глубину, итеративный поиск в глубину, двунаправленный поиск;
Стратегии направленного поиска: поиск по критерию близости к цели, поиск по критерию цены пути, оптимизирующий итеративный поиск.
Поиск начинается с корневой вершины, определяются все последователи корневой вершины, затем все последователи последователей и т.д., пока не будут найдены все вершины, соответствующие целевым состояниям.
Если полагать что число последователей каждой вершины l , то число вершин S при глубине поиска k равно:
При конкретных значениях l и k по этой формуле вычисляется максимальное число вершин дерева поиска.
Для оценки памяти и времени, требуемых при поиске, применяется экспоненциальная оценка:
![]() |
![]() |