May, 1966. Глава
May, 1966.
Глава 2. ПЕРЕБОР И МЕТОДЫ ЕГО СОКРАЩЕНИЯ
2.1. Перебор с возвратом
2.1.1. Общая схема
Даны N упорядоченных множеств U1, U2, ..., UN (N - известно), и требуется построить вектор A=(a1, a2, ..., aN), где a1?U1, a2?U2, ..., aN?UN, удовлетворяющий заданному множеству условий и ограничений.
В алгоритме перебора вектор А строится покомпонентно слева направо. Предположим, что уже найдены значения первых (k-1) компонент, А=(а1, а2, ..., а(k-1), ?, ..., ?), тогда заданное множество условий ограничивает выбор следующей компоненты аk некоторым множеством Sk?Uk. Если Sk<>[ ] (пустое), мы вправе выбрать в качестве аk наименьший элемент Sk и перейти к выбору (k+1) компоненты и так далее. Однако если условия таковы, что Sk оказалось пустым, то мы возвращаемся к выбору (k-1) компоненты, отбрасываем а(k-1) и выбираем в качестве нового а(k-1) тот элемент S(k-1), который непосредственно следует за только что отброшенным. Может оказаться, что для нового а(k-1) условия задачи
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
