Определение методики построения алгоритма обратного слежения

Question

Я читаю о методике разработки алгоритмов возврата. Это упоминается следующим образом.

Откат назад - это уточнение подхода грубой силы, который систематически ищет решение проблемы среди всех доступных вариантов. Он делает это, предполагая, что решения представлены векторами значений (v1, v2, ..., vm), и путем глубокого обхода сначала доменов векторов до тех пор, пока решения не будут найдены.

Мои квесты по тексту выше выглядят следующим образом.

1. Что автор подразумевает под решениями, представленными векторами?

2. Что автор подразумевает под доменами векторов?

Спасибо за разъяснения.

Answer 1

Давайте возьмем проблему восьми королев в качестве примера.

Решения представляют собой вектор из 8 позиций, по 1 на каждую ферзь. Вектор принадлежит пространству: ([0,7]x[0,7])^8, Это очень большое пространство, поэтому алгоритм обратного отслеживания будет использовать условие: "никакой ферзь не должен проверять другую ферзь", чтобы ограничиться меньшим "доменом" (подпространство ([0,7]x[0,7])^8) где существуют векторы решений.

В этом случае алгоритм создаст вектор решения, попробовав одно из допустимых значений для 1-й ферзя, задав вектор: [ (0,0), X, X, X ...], Затем, используя условие, он ограничит подпространство, в котором следует искать вторую позицию, и продолжит делать это, пока не найдет подходящий вектор.

Глубина в первую очередь означает, что перед переходом в домен для решения [ (0,1), X, X, X ...] алгоритм исчерпает все потенциальные векторы из области, определенной [ (0,0), X, X, X ...]