Сравнение стратегий поиска.

Сравним поиск в глубину и в ширину на примере.

На входе системы имеем последовательность символов

P = {К, Т, О}

Целью работы будет построить все распознаваемые человеком последовательности и найти слово КОТ.

Примем за начальную точку – O . Дерево пространства состояний (неизменно):

 

Дерево решений при использовании поиска в ширину:

 

Дерево решений при использовании поиска в глубину:

 

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

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

Критерий

Поиск в ширину

Поиск в глубину

Время

Память

Полнота

да

где l – степень ветвления,

k – глубина поиска,

d – максимальная глубина поиска.