Презентация «Основы программирования. Комбинаторные алгоритмы»

Вы можете ознакомиться с презентацией онлайн, просмотреть текст и слайды к ней, а также, в случае, если она вам подходит - скачать файл для редактирования или печати. Документ содержит 20 слайдов и доступен в формате ppt. Размер файла: 794.37 KB

Просмотреть и скачать

Pic.1

Основы программирования Комбинаторные алгоритмы

Pic.2

Комбинаторные алгоритмы Исследуемые объекты представлены дискретными математическими структурами (множествами, графами). Требуется найти ответ на вопросы типа: существует ли способ… сколько …

Pic.3

Перестановки Пример комбинаторной задачи: нахождение всех перестановок натуральных чисел от 1 до n: 1) первое число – любое из чисел 1, …, n; 2) второе число – любое из чисел 1, …, n, кроме первого …

Pic.4

Дерево решений для n=3

Pic.5

Перестановки В реальных задачах могут потребоваться различные перестановки n произвольных объектов. Для этого проще всего использовать «косвенный» метод: переставлять местами не сами объекты, а их …

Pic.6

Алгоритм генерации всех перестановок В алгоритме используются 2 массива (их проще сделать глобальными, чтобы постоянно не передавать параметры в рекурсивную функцию): целочисленный массив Per длины n …

Pic.7

Алгоритм генерации всех перестановок void permut(int k) { for (int i = 0; i < n; i++) if (!Inc[i]) { Per[k] = i; Inc[i] = true; if (k == n-1) OUTPUT_PERMUTATION(); else permut(k+1); Inc[i] = …

Pic.8

Сочетания Сочетания из n элементов по m – это всевозможные подмножества элементов множества длины n. Порядок расположения элементов не важен, т. е. при использовании их номеров и m=3 …

Pic.9

Алгоритм генерации всех сочетаний void combinat(int k) { int i = (!k)? 0 : Comb[k-1]+1; for (; i <= n-m+k; i++) { Comb[k] = i; if (k == m-1) OUTPUT_COMBINATION(); else combinat(k+1); } } Вызов: …

Pic.10

Задача о ферзях Пример для доски 4x4

Pic.11

Задача о ферзях Основные требования при поиске решения любой комбинаторной задачи: найти удобную форму для представления информации; найти эвристики (совокупности приемов и правил решения …

Pic.12

Задача о ферзях с учетом горизонталей и диагоналей – для элементов на одной диагонали константами являются величины: (№ столбца – № строки) (№ столбца + № строки) Для 8 ферзей проверяется всего …

Pic.13

Гамильтоновы циклы и пути Гамильтонов цикл в неориентированном графе: начинается в произвольной вершине a проходит по ребрам через все вершины графа по одному разу завершается в вершине a. Если в …

Pic.14

Гамильтоновы циклы и пути Любой гамильтонов цикл/путь задается некоторой перестановкой номеров вершин графа. Получать все перестановки, а затем проверять, не соответствуют ли они некоторому пути в …

Pic.15

Алгоритм поиска всех гамильтоновых циклов void MGraph::ham_loops(int k) { int i, j; for (i = 0; i < vernum; i++) if (!Inc[i] && mat[Path[k-1]][i]) { Path[k] = i; Inc[i] = true; if (k == …

Pic.16

Обертка для рекурсивной функции Для метода ham_loops необходимо заранее подготовить 2 массива и задать начальную вершину пути. Поэтому ham_loops лучше сделать приватным методом и добавить …

Pic.17

Формализация комбинаторных задач Общие условия: задано – множество элементов решения решение , – это обычно не просто подмножество , а комплекс, в котором важен порядок следования элементов множество …

Pic.18

Бэктрекинг (поиск с возвратом) Полное решение формируется рекурсивно на основе последовательности частичных решений , ,…, : при очередном рекурсивном вызове к текущему частичному решению добавляется …

Pic.19

Общий вид алгоритма поиска с возвратом Пусть S – текущее решение, M – множество элементов решений, a – один из эл-тов M): поиск(S) { while (существует_подходящий_элемент(M,S,a)) { …

Pic.20

Метод решета Производится не последовательный расчет допустимых решений, а исключение вариантов, которые не являются решениями (если таких много и они исключаются просто). Решето Эратосфена для …

Скачать презентацию

Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!