 | В этой статье не процитировать какие - либо источники . ( декабрь 2009 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
Ласточкин хвост , в алгоритме конструкции , является метод , который переплетается различные вычисления , выполняя их по существу , одновременно. Алгоритмы, использующие «ласточкин хвост», иногда называют « ласточкин хвост» .
Рассмотрим дерево, которое потенциально содержит путь бесконечной длины: если в этой среде выполняется поиск в глубину , поиск может двигаться вниз по бесконечному пути и никогда не возвращаться, потенциально оставляя часть дерева неисследованной. Однако, если используется поиск в ширину , существование бесконечного пути больше не является проблемой: каждый узел посещается с ветвлением в соответствии с его расстоянием от корня, поэтому бесконечный путь повлияет только на часть пути. поиск по этому пути.
Мы можем рассматривать это дерево как аналог набора программ; в этом случае подход «сначала в глубину» соответствует запуску одной программы за раз, переход к следующей только после завершения текущей программы. В случае, если одна из программ работает бесконечно долго, этот переход никогда не произойдет. Подход «вширь», заключающийся в посещении каждого дочернего элемента на одном уровне дерева, соответствует принципу «ласточкин хвост», когда для каждой программы выполняется один шаг перед переходом к следующей. Таким образом, прогресс достигается в каждой программе, независимо от потенциального существования программы с бесконечным временем выполнения.
В случае бесконечного числа программ, потенциально бесконечно длинных, ни принципа в ширину, ни в глубину не будет достаточно для обеспечения прогресса по всем программам. Вместо этого можно использовать следующую технику: выполнить первый шаг первой программы; затем выполните первый шаг второй программы и второй шаг первой программы; затем выполните первый шаг третьей программы, второй шаг второй программы и третий шаг первой программы; и так далее.
- Примечание: мы могли бы согласовать механизмы комбинирования алгоритмов по принципу «сначала в глубину» (без «ласточкин хвост») и в ширину («ласточкин хвост»). Это рекурсивное применение алгоритма «ласточкин хвост» к самому себе приводит к бесконечному количеству новых алгоритмов, каждый из которых требует немного меньшего полного согласования.
Этимология [ править ]
- Аналогия с переплетением концов соединения « ласточкин хвост» в деревообработке .
См. Также [ править ]
