BFS с постоянным объемом памяти
Можно ли выполнить поиск с первым дыханием, используя только (размер графика) + постоянный объем памяти - другими словами, без записи, какие узлы уже были посещены?
1 ответ
Решение
Нет. Вам всегда нужно помнить, где вы побывали. Следовательно, в худшем случае вам нужно записать посещенное состояние всех узлов. Тем не менее, фактор ветвления и глубина графика являются основными факторами. Если график не сильно разветвляется, вам не нужно ничего подобного. Если он сильно разветвлен, вы склонны к худшему случаю.