🗊Презентация Поиск с возвращением. Задача о ферзях. Оценка методом Монте-Карло.

Построение и анализ алгоритмов Лекция 1

Темы лекций Поиск с возвращением. Задача о ферзях. Оценка методом Монте-Карло. Метод ветвей и границ. Общая схема. Задача коммивояжера (ЗК). Метод ветвей и границ. ЗК (продолжение). Приближенные решения. Динамическое программирование. Идея и общая схема. Оптимальное умножение матриц. Динамическое программирование. Оптимальные БДП. Хорошие БДП. Аналогии.

Продолжение Графы и структуры данных. Задачи связности. Остовные деревья графа. Алгоритм Краскала. Алгоритм ЯПД. Непересекающиеся подмножества. Обходы графа. Алгоритм Борувки для МОД. МОД как приближение в ЗК. Двусвязные компоненты (применение обхода в глубину). ПВГ в орграфах. Топологическая сортировка. Сильно связные компоненты. Кратчайшие пути в графе (1). Кратчайшие пути в графе (2).

Лабораторные работы и курсовая работа Задание 1. Алгоритмы сортировки, частичного упорядочения, хеширования. Задание 2. Перебор с возвращением (Backtracking). Задание 3. Метод ветвей и границ Задание 4. Динамическое программирование.   Курсовая работа (КР): Алгоритмы на графах.

… Замечание 1. Об алгоритмах (например, сортировки) Замечание 2. О языке программирования и псевдокоде.

Исчерпывающий поиск в комбинаторных алгоритмах Поиск с возвращением = = Перебор с возвратом = = Backtracking

Стратегия поиска

Общий алгоритм Решение вида (a1, a2, a3, …, an) n – конечно, но, вообще говоря, заранее не известно ai Ai ; Ai – конечное линейно упорядоченное множество Исчерпываем все элементы множества A1A2A3…Ai i = 0  () i = 1; S1  A1; a1  S1; ()  (a1) i = 2; S2  A2; a2  S2; (a1)  (a1, a2) … i = k; Sk  Ak; ak  Sk; (a1,…, ak-1)  (a1,…, ak-1,ak) При Sk =  backtrack и новый выбор ak-1  Sk-1;

Обход дерева Прямой порядок обхода дерева. Тупики.

Общий алгоритм S1 = А1; k = 1; count = 0; while (k>0) { //пока не все решения найдены while (Sk != ) { // продвижение вперед ak = элемент из Sk; //выбор очередного элемента из Sk Sk = Sk  {ak}; count ++; if ((a1,…, ak-1,ak) – решение) { /*фиксировать решение*/} else { // переход к следующему уровню k ++; вычислить Sk; } } // end while продвижения вперед k --; // backtrack } //все решения найдены; count – число обследованных узлов

Пример задачи, решаемой алгоритмом по этой схеме

Задача о ферзях Задача о ферзях На шахматной доске размера nn расставить максимальное число не атакующих друг друга ферзей.

Продолжение

Решение (a1, a2, …, an) Ферзи i и k атакуют друг друга: i = k - ферзи на одной вертикали ai = ak - ферзи на одной горизонтали ai - ak = i - k - ферзи на одной диагонали Наращивание (продолжение) решения (a1, a2, …, ak-1)ak = (a1, a2, …, ak-1, ak )

Ak = (1, 2, …,n) – номера клеток вертикалей. Ak = (1, 2, …,n) – номера клеток вертикалей. Множество Sk явно не формируется, но, выбирая очередного кандидата k  Ak, проверяем  k  Sk Используется sk - нижняя граница в Ak, т.о. кандидаты в Sk выбираются из множества (sk, sk+1, …, n) , т.е. Sk  (sk, sk+1, …, n). Обсудить альтернативу.

Альтернативное представление Sk

Проверка s[k] bool noQueen (uns s, uns k) // ферзь не может быть поставлен в строку s столбца k { bool Flag = true; uns i = 1; while ((i<k) && Flag) { // Flag='ферзи [1..i) не атакуют поле <k,s>' // атакует ли ферзь из i-го столбца поле <k,s>?} Flag = !( (a[i]==s) || (abs(a[i]-s)== k-i) ); i++; } //end - while return (!Flag); } // end noQueen

Нахождение очередного свободного поля s[k] /*найти следующее наименьшее значение s[k], начиная с текущего s[k]; если такового нет, то s[k]=n+1 */ while ((s[k]<=n) && noQueen (s[k],k)) s[k]++;

Реализация void queen1(const uns n) { pos s; /*s[k] - наименьший элемент множества Sk неопробованных (допустимых) значений */ uns count = 0; // счетчик обследованных // узлов дерева поиска uns countS = 0; // счетчик найденых решений a[1] = 1; s[1] = 1; uns k = 1;

while (k>0) { while (k>0) { while ((k>=1) && (s[k]<=n)) { a[k]= s[k]; s[k]++; // найти следующее наименьшее значение s[k] while ((s[k]<=n) && noQueen (s[k],k)) s[k]++; count++; if (k==n) {countS++; …} //решение найдено - фиксировать ! else {// переход к следующей вертикали k++; s[k]= 1; //найти следующее наименьшее значение s[k], while ((s[k]<=n) && noQueen (s[k],k)) s[k]++; } } k--; // backtrack }

Демонстрация

Усовершенствования: пояснения к инициализации Вращения и отражения

Усовершенствования: пояснения к инициализации Вращения и отражения

Усовершенствования: пояснения к инициализации Вращения и отражения

Усовершенствования

Подсчет вариантов n=8 Все возможные способы C(n2|n)  4,4*109 В каждом столбце один nn  1,7*107 + В каждой строке один n!  4,0*104 На каждой диагонали не более одного 2056 Усовершенствования (вращения и отражения) 801

Результаты количество ферзей = 4 р е ш е н и я : 1 :: 2 4 1 3 всего вершин = 4 количество ферзей = 5 р е ш е н и я : 1 :: 2 4 1 3 5 2 :: 2 5 3 1 4 всего вершин = 11 количество ферзей = 6 р е ш е н и я : 1 :: 2 4 6 1 3 5 2 :: 3 6 2 5 1 4 всего вершин = 54

количество ферзей = 8 количество ферзей = 8 р е ш е н и я : 1 :: 2 4 6 8 3 1 7 5 2 :: 2 5 7 1 3 8 6 4 3 :: 2 5 7 4 1 8 6 3 4 :: 2 6 1 7 4 8 3 5 5 :: 2 6 8 3 1 4 7 5 6 :: 2 7 3 6 8 5 1 4 7 :: 2 7 5 8 1 4 6 3 8 :: 2 8 6 1 3 5 7 4 9 :: 3 1 7 5 8 2 4 6 10 :: 3 5 2 8 1 7 4 6 11 :: 3 5 2 8 6 4 7 1 12 :: 3 5 7 1 4 2 8 6 13 :: 3 5 8 4 1 7 2 6 14 :: 3 6 2 5 8 1 7 4 15 :: 3 6 2 7 1 4 8 5 16 :: 3 6 2 7 5 1 8 4 17 :: 3 6 4 1 8 5 7 2 18 :: 3 6 4 2 8 5 7 1 19 :: 3 6 8 1 4 7 5 2 20 :: 3 6 8 1 5 7 2 4 21 :: 3 6 8 2 4 1 7 5

количество ферзей = 9 количество ферзей = 9 р е ш е н и я : 1 :: 2 4 1 7 9 6 3 5 8 2 :: 2 4 7 1 3 9 6 8 5 3 :: 2 4 8 3 9 6 1 5 7 4 :: 2 4 9 7 3 1 6 8 5 5 :: 2 4 9 7 5 3 1 6 8 6 :: 2 5 7 1 3 8 6 4 9 7 :: 2 5 7 4 1 3 9 6 8 8 :: 2 5 7 9 3 6 4 1 8 9 :: 2 5 7 9 4 8 1 3 6 10 :: 2 5 8 1 3 6 9 7 4 11 :: 2 5 8 1 9 6 3 7 4 12 :: 2 5 8 6 9 3 1 4 7 13 :: 2 5 8 6 9 3 1 7 4 14 :: 2 5 9 4 1 8 6 3 7 15 :: 2 6 1 3 7 9 4 8 5 16 :: 2 6 1 7 4 8 3 5 9 17 :: 2 6 1 7 5 3 9 4 8 18 :: 2 6 1 9 5 8 4 7 3 19 :: 2 6 3 1 8 4 9 7 5 20 :: 2 6 9 3 5 8 4 1 7 21 :: 2 7 5 1 9 4 6 8 3 22 :: 2 7 5 8 1 4 6 3 9 23 :: 2 7 9 6 3 1 4 8 5 24 :: 2 8 1 4 7 9 6 3 5 25 :: 2 8 5 3 9 6 4 1 7 26 :: 2 8 6 9 3 1 4 7 5 27 :: 2 9 5 3 8 4 7 1 6 28 :: 2 9 6 3 5 8 1 4 7 29 :: 2 9 6 3 7 4 1 8 5 30 :: 2 9 6 4 7 1 3 5 8 31 :: 3 1 4 7 9 2 5 8 6 32 :: 3 1 6 8 5 2 4 9 7 33 :: 3 1 7 2 8 6 4 9 5

Оценка сложности выполнения Метод Монте-Карло Число исследуемых узлов дерева

Метод Монте-Карло Оценка площади фигуры (интеграла) Число точек внутри ______________________________________________ Общее число точек

Оценка размеров дерева Пример: 20 узлов, без корня 19 (количество веток)

Схема испытания При mk =Sk 0 выбор ak из Sk случайный с вероятностью 1/mk. При mk = 0 испытание заканчивается.

Схема испытания Случайная величина V = m1 + m1m2 + m1m2m3 + … + m1m2…mL Математическое ожидание E(V) = число узлов в дереве (отличных от корня) Напоминание: для случайной величины x с исходами x1, x2,…, xk и вероятностями p1, p2,…, pk математическое ожидание есть

Покажем, что E(V) = число узлов в дереве 1) функция на дереве T (не случайная)

Пример

2) Функция «индикатор», описывающая случайность 2) Функция «индикатор», описывающая случайность 1, если узел x пройден при испытании I(x) = 0, если узел x не пройден при испытании Случайное событие = «узел x пройден», а I(x)  случайная величина {0,1} Вероятность дойти до узла x = vj есть (1/m1)  (1/m2)  …  (1/mj)

Пример

Итак, покажем, что E(V) = число узлов в дереве

Общий алгоритм // Монте-Карло SV = 0; // M – число испытаний for (i = 1; i<=M; i++) { k = 1; S1 = А1; m1 = S1; Sum = 0; Prod = 1; while (mk  0) { { //продвижение вперед Prod* = mk; Sum+ = Prod; ak = случайный выбор очередного элемента из Sk; k ++; вычислить Sk и mk; } SV := SV + Sum; } // end - for V = SV/ M;

begin { MonteCarlo } begin { MonteCarlo } Randomize; n_div_2 := n div 2; all := 0; for iExp:=1 to nExp do begin { очередное испытание } m_k := n_div_2 - 1; num := Random ( m_k ) + 1; a[1] := 1+num; k := 2; prod := m_k; sum := prod; FormSk ( k, m_k, S_k ); while m_k<>0 do begin prod := prod*m_k; sum := sum + prod; num := Random ( m_k ) + 1; a[k] := S_k[num]; k := k + 1; FormSk ( k, m_k, S_k ); end {while}; all := all + sum end {for}; v := all/nExp end { MonteCarlo };

procedure FormSk ( k: Nat; var m_k: Nat0; var S_k: pos ); procedure FormSk ( k: Nat; var m_k: Nat0; var S_k: pos ); { формирует "множество" (вектор) S_k возможных ходов и его мощность m_k; если S_k пусто, то m_k=0 } var s: Nat; begin m_k := 0; for s:=1 to n do if not NoQueen( k, s) then begin { можно ставить } m_k := m_k + 1; S_k[m_k] := s end; end {FormSk};

См. файлы с результатами Queen Queen_re

Backtracking. Другие способы программирования 1. Рекурсивный подход

void backtrack (sequence a, int k) void backtrack (sequence a, int k) // a = (a1, a2, …,ak-1) – частичное решение { if (a – решение) {фиксировать a;} else { вычислить Sk; for (b  Sk ) backtrack ( postfix (a, b), k+1 ); } } // end - backtrack

2. Макрокоманды Уменьшение «накладных расходов» (все решения одной длины n) Макрокоманда CODEk: вычислить Sk; Lk: if Sk =  then goto Lk-1; ak = очередной элемент из Sk; Sk := Sk  {ak};

Цикл периода макрогенерации: for ( k = 1; k<=n; k++) CODEk; CODE1; CODE2; … … CODEk; … CODEn; фиксировать решение (a1, a2, …,an); goto Ln; L0: // конец – все решения найдены

Пентамино

Для случая 6×10 эту задачу впервые решил в 1965 году Джон Флетчер [1]. Для случая 6×10 эту задачу впервые решил в 1965 году Джон Флетчер [1]. Существует ровно 2339 различных укладок пентамино в прямоугольник 6×10, не считая поворотов и отражений целого прямоугольника, но считая повороты и отражения его частей (иногда внутри прямоугольника образуется симметричная комбинация фигур, поворачивая которую, можно получить дополнительные решения; для прямоугольника 3×20, приведённого на рисунке, второе решение можно получить поворотом блока из 7 фигур, или, иначе говоря, если поменять местами четыре фигуры, крайние слева, и одну крайнюю справа, см.предыдущий слайд).

Продолжение Для прямоугольника 5×12 существует 1010 решений, 4×15 — 368 решений, 3×20 — всего 2 решения. John G. Fletcher (1965). "A program to solve the pentomino problem by the recursive use of macros". Communications of the ACM 8, 621–623.

Мартин Гарднер

КОНЕЦ ЛЕКЦИИ КОНЕЦ ЛЕКЦИИ