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

Нажмите для полного просмотра!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Поиск с возвращением. Задача о ферзях. Оценка методом Монте-Карло.. Доклад-сообщение содержит 54 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

Общий алгоритм Решение вида (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;

Слайд 9

Описание слайда:

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

Слайд 10

Описание слайда:

Общий алгоритм 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 – число обследованных узлов

Слайд 11

Описание слайда:

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

Слайд 12

Описание слайда:

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

Слайд 13

Описание слайда:

Продолжение

Слайд 14

Описание слайда:

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

Слайд 15

Описание слайда:

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). Обсудить альтернативу.

Слайд 16

Описание слайда:

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

Слайд 17

Описание слайда:

Проверка s[k] bool noQueen (uns s, uns k) // ферзь не может быть поставлен в строку s столбца k { bool Flag = true; uns i = 1; while ((i

Слайд 18

Описание слайда:

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

Слайд 19

Описание слайда:

Реализация 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;

Слайд 20

Описание слайда:

while (k>0) { while (k>0) { while ((k>=1) && (s[k]

Слайд 21

Описание слайда:

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

Слайд 22

Описание слайда:

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

Слайд 23

Описание слайда:

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

Слайд 24

Описание слайда:

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

Слайд 25

Описание слайда:

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

Слайд 26

Описание слайда:

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

Слайд 27

Описание слайда:

Результаты количество ферзей = 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

Слайд 28

Описание слайда:

количество ферзей = 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

Слайд 29

Описание слайда:

количество ферзей = 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

Слайд 30

Описание слайда:

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

Слайд 31

Описание слайда:

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

Слайд 32

Описание слайда:

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

Слайд 33

Описание слайда:

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

Слайд 34

Описание слайда:

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

Слайд 35

Описание слайда:

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

Слайд 36

Описание слайда:

Пример

Слайд 37

Описание слайда:

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

Слайд 38

Описание слайда:

Пример

Слайд 39

Описание слайда:

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

Слайд 40

Описание слайда:

Общий алгоритм // Монте-Карло SV = 0; // M – число испытаний for (i = 1; i

Слайд 41

$begin { MonteCarlo } begin { MonteCarlo } Randomize; n_div_2 := n div 2; all := 0; for iExp:=1 to nExp do begin { очередное испытание } m_k :=...$

Описание слайда:

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_k0 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 };

Слайд 42

$procedure FormSk ( k: Nat; var m_k: Nat0; var S_k: pos ); procedure FormSk ( k: Nat; var m_k: Nat0; var S_k: pos ); { формирует "множество"...$

Описание слайда:

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};

Слайд 43

Описание слайда:

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

Слайд 44

Описание слайда:

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

Слайд 45

Описание слайда:

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

Слайд 46

Описание слайда:

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

Слайд 47

Описание слайда:

Цикл периода макрогенерации: for ( k = 1; k

Слайд 48

Описание слайда:

Пентамино

Слайд 49

Описание слайда:

Слайд 50

Описание слайда:

Слайд 51

Описание слайда:

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

Слайд 52

Описание слайда:

Продолжение Для прямоугольника 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.