Реті перебора нұсқа
Порядок перебора вариантов — это правило, по которому алгоритм решает, какую ветвь дерева вариантов проверять первой, второй и далее. Он нужен, чтобы однозначно задать ход перебора и, например, получить варианты в требуемом порядке.
В дереве возможных нұсқа каждая вершина соответствует уже сделанному выбору, а исходящие ветви — следующим возможным выборам. Для каждой вершины нужно установить, в каком порядке просматривать эти ветви. Например, если на очередном шаге можно выбрать числа 1, 2 или 3, то перебор может идти как \(1,2,3\) или как \(3,2,1\).
Как задают порядок
Чаще всего используется естественный порядок: значения рассматриваются по возрастанию. Тогда первым проверяется наименьший допустимый вариант. Если он не приводит к решению, алгоритм возвращается и пробует следующий. Такой способ часто встречается при поиске в глубину и построении нұсқа с возвратом.
Нужно перечислить все двузначные числа из цифр 1 и 2 без повторений. Сначала выбираем первую цифру в порядке \(1,2\). После выбора 1 остаётся только 2, поэтому получаем 12. Затем алгоритм возвращается к первому выбору и проверяет ветвь 2, получая 21. Порядок результатов: 12, 21.
Порядок перебора — не количество вариантов и не глубина дерева. Он определяет очередность проверки ветвей. Одно и то же дерево может обходиться в разных порядках и давать результаты в разной последовательности.
В каком порядке будут проверяться варианты, если правило требует перебирать числа по возрастанию: 2, 5, 1?
Главное
- Реті перебора задаёт последовательность проверки ветвей из каждой вершины дерева нұсқа.
- Обычно варианты проверяют слева направо или по возрастанию, но точное правило определяется условием задачи.
- Порядок перебора влияет на последовательность найденных решений, но не меняет само множество допустимых вариантов.