Презентация Основы программирования. Комбинаторные алгоритмы онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Основы программирования. Комбинаторные алгоритмы абсолютно бесплатно. Урок-презентация на эту тему содержит всего 20 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Устройства и комплектующие » Основы программирования. Комбинаторные алгоритмы
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:20 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:794.37 kB
- Просмотров:64
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№2 слайд
![Комбинаторные алгоритмы](/documents_6/d331cf9ed3caaed397ba2da7ba4b5cd5/img1.jpg)
Содержание слайда: Комбинаторные алгоритмы
Исследуемые объекты представлены дискретными математическими структурами (множествами, графами).
Требуется найти ответ на вопросы типа:
существует ли способ…
сколько существует способов…
найти все решения…
найти лучшее (в смысле некоторого критерия) решение.
При этом обычно не существует аналитического решения и не заданы правила вычислений.
Задачи, требующие перебора вариантов решения – комбинаторные.
№3 слайд
![Перестановки Пример](/documents_6/d331cf9ed3caaed397ba2da7ba4b5cd5/img2.jpg)
Содержание слайда: Перестановки
Пример комбинаторной задачи: нахождение всех перестановок натуральных чисел от 1 до n:
1) первое число – любое из чисел 1, …, n;
2) второе число – любое из чисел 1, …, n, кроме первого числа;
3) третье число – одно из чисел, которое не выбрано первым или вторым, и т.д.
Всего существует n (n – 1) … 2∙1 = n! вариантов перестановок.
№5 слайд
![Перестановки В реальных](/documents_6/d331cf9ed3caaed397ba2da7ba4b5cd5/img4.jpg)
Содержание слайда: Перестановки
В реальных задачах могут потребоваться различные перестановки n произвольных объектов. Для этого проще всего использовать «косвенный» метод: переставлять местами не сами объекты, а их номера в наборе.
Построим, соответственно, алгоритм генерации всех перестановок чисел 0…n-1.
Идея рекурсивного алгоритма:
основным параметром является номер текущей позиции в перестановке k ()
начиная с k=0, последовательно ставим на позицию k все числа, которые пока не использованы в перестановке, и производим рекурсивный вызов для k+1 (т.е. генерируем все возможные варианты для позиций k+1…n-1).
№6 слайд
![Алгоритм генерации всех](/documents_6/d331cf9ed3caaed397ba2da7ba4b5cd5/img5.jpg)
Содержание слайда: Алгоритм генерации всех перестановок
В алгоритме используются 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);
№8 слайд
![Сочетания Сочетания из n](/documents_6/d331cf9ed3caaed397ba2da7ba4b5cd5/img7.jpg)
Содержание слайда: Сочетания
Сочетания из 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:
№11 слайд
![Задача о ферзях Основные](/documents_6/d331cf9ed3caaed397ba2da7ba4b5cd5/img10.jpg)
Содержание слайда: Задача о ферзях
Основные требования при поиске решения любой комбинаторной задачи:
найти удобную форму для представления информации;
найти эвристики (совокупности приемов и правил решения практических задач), позволяющие заранее отсекать невыполнимые варианты.
Число проверяемых вариантов для 8 ферзей:
без учета совпадения вертикалей и горизонталей всего
млрд.
с учетом расстановки только в разных горизонталях (или только в разных вертикалях) млн.
№13 слайд
![Гамильтоновы циклы и пути](/documents_6/d331cf9ed3caaed397ba2da7ba4b5cd5/img12.jpg)
Содержание слайда: Гамильтоновы циклы и пути
Гамильтонов цикл в неориентированном графе:
начинается в произвольной вершине a
проходит по ребрам через все вершины графа по одному разу
завершается в вершине a.
Если в графе найдутся такие 2 вершины a и b, что переходя из a по ребрам можно попасть в b, обойдя все остальные вершины по одному разу, то в графе существует гамильтонов путь из a в b.
Для графов нет явных аналитических условий существования гамильтонова цикла/пути, поэтому решение можно найти только путем перебора вариантов путей.
№14 слайд
![Гамильтоновы циклы и пути](/documents_6/d331cf9ed3caaed397ba2da7ba4b5cd5/img13.jpg)
Содержание слайда: Гамильтоновы циклы и пути
Любой гамильтонов цикл/путь задается некоторой перестановкой номеров вершин графа. Получать все перестановки, а затем проверять, не соответствуют ли они некоторому пути в графе, невыгодно.
Необходимо как можно раньше отсекать варианты, которые не соответствуют путям в графе, когда переход из предыдущей вершины в следующую невозможен.
Для упрощения алгоритма добавим в класс MGraph 2 дополнительных поля:
int *Path – массив, в котором будут сохраняться пути
bool *Inc – массив отметок пройденных вершин.
Рекурсивная функция ham_loops – поиск всех гамильтоновых циклов в графе – это просто модификация функции генерации всех перестановок.
№15 слайд
![Алгоритм поиска всех](/documents_6/d331cf9ed3caaed397ba2da7ba4b5cd5/img14.jpg)
Содержание слайда: Алгоритм поиска всех гамильтоновых циклов
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 слайд
![Обертка для рекурсивной](/documents_6/d331cf9ed3caaed397ba2da7ba4b5cd5/img15.jpg)
Содержание слайда: Обертка для рекурсивной функции
Для метода 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 слайд
![Формализация комбинаторных](/documents_6/d331cf9ed3caaed397ba2da7ba4b5cd5/img16.jpg)
Содержание слайда: Формализация комбинаторных задач
Общие условия:
задано – множество элементов решения
решение , – это обычно не просто подмножество , а комплекс, в котором важен порядок следования элементов
множество всех возможных вариантов решений (возможных комплексов элементов из ) очень велико и не может быть построено целиком, поэтому все решения отыскиваются последовательно
не каждый вариант может оказаться решением задачи.
Существуют 2 основных подхода к решению комбинаторных задач: бэктрекинг и метод решета.
№18 слайд
![Бэктрекинг поиск с возвратом](/documents_6/d331cf9ed3caaed397ba2da7ba4b5cd5/img17.jpg)
Содержание слайда: Бэктрекинг (поиск с возвратом)
Полное решение формируется рекурсивно на основе последовательности частичных решений , ,…, : при очередном рекурсивном вызове к текущему частичному решению добавляется новый элемент – один из множества допустимых.
Если из текущего решения невозможно построить никакое последующее (тупик) или уже является полным решением, то производится рекурсивный возврат к предыдущему частичному решению и выбирается следующий допустимый элемент .
Бэктрекинг позволяет перебрать все варианты полных решений без повторов.
№19 слайд
![Общий вид алгоритма поиска с](/documents_6/d331cf9ed3caaed397ba2da7ba4b5cd5/img18.jpg)
Содержание слайда: Общий вид алгоритма поиска с возвратом
Пусть S – текущее решение, M – множество элементов решений, a – один из эл-тов M):
поиск(S)
{
while (существует_подходящий_элемент(M,S,a))
{
добавить_к_текущему_решению(S,a);
if (полное_решение(S)) вывод_решения(S);
else if
(возможен_дальнейший_поиск(S)) поиск(S);
удалить_из_текущего_решения(S,a);
}
}
№20 слайд
![Метод решета Производится не](/documents_6/d331cf9ed3caaed397ba2da7ba4b5cd5/img19.jpg)
Содержание слайда: Метод решета
Производится не последовательный расчет допустимых решений, а исключение вариантов, которые не являются решениями (если таких много и они исключаются просто).
Решето Эратосфена для нахождения простых чисел :
битовую строку длины заполнить нулями
нулевого бита с номером установить в 1 все биты с номерами .
Трудоемкость составляет – это гораздо быстрее, чем проверять остатки от деления.
Задача о корзине с яйцами
Найти минимальное , для которого выполняется:
.
Решение: делится нацело на 2, 3, 4, 5 и 6,
следовательно,
Скачать все slide презентации Основы программирования. Комбинаторные алгоритмы одним архивом:
Похожие презентации
-
Кодирование основных типов алгоритмических структур на языках объектно — ориентированного и процедурного программирования
-
Основы алгоритмизации и программирование
-
Основы программирования ФИСТ. Двухмерные массивы. Базовые алгоритмы. Лекция 10
-
Основы алгоритмизации и программирования. Указатели
-
Основы алгоритмизации и программирования. Понятие и свойства алгоритма
-
Основы алгоритмизации и программирования. Структуры, объединения, перечисления
-
Структурное программирование. Основные сведения об алгоритмах
-
Основы алгоритмизации и программирования. Особенности ввода-вывода массивов
-
Основы программирования. Общее понятие алгоритма
-
Основы программирования. Эффективные алгоритмы сортировки