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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Основы программирования. Комбинаторные алгоритмы, слайд №1Основы программирования. Комбинаторные алгоритмы, слайд №2Основы программирования. Комбинаторные алгоритмы, слайд №3Основы программирования. Комбинаторные алгоритмы, слайд №4Основы программирования. Комбинаторные алгоритмы, слайд №5Основы программирования. Комбинаторные алгоритмы, слайд №6Основы программирования. Комбинаторные алгоритмы, слайд №7Основы программирования. Комбинаторные алгоритмы, слайд №8Основы программирования. Комбинаторные алгоритмы, слайд №9Основы программирования. Комбинаторные алгоритмы, слайд №10Основы программирования. Комбинаторные алгоритмы, слайд №11Основы программирования. Комбинаторные алгоритмы, слайд №12Основы программирования. Комбинаторные алгоритмы, слайд №13Основы программирования. Комбинаторные алгоритмы, слайд №14Основы программирования. Комбинаторные алгоритмы, слайд №15Основы программирования. Комбинаторные алгоритмы, слайд №16Основы программирования. Комбинаторные алгоритмы, слайд №17Основы программирования. Комбинаторные алгоритмы, слайд №18Основы программирования. Комбинаторные алгоритмы, слайд №19Основы программирования. Комбинаторные алгоритмы, слайд №20
Скачать

Содержание ▲

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

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

Слайд 1


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

Слайд 2


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

Слайд 3


Перестановки Пример комбинаторной задачи: нахождение всех перестановок натуральных чисел от 1 до n: 1) первое число – любое из чисел 1, …, n; 2) второе число – любое из чисел 1, …, n, кроме первого числа; 3) третье число – одно из чисел, которое не выбрано первым или вторым, и т.д. Всего существует n (n – 1) … 2∙1 = n! вариантов перестановок.
Описание слайда:
Перестановки Пример комбинаторной задачи: нахождение всех перестановок натуральных чисел от 1 до n: 1) первое число – любое из чисел 1, …, n; 2) второе число – любое из чисел 1, …, n, кроме первого числа; 3) третье число – одно из чисел, которое не выбрано первым или вторым, и т.д. Всего существует n (n – 1) … 2∙1 = n! вариантов перестановок.

Слайд 4


Дерево решений для n=3
Описание слайда:
Дерево решений для n=3

Слайд 5


Перестановки В реальных задачах могут потребоваться различные перестановки n произвольных объектов. Для этого проще всего использовать «косвенный» метод: переставлять местами не сами объекты, а их номера в наборе. Построим, соответственно, алгоритм генерации всех перестановок чисел 0…n-1. Идея рекурсивного алгоритма: основным параметром является номер текущей позиции в перестановке k () начиная с k=0, последовательно ставим на позицию k все числа, которые пока не использованы в перестановке, и производим рекурсивный вызов для k+1 (т.е. генерируем все возможные варианты для позиций k+1…n-1).
Описание слайда:
Перестановки В реальных задачах могут потребоваться различные перестановки n произвольных объектов. Для этого проще всего использовать «косвенный» метод: переставлять местами не сами объекты, а их номера в наборе. Построим, соответственно, алгоритм генерации всех перестановок чисел 0…n-1. Идея рекурсивного алгоритма: основным параметром является номер текущей позиции в перестановке k () начиная с k=0, последовательно ставим на позицию k все числа, которые пока не использованы в перестановке, и производим рекурсивный вызов для k+1 (т.е. генерируем все возможные варианты для позиций k+1…n-1).

Слайд 6


Алгоритм генерации всех перестановок В алгоритме используются 2 массива (их проще сделать глобальными, чтобы постоянно не передавать параметры в рекурсивную функцию): целочисленный массив Per длины n содержит текущую построенную часть перестановки массив Inc длины n содержит признаки включения чисел в перестановку (bool или int), например Inc[i]=true, если число i включено в перестановку, и Inc[i]=false, если нет. Вызов функции генерации перестановок permut: for (i = 0; i < n; i++) Inc[i] = false; permut(0);
Описание слайда:
Алгоритм генерации всех перестановок В алгоритме используются 2 массива (их проще сделать глобальными, чтобы постоянно не передавать параметры в рекурсивную функцию): целочисленный массив Per длины n содержит текущую построенную часть перестановки массив Inc длины n содержит признаки включения чисел в перестановку (bool или int), например Inc[i]=true, если число i включено в перестановку, и Inc[i]=false, если нет. Вызов функции генерации перестановок permut: for (i = 0; i < n; i++) Inc[i] = false; permut(0);

Слайд 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] = false; } } Число рекурсивных вызовов: O(n!)
Описание слайда:
Алгоритм генерации всех перестановок 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] = false; } } Число рекурсивных вызовов: O(n!)

Слайд 8


Сочетания Сочетания из n элементов по m – это всевозможные подмножества элементов множества длины n. Порядок расположения элементов не важен, т.е. при использовании их номеров и m=3 последовательности (1,3,6), (3,1,6), (6,3,1) представляют одно и то же сочетание. Следовательно, сочетания номеров элементов (в глобальном массиве Comb) выгодно генерировать в возрастающем порядке, и массив Inc не нужен: min(Comb[k+1]) = Comb[k] + 1 max(Comb[k]) = n – m + k Количество различных сочетаний из n по m:
Описание слайда:
Сочетания Сочетания из n элементов по m – это всевозможные подмножества элементов множества длины n. Порядок расположения элементов не важен, т.е. при использовании их номеров и m=3 последовательности (1,3,6), (3,1,6), (6,3,1) представляют одно и то же сочетание. Следовательно, сочетания номеров элементов (в глобальном массиве Comb) выгодно генерировать в возрастающем порядке, и массив Inc не нужен: min(Comb[k+1]) = Comb[k] + 1 max(Comb[k]) = n – m + k Количество различных сочетаний из n по m:

Слайд 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); } } Вызов: combinat(0);
Описание слайда:
Алгоритм генерации всех сочетаний 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); } } Вызов: combinat(0);

Слайд 10


Задача о ферзях Пример для доски 4x4
Описание слайда:
Задача о ферзях Пример для доски 4x4

Слайд 11


Задача о ферзях Основные требования при поиске решения любой комбинаторной задачи: найти удобную форму для представления информации; найти эвристики (совокупности приемов и правил решения практических задач), позволяющие заранее отсекать невыполнимые варианты. Число проверяемых вариантов для 8 ферзей: без учета совпадения вертикалей и горизонталей всего млрд. с учетом расстановки только в разных горизонталях (или только в разных вертикалях) млн.
Описание слайда:
Задача о ферзях Основные требования при поиске решения любой комбинаторной задачи: найти удобную форму для представления информации; найти эвристики (совокупности приемов и правил решения практических задач), позволяющие заранее отсекать невыполнимые варианты. Число проверяемых вариантов для 8 ферзей: без учета совпадения вертикалей и горизонталей всего млрд. с учетом расстановки только в разных горизонталях (или только в разных вертикалях) млн.

Слайд 12


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

Слайд 13


Гамильтоновы циклы и пути Гамильтонов цикл в неориентированном графе: начинается в произвольной вершине a проходит по ребрам через все вершины графа по одному разу завершается в вершине a. Если в графе найдутся такие 2 вершины a и b, что переходя из a по ребрам можно попасть в b, обойдя все остальные вершины по одному разу, то в графе существует гамильтонов путь из a в b. Для графов нет явных аналитических условий существования гамильтонова цикла/пути, поэтому решение можно найти только путем перебора вариантов путей.
Описание слайда:
Гамильтоновы циклы и пути Гамильтонов цикл в неориентированном графе: начинается в произвольной вершине a проходит по ребрам через все вершины графа по одному разу завершается в вершине a. Если в графе найдутся такие 2 вершины a и b, что переходя из a по ребрам можно попасть в b, обойдя все остальные вершины по одному разу, то в графе существует гамильтонов путь из a в b. Для графов нет явных аналитических условий существования гамильтонова цикла/пути, поэтому решение можно найти только путем перебора вариантов путей.

Слайд 14


Гамильтоновы циклы и пути Любой гамильтонов цикл/путь задается некоторой перестановкой номеров вершин графа. Получать все перестановки, а затем проверять, не соответствуют ли они некоторому пути в графе, невыгодно. Необходимо как можно раньше отсекать варианты, которые не соответствуют путям в графе, когда переход из предыдущей вершины в следующую невозможен. Для упрощения алгоритма добавим в класс MGraph 2 дополнительных поля: int *Path – массив, в котором будут сохраняться пути bool *Inc – массив отметок пройденных вершин. Рекурсивная функция ham_loops – поиск всех гамильтоновых циклов в графе – это просто модификация функции генерации всех перестановок.
Описание слайда:
Гамильтоновы циклы и пути Любой гамильтонов цикл/путь задается некоторой перестановкой номеров вершин графа. Получать все перестановки, а затем проверять, не соответствуют ли они некоторому пути в графе, невыгодно. Необходимо как можно раньше отсекать варианты, которые не соответствуют путям в графе, когда переход из предыдущей вершины в следующую невозможен. Для упрощения алгоритма добавим в класс MGraph 2 дополнительных поля: int *Path – массив, в котором будут сохраняться пути bool *Inc – массив отметок пройденных вершин. Рекурсивная функция ham_loops – поиск всех гамильтоновых циклов в графе – это просто модификация функции генерации всех перестановок.

Слайд 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 == vernum-1) { if (mat[i][0]) PROCESS_LOOP(); } else ham_loops(k+1); Inc[i] = false; } } Трудоемкость:
Описание слайда:
Алгоритм поиска всех гамильтоновых циклов 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 == vernum-1) { if (mat[i][0]) PROCESS_LOOP(); } else ham_loops(k+1); Inc[i] = false; } } Трудоемкость:

Слайд 16


Обертка для рекурсивной функции Для метода ham_loops необходимо заранее подготовить 2 массива и задать начальную вершину пути. Поэтому ham_loops лучше сделать приватным методом и добавить public-обертку для него: void hamilton_loops() { Path = new int[vernum]; Inc = new bool[vernum]; for (int i = 0; i < vernum; i++) Inc[i] = false; Path[0] = 0; Inc[0] = true; ham_loops(1); delete [] Inc; delete [] Path; }
Описание слайда:
Обертка для рекурсивной функции Для метода ham_loops необходимо заранее подготовить 2 массива и задать начальную вершину пути. Поэтому ham_loops лучше сделать приватным методом и добавить public-обертку для него: void hamilton_loops() { Path = new int[vernum]; Inc = new bool[vernum]; for (int i = 0; i < vernum; i++) Inc[i] = false; Path[0] = 0; Inc[0] = true; ham_loops(1); delete [] Inc; delete [] Path; }

Слайд 17


Формализация комбинаторных задач Общие условия: задано – множество элементов решения решение , – это обычно не просто подмножество , а комплекс, в котором важен порядок следования элементов множество всех возможных вариантов решений (возможных комплексов элементов из ) очень велико и не может быть построено целиком, поэтому все решения отыскиваются последовательно не каждый вариант может оказаться решением задачи. Существуют 2 основных подхода к решению комбинаторных задач: бэктрекинг и метод решета.
Описание слайда:
Формализация комбинаторных задач Общие условия: задано – множество элементов решения решение , – это обычно не просто подмножество , а комплекс, в котором важен порядок следования элементов множество всех возможных вариантов решений (возможных комплексов элементов из ) очень велико и не может быть построено целиком, поэтому все решения отыскиваются последовательно не каждый вариант может оказаться решением задачи. Существуют 2 основных подхода к решению комбинаторных задач: бэктрекинг и метод решета.

Слайд 18


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

Слайд 19


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

Слайд 20


Метод решета Производится не последовательный расчет допустимых решений, а исключение вариантов, которые не являются решениями (если таких много и они исключаются просто). Решето Эратосфена для нахождения простых чисел : битовую строку длины заполнить нулями нулевого бита с номером установить в 1 все биты с номерами . Трудоемкость составляет – это гораздо быстрее, чем проверять остатки от деления. Задача о корзине с яйцами Найти минимальное , для которого выполняется: . Решение: делится нацело на 2, 3, 4, 5 и 6, следовательно,
Описание слайда:
Метод решета Производится не последовательный расчет допустимых решений, а исключение вариантов, которые не являются решениями (если таких много и они исключаются просто). Решето Эратосфена для нахождения простых чисел : битовую строку длины заполнить нулями нулевого бита с номером установить в 1 все биты с номерами . Трудоемкость составляет – это гораздо быстрее, чем проверять остатки от деления. Задача о корзине с яйцами Найти минимальное , для которого выполняется: . Решение: делится нацело на 2, 3, 4, 5 и 6, следовательно,

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию