Презентация на тему Алгоритмы с возвратом. (Лекция 9)

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

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

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

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

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

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

[х][ у] = 0 – поле (х, у) еще

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

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

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

Отмена хода: h[u][v] = 0.
Введем локальную переменную q для результата.

{ int u,v; int q = 0; инициация выбора хода; do

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

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

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

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

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

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

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

на еще не пройденные поля. Если таких полей несколько, разрешается выбирать любое из них.
Долгое время не было известно, справедливо ли оно.
Верно для доски от 5x5 до 76x76.
Опровержение правила Варнсдорфа: для любого исходного поля доски указаны контрпримеры, построенные с помощью ЭВМ. Иными словами, с какого бы поля конь ни начал движение, следуя правилу Варнсдорфа, его можно завести в тупик до полного обхода доски.

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

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

m – количество вариантов на каждом шаге)
Try(int i)

{
int k;
for (k = 1; k <= m; k++)
{
выбор k-го кандидата; if (подходит)
{ его запись; if (i < n) Try(i+1); else печатать решение;
стирание записи ;
}
}
}

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

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

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

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

партнеров для мужчин и женщин: ForLady и ForMan.
ForMan

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

single и 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]=0;
if (m < n) Try(m+1);
else record set;
} single[w]=1;
}
}

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

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

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

что все эти
женщины уже были выданы замуж, иначе бы выбрали ее.
stable = 1; i = 1;
while((i pw = ForMan[m][i];
i = i+1; if(!single[pw]) {
stable = (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)-й.

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

получить слово, записанное в глобальной строке w, начиная n-го

символа, перекатывая кубик, лежащий g-ой гранью.

int chkword(g, n) {
if((n>strlen(w)) || (w[n]== ‘ ‘))
return 1;
if(CB[g] != w[n]) break;
for(i=1; i<=6; i++) {
if((i != g) && (i+g != 7))
q=chkwrd(i,n+1);
if (q) return 1;
}
return 0;
}

вещей {x1, x2, x3, …xn}.
Каждая i-я вещь имеет свой

вес wi, и свою стоимость ci.
Нужно из этого множества выбрать такой набор вещей, что их общий вес не превышал бы заданного числа K, а их общая стоимость была бы максимальной.
ti = 0, если вещь не взята, и
ti = 1, иначе.

{
if (включение приемлемо)
{ включение i-го объекта; if (i < n)

Try(i+1); else проверка оптимальности;
исключение i-го объекта;
}
if (приемлемо невключение )
{ if (i < n) Try(i+1); else проверка оптимальности;
}
}

оптимальных решений различных задач оптимизации. Метод — есть вариация

полного перебора с отсечением подмножеств допустимых решений, заведомо не содержащих оптимальных решений.
Впервые метод ветвей и границ был предложен Лендом и Дойгом в 1960 для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его “второе рождение” связано с работой Литтла, Мурти, Суини и Кэрела, посвященной задаче коммивояжера. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям.

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

размеров. Процедуру можно рекурсивно применять к полученным подмножествам. Эти подмножества образуют дерево, называемое деревом поиска или деревом ветвей и границ. Узлами этого дерева являются построенные подмножества.
На каждом шаге разбиения осуществляется проверка того, содержит ли данное подмножество оптимальное решение или нет. Проверка осуществляется посредством вычисления оценок снизу и сверху для целевой функции на данном подмножестве. Если для пары подмножеств получается такая ситуация, что нижняя граница для первого подмножества дерева поиска больше, чем верхняя граница для второго подмножества, то тогда первое подмножество можно исключить из дальнейшего рассмотрения.
Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является минимумом функции и достигается на соответствующем подмножестве.

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

из полученных к этому времени решений. Процедура Try вызывается рекурсивно для исследования очередного объекта до тех пор, пока все объекты не будут рассмотрены. При этом возможны два заключения: либо включать объект в текущую выборку, либо не включать. Оба варианта должны быть рассмотрены.
Пусть opts – оптимальная выборка, полученная к данному моменту,
maxv – ее ценность, t – текущая выборка.
Объект можно включать в выборку, если он подходит по весовым ограничениям.
Критерием неприемлимости будет то, что после данного исключения общая ценность выборки будет не меньше полученного до этого момента оптимума.