Описание тега dovetailing

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

Мы можем рассматривать это дерево как аналог коллекции программ; в этом случае подход с глубиной соответствует запуску одной программы за раз, переход к следующей только после завершения текущей программы. В случае, если одна из программ работает бесконечно много времени, этот переход никогда не произойдет. Первый подход к посещению каждого ребенка на одном и том же уровне дерева соответствует "ласточкин хвост", когда для каждой программы перед переходом к следующей программе выполняется один шаг. Таким образом, прогресс достигается в каждой программе, независимо от потенциального существования программы с бесконечным временем выполнения.

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

Проверьте вики