Методы упорядоченного перебора на дереве вариантов решений (задача комивояжера).

стратегия волнового ветвления- активная вершина ищется среди всех висячих вершин всех уровней декомпозиции (где активная вершина –вершина ДВР, выбранная в данный момент для ветвления по некоторому правилу).

стратегия лучевого ветвления- активная вершина ищется среди всех висячих вершин последнего образовавшегося уровня декомпозиции ;после ''прохода по лучу'' до последнего уровня декомпозиции активная вершина определяется на ближащем снизу уровне декомпозиции; далее снова ''проход по лучу'' и т.д.

лучеволновая стратегия - сначала «проход по лучу» до последнего уровня декомпозиции, а затем активная вершина ищется среди всех висячих вершин всех уровней декомпозиции, а далее снова «проход по лучу».

По правилу, выбранному в соответствии со стратегией ветвления, каждый раз определяется подмножество вершин ,среди которых выбирается вершина нижней границы оценки (НГ).Верхняя граница оценки (ВГ) ограничивает решение сверху. В данном случае ВГ1соответствует первому полученному решению. ВГ может пересчитываться , если получается очередное решение, имеющее НГ меньше, чем ВГ1, тогда ВГ2=НГ. Критерием прекращения поиска решения является ситуация ,когда нет ни одной висячей вершины с НГ, меньшей, чем ВГ текущей (НГ< ВГтек.).

Еще один тип задач: поиск минимального пути в сети.