WikiSort.ru - Программирование

Подсчёт количества операций

Слишком зависит от конкретной ситуации, если поиск осуществляется не по n-арному дереву.

Асимптотическая сложность возрастания количества операций

• Если известны единственные конкретные начальный и целевой элементы, то временная асимптотическая сложность прямого и обратного поисков равна ${\displaystyle O(b^{d/2})}$ , следовательно общая — ${\displaystyle O(b^{d/2})}$ + ${\displaystyle O(b^{d/2})}$ , что гораздо меньше чем ${\displaystyle O(b^{d})}$ . Пространственная асимптотическая сложность ${\displaystyle O(b^{d/2})}$ , вместо — ${\displaystyle O(1)}$ у прямого, так как нужно хранить в памяти.
• Если известны конкретный начальный элемент и набор элементов, из которого один — целевой.

Статистическая оценка

Двунаправленный поиск, при заданных единственных начальном и конечном элементах, может улучшить однонаправленный поиск в ширину, обычно, в 2 раза. Наиболее сложным случаем для двунаправленного поиска является такая задача, в которой для проверки цели дано только неявное описание некоторого (возможно очень большого) множества целевых состояний, например всех состояний, соответствующих проверки цели «Мат» в шахматах. При обратном поиске потребовалось бы создать компактные описания всех состояний, которые позволяют поставить мат с помощью ходов ${\displaystyle q1,q2,q3...}$ и т. д. ; и эти описания нужно было бы сверять с состояниями, формируемыми при прямом поиске. Общего способа эффективного решения такой проблемы не существует.