![]() |
![]() |
Сравним поиск в глубину и в ширину на примере.
На входе системы имеем последовательность символов
P = {К, Т, О}
Целью работы будет построить все распознаваемые человеком последовательности и найти слово КОТ.
Примем за начальную точку – O . Дерево пространства состояний (неизменно):
Дерево решений при использовании поиска в ширину:
Дерево решений при использовании поиска в глубину:
Алгоритм поиска в ширину отыскивает решение, путь к которому кратчайший, если оно существует (это кратчайший путь между исходным состоянием и решением). Алгоритмы, обладающие такими свойствами, называются разрешимыми.
Поиск в глубину может быстрее найти решение, особенно если используются эвристики для выбора очередной ветки, но алгоритм может никогда не закончиться, если пространство состояний неограниченно.
Критерий |
Поиск в ширину |
Поиск в глубину |
Время |
|
|
Память |
|
|
Полнота |
да |
– |
где l – степень ветвления,
k – глубина поиска,
d – максимальная глубина поиска.
![]() |
![]() |