84
правки
Изменения
→Задача о нахождении кратчайшего расстояния между двумя вершинами в графе
[[Файл:bfs.png|600px|thumb|right|Нахождение кратчайшего расстояния между двумя вершинами]]
Еще одна задача, решаемая '''Meet-in-the-middle''' — это нахождение кратчайшего расстояния между двумя вершинами, зная начальное состояние, конечное состояние и то, что длина оптимального пути не превышает <tex> N </tex>.
Стандартным подходом для решения данной задачи, является применение алгоритма [[Обход в ширину|обхода в ширину]]. Пусть из каждого состояния у нас есть <tex> K </tex> переходов, тогда бы мы сгенерировали <tex> {K^{N}} </tex> состояний. Асимптотика данного решения составила бы <tex> {O({K^{N}})} </tex>. '''Meet-in-the-middle''' помогает снизить асимптотику до <tex> {O({K^{\frac{N/}{2}}})} </tex>. <br>
=== Алгоритм решения ===
Таким образом, '''BFS-ом''' из двух концов, мы сгенерируем максимум <tex> {O({K^{\frac{N/}{2}}})} </tex> состояний.
== См. также ==
