Содержание
- 2. Темы лекций Поиск с возвращением. Задача о ферзях. Оценка методом Монте-Карло. Метод ветвей и границ. Общая
- 3. Продолжение Графы и структуры данных. Задачи связности. Остовные деревья графа. Алгоритм Краскала. Алгоритм ЯПД. Непересекающиеся подмножества.
- 4. Лабораторные работы и курсовая работа Задание 1. Алгоритмы сортировки, частичного упорядочения, хеширования. Задание 2. Перебор с
- 5. … Замечание 1. Об алгоритмах (например, сортировки) Замечание 2. О языке программирования и псевдокоде. 10.02.2014 Поиск
- 6. 10.02.2014 Поиск с возвращением Исчерпывающий поиск в комбинаторных алгоритмах Поиск с возвращением = = Перебор с
- 7. 10.02.2014 Поиск с возвращением Стратегия поиска с в ю з с→в→ю→з Направление = (с, в, ю,
- 8. 10.02.2014 Поиск с возвращением Общий алгоритм Решение вида (a1, a2, a3, …, an) n – конечно,
- 9. 10.02.2014 Поиск с возвращением Обход дерева Прямой порядок обхода дерева. Тупики. Выбор a1 Выбор a2 Выбор
- 10. 10.02.2014 Поиск с возвращением Общий алгоритм S1 = А1; k = 1; count = 0; while
- 11. Пример задачи, решаемой алгоритмом по этой схеме 10.02.2014 Поиск с возвращением
- 12. 10.02.2014 Поиск с возвращением Задача о ферзях На шахматной доске размера n×n расставить максимальное число не
- 13. 10.02.2014 Поиск с возвращением Продолжение Решение = (2, 4, 1, 3) Решение = (a1, a2, a3,
- 14. 10.02.2014 Поиск с возвращением Решение (a1, a2, …, an) Ферзи i и k атакуют друг друга:
- 15. 10.02.2014 Поиск с возвращением Ak = (1, 2, …,n) – номера клеток вертикалей. Множество Sk явно
- 16. 10.02.2014 Поиск с возвращением Альтернативное представление Sk Горизонталей = n Диагоналей = 2(2n – 1)
- 17. 10.02.2014 Поиск с возвращением Проверка s[k] bool noQueen (uns s, uns k) // ферзь не может
- 18. 10.02.2014 Поиск с возвращением Нахождение очередного свободного поля s[k] /*найти следующее наименьшее значение s[k], начиная с
- 19. 10.02.2014 Поиск с возвращением Реализация void queen1(const uns n) { pos s; /*s[k] - наименьший элемент
- 20. 10.02.2014 Поиск с возвращением while (k>0) { while ((k>=1) && (s[k] a[k]= s[k]; s[k]++; // найти
- 21. Демонстрация 10.02.2014 Поиск с возвращением
- 22. 10.02.2014 Поиск с возвращением Усовершенствования: пояснения к инициализации Вращения и отражения 2 4 1 3 5
- 23. 10.02.2014 Поиск с возвращением Усовершенствования: пояснения к инициализации Вращения и отражения 2 4 1 3 5
- 24. 10.02.2014 Поиск с возвращением Усовершенствования: пояснения к инициализации Вращения и отражения 2 4 1 3 5
- 25. Усовершенствования 10.02.2014 Поиск с возвращением void queen1(const uns n) {pos s; //s[k] - наименьший элемент множества
- 26. 10.02.2014 Поиск с возвращением Подсчет вариантов n=8 Все возможные способы C(n2|n) ≈ 4,4*109 В каждом столбце
- 27. 10.02.2014 Поиск с возвращением Результаты количество ферзей = 4 р е ш е н и я
- 28. 10.02.2014 Поиск с возвращением количество ферзей = 8 р е ш е н и я :
- 29. 10.02.2014 Поиск с возвращением количество ферзей = 9 р е ш е н и я :
- 30. 10.02.2014 Поиск с возвращением Оценка сложности выполнения Метод Монте-Карло Число исследуемых узлов дерева - мощность множества
- 31. 10.02.2014 Поиск с возвращением Метод Монте-Карло Оценка площади фигуры (интеграла) Число точек внутри ______________________________________________ Общее число
- 32. 10.02.2014 Поиск с возвращением Оценка размеров дерева Пример: 20 узлов, без корня 19 (количество веток) 2+2*3+2*3*4=32
- 33. 10.02.2014 Поиск с возвращением Схема испытания При mk =⏐Sk⏐≠ 0 выбор ak из Sk случайный с
- 34. 10.02.2014 Поиск с возвращением Схема испытания Случайная величина V = m1 + m1m2 + m1m2m3 +
- 35. 10.02.2014 Поиск с возвращением Покажем, что E(V) = число узлов в дереве 1) функция на дереве
- 36. 10.02.2014 Поиск с возвращением Пример μ(a) = 1, μ(b) = μ(c) = 2, μ(d) = μ(e)
- 37. 10.02.2014 Поиск с возвращением 2) Функция «индикатор», описывающая случайность 1, если узел x пройден при испытании
- 38. 10.02.2014 Поиск с возвращением Пример 1/24 1/24 1/24
- 39. 10.02.2014 Поиск с возвращением Итак, покажем, что E(V) = число узлов в дереве
- 40. 10.02.2014 Поиск с возвращением Общий алгоритм // Монте-Карло SV = 0; // M – число испытаний
- 41. 10.02.2014 Поиск с возвращением begin { MonteCarlo } Randomize; n_div_2 := n div 2; all :=
- 42. 10.02.2014 Поиск с возвращением procedure FormSk ( k: Nat; var m_k: Nat0; var S_k: pos );
- 43. 10.02.2014 Поиск с возвращением См. файлы с результатами Queen Queen_re
- 44. 10.02.2014 Поиск с возвращением Backtracking. Другие способы программирования 1. Рекурсивный подход k − 1 k void
- 45. 10.02.2014 Поиск с возвращением void backtrack (sequence a, int k) // a = (a1, a2, …,ak-1)
- 46. 10.02.2014 Поиск с возвращением 2. Макрокоманды Уменьшение «накладных расходов» (все решения одной длины n) Макрокоманда CODEk:
- 47. 10.02.2014 Поиск с возвращением Цикл периода макрогенерации: for ( k = 1; k CODE1; CODE2; …
- 48. 10.02.2014 Поиск с возвращением Пентамино
- 49. 10.02.2014 Поиск с возвращением Пентамино
- 50. 10.02.2014 Поиск с возвращением
- 51. 10.02.2014 Поиск с возвращением Для случая 6×10 эту задачу впервые решил в 1965 году Джон Флетчер
- 52. 10.02.2014 Поиск с возвращением Продолжение Для прямоугольника 5×12 существует 1010 решений, 4×15 — 368 решений, 3×20
- 53. 10.02.2014 Поиск с возвращением Мартин Гарднер
- 55. Скачать презентацию