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

Question

Я читаю о методе проектирования алгоритма обратного отслеживания. Об этом говорится ниже.

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

Мои quesitons над текстом выше.

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

2. Что подразумевает автор под областями векторов?

Благодарим за разъяснения.

Answer 1

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

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

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

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