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

Сентябрь 7, 2022

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

Содержание

2. Комбинаторные алгоритмы Исследуемые объекты представлены дискретными математическими структурами (множествами, графами). Требуется найти ответ на вопросы типа:
3. Перестановки Пример комбинаторной задачи: нахождение всех перестановок натуральных чисел от 1 до n: 1) первое число
4. Дерево решений для n=3
5. Перестановки
6. Алгоритм генерации всех перестановок В алгоритме используются 2 массива (их проще сделать глобальными, чтобы постоянно не
7. Алгоритм генерации всех перестановок void permut(int k) { for (int i = 0; i if (!Inc[i])
8. Сочетания
9. Алгоритм генерации всех сочетаний void combinat(int k) { int i = (!k)? 0 : Comb[k-1]+1; for
10. Задача о ферзях Пример для доски 4x4
11. Задача о ферзях Основные требования при поиске решения любой комбинаторной задачи: найти удобную форму для представления
12. Задача о ферзях с учетом горизонталей и диагоналей – для элементов на одной диагонали константами являются
13. Гамильтоновы циклы и пути Гамильтонов цикл в неориентированном графе: начинается в произвольной вершине a проходит по
14. Гамильтоновы циклы и пути Любой гамильтонов цикл/путь задается некоторой перестановкой номеров вершин графа. Получать все перестановки,
15. Алгоритм поиска всех гамильтоновых циклов
16. Обертка для рекурсивной функции Для метода ham_loops необходимо заранее подготовить 2 массива и задать начальную вершину
17. Формализация комбинаторных задач
18. Бэктрекинг (поиск с возвратом)
19. Общий вид алгоритма поиска с возвратом Пусть S – текущее решение, M – множество элементов решений,
21. Скачать презентацию

Слайд 2

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

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

Слайд 3

Перестановки
Пример комбинаторной задачи: нахождение всех перестановок натуральных чисел от 1 до

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

Слайд 4

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

Слайд 5

Перестановки

Слайд 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);

Слайд 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!)

Слайд 8

Сочетания

Слайд 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);

Слайд 10

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

Слайд 11

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

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

Слайд 12

Задача о ферзях
с учетом горизонталей и диагоналей – для элементов на

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

Слайд 13

Гамильтоновы циклы и пути
Гамильтонов цикл в неориентированном графе:
начинается в произвольной вершине

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

Слайд 14

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

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

Слайд 15

Алгоритм поиска всех гамильтоновых циклов

Слайд 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;
}

Слайд 17

Формализация комбинаторных задач

Слайд 18

Бэктрекинг (поиск с возвратом)

Слайд 19

Общий вид алгоритма поиска с возвратом
Пусть S – текущее решение, M

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

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

Содержание

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

ПерестановкиПример комбинаторной задачи: нахождение всех перестановок натуральных чисел от 1 до

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

Перестановки

Алгоритм генерации всех перестановокВ алгоритме используются 2 массива (их проще сделать

Алгоритм генерации всех перестановокvoid permut(int k){ for (int i =

Сочетания

Алгоритм генерации всех сочетанийvoid combinat(int k){ int i = (!k)? 0

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

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

Задача о ферзяхс учетом горизонталей и диагоналей – для элементов на

Гамильтоновы циклы и путиГамильтонов цикл в неориентированном графе:начинается в произвольной вершине

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