Презентация на тему Алгоритмы с возвратом

ищем решение не по заданным
правилам вычислений, а путем проб

и ошибок. Обычно процесс проб и
ошибок разделяется на отдельные задачи, и они наиболее естественно
выражаются в терминах рекурсии и требуют исследования конечного
числа подзадач.
В общем виде весь процесс можно мыслить как процесс поиска,
строящий (и обрезающий) дерево подзадач.
Во многих проблемах такое дерево поиска растет очень быстро, рост
зависит от параметров задачи и часто бывает экспоненциальным.
Иногда, используя некоторые эвристики, дерево поиска удается
сократить и свести затраты на вычисления к разумным пределам.
Начнем с демонстрации основных методов на хорошо известном
примере — задаче о ходе коня.

на поле с координатами
(х0, у0) помещается конь —

фигура, перемещающаяся по
обычным шахматным правилам. Задача заключается в
поиске последовательности ходов, при которой конь точно
один раз побывает на всех полях доски.

хода; do
выбор очередного хода из списка возможных;

if (выбранный ход приемлем) { запись хода;
if (доска нe заполнена) {
Try(i+1); if(неудача)отменить предыдущий ход;
} }
while(неудача) && (есть другие ходы); }

для данных. Доску можно
представлять как матрицу h:

h [х, у]

= 0 – поле (х, у) еще не посещалось
h [х, у] = i – поле (х, у) посещалось на i-м ходу

результат (если ход сделан). В первом случае достаточно задавать

координаты поля (х, у), откуда следует ход, и число i, указывающее
номер хода.

Очевидно, условие «доска не заполнена» можно переписать как
i < п2.
Кроме того, если ввести две локальные переменные u и v для позиции
возможного хода, определяемого в соответствии с правилами хода
коня, то условие «ход приемлем» можно представить как
конъюнкцию условий, что новое поле находится в пределах доски
(l≤ u ≤ n && 1 ≤ v ≤ n) и еще не посещалось
h[u,v] == 0.
Отмена хода: h[u,v] = 0.

Try(i, х, у) { int u,v; int q1; инициация выбора

хода;
do - координаты следующего хода; if((1<=u)&&(u<=n)&&(1<=v)&&(v<=n)&&(h[u,v]==0)) {
h[u,v]= i; if (i q1= Try(i+1,u,v); if (!q1) h[u,v]=0;
}
else q1 = 1;
}
while(!q1) && (есть другие ходы);
q = q1;
}

остальные поля помечаются как свободные.

Если задана начальная пара координат

х, у, то для
следующего хода u, v существует максимально восемь
возможных вариантов.
Получать u, v из х, у можно, если к последним добавлять
разности между координатами, хранящиеся либо
в массиве разностей, либо в двух массивах, хранящих
отдельные разности.

от двух до восьми.
Рассмотрим вспомогательную матрицу:
Для поля

(x, y) построим последовательность ходов:
(x + D0,k, y + D1, k)     (k = 0, 1, ..., 7)  

и отберем из них те, которые не выводят за пределы поля.

в позиции (x, y). Клетки с
цифрами вокруг K -

это поля, на которые конь может переместиться из
(x, y) за один ход.

такое поле, из которого
можно совершить наименьшее число ходов на

еще не
пройденные поля. Если таких полей несколько, разрешается
выбирать любое из них.
Долгое время не было известно, справедливо ли оно.
Верно для доски от 5x5 до 76x76.

В опровержении правила Варнсдорфа для любого исходного
поля доски указаны контрпримеры, построенные с помощью
ЭВМ. Иными словами, с какого бы поля конь ни начал движение,
следуя правилу Варнсдорфа, его можно завести в тупик до
полного обхода доски.

хорошо известный пример
использования методов проб и ошибок и

алгоритмов
с возвратами. В 1850 г. эту задачу исследовал
К. Ф. Гаусс, однако полностью он ее так и не решил.
Восемь ферзей нужно расставить на шахматной доске так,
чтобы один ферзь не угрожал другому.

и В. Нужно найти
множество пар , таких, что

а  A, b В, и они удовлетворяют
некоторым условиям.
Для выбора таких пар существует много различных критериев;
один из них называется «правилом стабильных браков».
Пусть А — множество мужчин, а В — женщин. У каждых мужчины и
женщины есть различные предпочтения возможного партнера.
Если среди n выбранных пар существуют мужчины и женщины, не
состоящие между собой в браке, но предпочитающие друг друга, а не
своих фактических супругов, то такое множество браков считается
нестабильным. Если же таких пар нет, то множество считается
стабильным.

порядке списка предпочтений именно этого
мужчины.
Try(m) {
int r; for (r=0;

r запись брака; if (m - нe последний) Try(m+1); else записать стабильное множество;
} отменить брак;
}
}

и женщин: Lady и Man.
ForMan [m, r] — женщина,

стоящая на r-м месте в списке для
мужчины m.
ForLady [w, r] — мужчина, стоящий на r-м месте в списке
женщины w.
Результат — массив женщин х, где х[m] соответствует партнерше
для мужчины m.
Для поддержания симметрии между мужчинами и женщинами и
для эффективности алгоритма будем использовать дополнительный
массив у: y[w] — партнер для женщины w.

и stable, где stable — функция, которую нужно еще

определить.
Try (int m) { int r, w; for (r=0; r w=ForMan[m,r]; if (single[w] && stable) { x[m]= w; y[w]= m; single[w]=1;
if (m < n) Try(m+1);
else record set;
} single[w]=0;
}

и w, где w стоит в списке m на

r-м месте.
Возможные источники неприятностей могут быть:
1) Может существовать женщина pw, которая для
m предпочтительнее w, и для pw мужчина m
предпочтительнее ее супруга.
2) Может существовать мужчина рm, который для w
предпочтительнее m, причем для рm женщина w
предпочтительнее его супруги.

женщин, котрых m предпочитает больше w. Мы знаем,

что все эти
женщины уже были выданы замуж, иначе бы выбрали ее.
s = 1; i = 1;
while((i pw= ForMan[m,i];
i:= i+1; if(single[pw]) {
s = ForLady[pw,m] > ForLady[pw,y[pw]];
}
}
2) Нужно проверить всех кандидатов pm, которые для w предпочтительнее
«суженому». Здесь не надо проводить сравнение с мужчинами, которые
еще не женаты. Нужно использовать проверку рm предшествующие m, уже женаты.
Напишите проверку 2) самостоятельно!

Можно ли получить входную строку, прокатив кубик?

Перенумеруем грани кубика

c 123456 на 124536:
1 – нижняя;
6 – верхняя; (1+6 = 7)
3 – фронтальная;
4 – задняя; (3+4 = 7)
2 – боковая левая;
5 – боковая правая (2+5 = 7).
Тогда соседними для i-й будут все, кроме i-й и (7-i)-й.

Попробуем построить слово, начиная со всех шести граней.