Порождение и перебор комбинаторных объектов

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ФГБОУ ВО «Кабардино-Балкарский государственный университет им. Х.М. Бербекова» (КБГУ)

ИНСТИТУТ ФИЗИКИ И МАТЕМАТИКИ

КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ

Курсовая работа на тему: «Порождение и перебор комбинаторных объектов»

Молов Аскер Мачраилович

Нальчик 2021

Оглавление

Введение

1. Теоретический обзор различных методов порождение и перебор комбинаторных объектов

1.1 Основные термины и понятия

1.2 История изучения методов порождение и перебор комбинаторных объектов

2. Основные разновидности методов порождения и перебора комбинаторных объектов

2.1 Необходимость перебор комбинаторных объектов

3. Описание методов порождения и перебора комбинаторных объектов. Примеры решения задач

Заключение

Список использованной литературы



Введение

Во многих прикладных задачах требуется найти оптимальное решение среди очень большого числа вариантов. Иногда удается построить это решение сразу, но в большинстве случаев единственный способ его отыскать состоит в переборе всех возможных вариантов и сравнении их между собой. Поэтому так важно научиться строить алгоритмы перебора различных комбинаторных объектов - последовательностей, перестановок, подмножеств и т.д.

Целью этой курсовой работы является изучение и понимание основных принципов перебора комбинаторных объектов.

Задачей данной курсовой работы является изучение наиболее основных и наиболее употребляемых алгоритмов перебора комбинаторных объектов, а так же методов, по которым происходит выбор в пользу того или иного метода. Кроме того, настоящая работа предполагает разбор и ознакомление с историей данного вопроса, рассмотрение и анализ конкретных примеров реализации некоторых алгоритмов перебора комбинаторных объектов на Pascal.

Объектом курсовой работы являются непосредственно методы порождение и перебор комбинаторных объектов. Структурно данная курсовая работа разделена на две части. Часть первая предполагает теоретическое ознакомление с основными методами порождения и перебора комбинаторных объектов, принципами, на которых они основываются и их свойства, и возможность применения в той или иной ситуации, а так же способы оптимального подбора метода, в зависимости от имеющихся ресурсов. Кроме того, в первой части работы приводятся области практического применения методов порождения и перебора комбинаторных объектов, а так же краткий экскурс в историю данного вопроса. Вторая часть работы отведены практическому решению данной задачи. Здесь будут приведены реализации упомянутых в первой части работы методы порождения и перебора комбинаторных объектов на Pascal с краткими пояснениями.



1. Теоретический обзор различных методов порождение и перебор комбинаторных объектов

1.1 Основные термины и понятия

комбинаторный перебор порождение

Элементарная комбинаторика имеет дело с множествами, из которых выбираются подмножества с определенными свойствами. Как правило, основной вопрос заключается в следующем: сколько таких подмножеств можно выбрать из данного множества? Т.е. задача состоит в подсчете числа этих подмножеств.

Введем следующие понятия.

Пусть A = {a1,…, an} - множество из n элементов.

Комбинаторный объект - это подмножество с определенными свойствами из элементов множества A.

Примеры комбинаторных объектов

1) Битовые вектора - последовательность нулей и единиц заданной длины.

2) Перестановки - это упорядоченный набор чисел обычно трактуемый как биекция на множестве, которая числу i ставит соответствие i-й элемент из набора.

3) Сочетания из n по k - это набор k элементов, выбранных из данных n элементов.

4) Размещение из n по k - это упорядоченный набор из k различных элементов некоторого n-элементного множества.

5) Разбиение числа на слагаемые.

6) Все возможные подмножества заданного множества.

7) Разбиение множества на подмножества такие, что в объединении они дают исходное множество, но при этом ни одно из них не пересекается с любым другим.

Размещениями с повторениями из n элементов по k называются всевозможные комбинации по k элементов, составленные из элементов данных n видов. При этом в комбинацию могут входить и предметы одного вида, а две комбинации считаются различными, если они отличаются друг от друга или видом входящих в них элементов, или порядком этих элементов.

Количество размещений с повторениями обозначается и равно nk.

Размещениями без повторений из n элементов по k называются всевозможные комбинации по k элементов, составленные из элементов данных n видов. При этом две комбинации считаются различными, если они либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке.

Количество размещений без повторений обозначают A^k_n. Общее правило вычисления количества размещений:

A^k_n=nЧ(n - 1)*(n - k+1)=.

Перестановками из n элементов называют всевозможные комбинации из n элементов, каждая из которых содержит все элементы по одному разу. Комбинации отличаются друг от друга лишь порядком элементов.

Число n-перестановок обозначают через Рn. Общее правило вычисления количества перестановок:

Рn=Аⁿ_n=nЧ (n-1) Ч (n-2) Ч…Ч2Ч1=n!

Перестановками с повторениями из n₁ элементов первого типа, n₂ элементов второго типа,…, nk элементов k-го типа называются всевозможные комбинации из этих элементов, каждая из которых содержит ni элементов i-го вида. Комбинации отличаются друг от друга лишь порядком элементов.

Число перестановок с повторениями обозначают через Р (n1, n2,…, nk). Общее правило вычисления количества перестановок с повторениями:

Р (n1, n2,…, nk)=.

Сочетаниями из n элементов по k называют всевозможные комбинации по k элементов, составленные из данных n элементов. Комбинации отличаются друг от друга составом, но не порядком элементов.

Количество сочетаний из n элементов по k обозначают.

Формула для вычисления числа сочетаний получается из формулы для вычисления количества размещений. Составим сначала все k-сочетания из n элементов, а потом переставим входящие в каждое сочетание элементы всеми возможными способами. При этом получатся все k-размещения из n элементов, причем каждое только по одному разу. Элементы каждого k-сочетания можно переставить k! способами, а число этих сочетаний равно. Значит, справедлива формула. Получаем

Сочетаниями с повторениями из n элементов по k называют всевозможные комбинации, составленные из элементов n видов по k элементов в каждой. Комбинации считаются различными, если они отличаются составом, но не порядком входящих в них элементов. В комбинацию могут входить элементы одного вида.

Количество сочетаний с повторениями из n элементов по k обозначают . Общее правило вычисления количества сочетаний с повторениями:



1.2 История изучения методов порождение и перебор комбинаторных объектов

Самое раннее зарегистрированное использование комбинаторных методов происходит в решинии 79 проблемы папируса Райнда, который датируется 16 веком до нашей эры. Проблема касается определенного геометрического ряда и имеет сходство с проблемой Фибоначчи о подсчете количества композиций единиц и двоек, которые в сумме составляют заданную сумму.

В Греции Плутарх писал, что Ксенократ Халкидонский (396-314 до н.э.) обнаружил количество различных слогов, возможных в греческом языке. Это была бы первая известная попытка решить сложную проблему перестановок и комбинаций. Однако это утверждение неправдоподобно: это одно из немногих упоминаний комбинаторики в Греции, и найденное ими число 1,002 Ч 10 12 кажется слишком круглым, чтобы быть более чем предположением.

Позже упоминается спор между Хрисиппом (3 век до н.э.) и Гиппархом (2 век до н.э.) из-за довольно деликатной проблемы перечисления, которая, как позже было показано, связана с числами Шредера-Гиппарха. Есть также свидетельства того, что в Остомахионе Архимед (3 век до н.э.) рассматривал конфигурации мозаичной головоломки, в то время как некоторые комбинаторные интересы могли присутствовать в утерянных работах Аполлония.

В Индии в Бхагавати Сутре впервые упоминается проблема комбинаторики; Задача заключалась в том, чтобы выяснить, сколько возможных комбинаций вкусов возможно при выборе вкусов по одному, по два, по три и т.д. из шести различных вкусов. Бхагавати также является первым текстом, в котором упоминается функция выбора. Во втором веке до нашей эры Пингала включил задачу перечисления в Чанда Сутру, в которой спрашивалось, сколькими способами можно составить шестисложный метр из коротких и длинных нот. Пингала нашла количество метров, в которых n длинных нот и k коротких нот; это эквивалентно нахождению биномиальных коэффициентов.

Идеи Бхагавати были обобщены индийским математиком Махавирой в 850 году нашей эры, а работа Пингалы по просодии была расширена Бхаскарой II и Хемачандрой в 1100 году нашей эры. Бхаскара был первым известным человеком, обнаружившим функцию обобщенного выбора, хотя Брахмагупта, возможно, знал об этом раньше. Хемачандра спросил, сколько метров существует определенной длины, если длинная нота считается вдвое длиннее короткой, что эквивалентно нахождению чисел Фибоначчи.

В древней китайской книге гадания И Цзин гексаграмма описывается как перестановка с повторением шести линий, где каждая линия может быть в одном из двух состояний: сплошной или пунктирной. При описании гексаграмм таким образом они определяют, что существуют 2⁶ = 64 воможные гексаграммы. Китайский монах также мог подсчитать количество конфигураций в игре, подобной Go, около 700 г. н.э. Хотя в Китае было относительно мало достижений в области перечислительной комбинаторики, около 100 г. н.э. они решили Квадрат Ло Шу, который представляет собой комбинаторную задачу построения нормального магического квадрата третьего порядка. Магические квадраты по-прежнему интересовали Китай, и они начали обобщать свой первоначальный квадрат 3*3 между 900 и 1300 годами нашей эры. Китай переписывался с Ближним Востоком по этой проблеме в 13 веке. Ближний Восток также узнал о биномиальных коэффициентах из индийских работ и обнаружил связь с полиномиальным расширением. Работа индуистов повлияла на арабов, как видно из работы аль-Халиля ибн Ахмада, который рассмотрел возможные варианты расположения букв для образования слогов. Его расчеты показывают понимание перестановок и комбинаций. В отрывке из работы арабского математика Умара аль-Хайями, датируемом примерно 1100 годом, подтверждается, что индусы знали биномиальные коэффициенты, но также и то, что их методы достигли Ближнего Востока.

Абу Бакр ибн Мухаммад ибн аль-Хусейн аль-Караджи (около 953-1029) писал о биномиальной теореме и треугольнике Паскаля. В уже утерянной работе, известной только из последующих цитат ас-Самавала, аль-Караджи ввел идею аргументации с помощью математической индукции.

Философ и астроном раввин Авраам ибн Эзра (ок. 1140 г.) подсчитал перестановки с повторениями при произнесении Божественного имени. Он также установил симметрию биномиальных коэффициентов, а замкнутая формула была получена позже талмудистом и математиком Леви бен Герсоном в 1321 году. Арифметический треугольник - графическая диаграмма, показывающая отношения между биномиальными коэффициентами - был представлен математиками в трактатах, датируемых еще 10 веком, и в конечном итоге стал известен как треугольник Паскаля. Позже, в средневековой Англии, кампанология предоставила примеры того, что сейчас известно как гамильтоновы циклы в некоторых графах Кэли на перестановках.

Комбинаторика на Западе

Комбинаторика пришла в Европу в 13 век через математиков Леонардо Фибоначчи и Иордании де Немора. «Liber Abaci» Фибоначчи представила Европе многие арабские и индийские идеи, включая идею чисел Фибоначчи. Джордан был первым, кто расположил биномиальные коэффициенты в треугольнике, как он это сделал в предложении 70 кнги «De Arithmetica». Это также было сделано на Ближнем Востоке в 1265 г. и в Китае около 1300 г. Сегодня этот треугольник известен как треугольник Паскаля.

Вклад Паскаля в треугольник, носящий его имя, основан на его работе над формальными доказательствами этого треугольника и связями, которые он установил между треугольником Паскаля и вероятностью. Из письма Лейбница Даниэлю Бернулли мы узнаем, что Лейбниц формально изучал математическую теорию разделов в 17 веке, хотя никаких официальных работ опубликовано не было. Вместе с Лейбницем Паскаль в 1666 году опубликовал книгу «De Arte Combinatoria», которая позже была переиздана. Паскаль и Лейбниц считаются основателями современной комбинаторики.

Они понимали, что биномиальное разложение эквивалентно функции выбора. Представление о соответствии алгебры и комбинаторики было расширено Де Муавром, который обнаружил расширение полинома. Де Муавр также нашел формулу расстройства, используя принцип включения-исключения, метод, отличный от Николауса Бернулли, который нашел его ранее. Де Муавру также удалось аппроксимировать биномиальные коэффициенты и факториал, и он нашел замкнутую форму для чисел Фибоначчи, изобретая производящие функции.

В 18 веке Эйлер работал над проблемами комбинаторики и несколькими проблемами вероятности, которые связаны с комбинаторикой. Проблемы, над которыми работал Эйлер, включают рыцарский тур, греко-латинский квадрат, числа Эйлера и другие. Для решения проблемы семи мостов Кенигсберга он изобрел теорию графов, которая также привела к формированию топологии. Наконец, он положил начало разбиениям с помощью производящих функций.

Современная комбинаторика В 19 веке тема частично упорядоченных множеств и теории решетки возникла в работах Дедекинда, Пирса и Шредера. Тем не менее, именно основополагающая работа Гарретта Биркгофа в его книге «Теория решеток», опубликованная в 1967 году, и работа Джона фон Неймана по-настоящему установили эти темы. В 1930-х годах Холл (1936) и Вейснер (1935) независимо сформулировали общую формулу обращения Мебиуса. В 1964 году Джан-Карло Рота в своей книге «Об основах комбинаторной теории I. Теория функций Мёбиуса» представила теории упорядоченных множеств и решеток как теории комбинаторики. Ричард П. Стэнли оказал большое влияние на современную комбинаторику своими работами по теории матроидов, введением полиномов Дзета, за явное определение эйлеровых множеств, разработкой теории биномиальных множеств вместе с Ротой и Питером. Doubilet, и другие.



2. Основные разновидности методов порождения и перебора комбинаторных объектов

2.1 Необходимость перебор комбинаторных объектов

Комбинаторика - это основная область математики, имеющая обширные приложения во многих областях.

Области, такие как инженерия, естественные и социальные науки, биомедицина, исследования операций и бизнеса. Наиболее распространенный сценарий состоит в том, что многие проблемы реального мира математически решаются.

В этих случаях методы комбинаторики необходимы для подсчета, перечисления или представления возможных решений.

Области применения

Коммуникационные сети, криптография и сетевая безопасность

Перестановки часто используются в сетях связи, а также в параллельных и распределенных системах. Маршрутизация различных перестановок в сети для оценки производительности - обычное дело.

Многие сети связи требуют безопасной передачи информации, которая обеспечивается развитием криптографии и сетевой безопасности

Компьютерная архитектура

Дизайн компьютерных микросхем включает рассмотрение возможных перестановок входных и выходных контактов. Программируемые на месте микросхемы обеспечивают программируемое пользователем соединение для желаемой перестановки. Расположение логических вентилей является основным элементом проектирования компьютерной архитектуры. Языки И естественные, и компьютерные языки тесно связаны с комбинаторикой.

Это связано с тем, что компоненты этих языков, такие как предложения, абзацы, программы и блоки, являются расположение более мелких элементов, таких как слова, символы и атомы. Например, алгоритм поиска строки может полагаться на комбинаторику слов и символов. Прямое применение этого может включать в себя обработку текста и базы данных. Другой важной областью применения является анализ производительности этих алгоритмов поиска строк. В Базы данных

Запросы в базах данных - это несколько операций соединения, которые представляют собой перестановки составляющих операций соединения. Определение оптимальной перестановки, которая дает минимальные затраты, является важной.

Моделирование

Перестановки и комбинации могут использоваться для моделирования во многих областях. Перестановки, представляющие различные ассоциации генотип-фенотип используются в генетическом моделировании. Другие области которые используют перестановки и комбинации для моделирования, включают сети, криптографию, базы данных и OR.



3. Описание методов порождения и перебора комбинаторных объектов. Примеры решения задач

В этой части мы разберем основные методы перебора комбинаторных объектов. Схема перебора всегда будет одинакова:

- во-первых, надо установить ПОРЯДОК на элементах, подлежащих перечислению (в частности, определить, какой из них будет первым, а какой последним);

- во-вторых, научиться переходить от произвольного элемента к HЕПОСРЕДСТВЕHHО СЛЕДУЮЩЕМУ за ним (т.е. для заданного элемента x1 строить такой элемент x2, что x1<x2 и между x1 и x2 нет других элементов).

Hаиболее естественным способом упорядочения составных объектов является ЛЕКСИКОГРАФИЧЕСКИЙ порядок, принятый в любом словаре (сначала сравниваются первые буквы слов, потом вторые и т.д.) - именно его мы и будем чаще всего использовать. А вот процедуру получения следующего элемента придется каждый раз изобретать за - ново. Пока запишем схему перебора в таком виде:

X:=First;

while X<>Last do Next(X);

где First - первый элемент; Last - последний элемент; Next - процедура получения следующего элемента.

1.1. Последовательности

Hапечатать все последовательности длины N из чисел 1,2,…, M.

First = (1,1,…, 1) Last = (M, M,…, M)



Всего таких последовательностей будет M^N. Чтобы понять. как должна действовать процедура Next, начнем с примеров. Пусть N=4, M=3. Тогда:

Next (1,1,1,1) -> (1,1,1,2) Next (1,1,1,3) -> (1,1,2,1) Next (3,1,3,3) -> (3,2,1,1)

Теперь можно написать общую процедуру Next:

procedure Next;

begin {найти i: X[i]<M, X [i+1]=M,…, X[N]=M};

X[i]:=X[i]+1;

X [i+1]:=…:=X[N]:=1

end;

Если такого i найти не удается, то следующей последовательности нет - мы добрались до последней (M, M,…, M). Заметим также, что если бы членами последовательности были числа не от 1 до M, а от 0 до M-1, то переход к следующей означал бы прибавление 1 в M-ичной системе счисления. Полная программа на Паскале выглядит так:

program Sequences;

type Sequence=array [byte] of byte;

var M, N, i:byte;

X: Sequence;

Yes:boolean;

procedure Next (var X: Sequence; var Yes:boolean);

var i:byte;

begin

i:=N;

{поиск i}

while (i>0) and (X[i]=M) do begin X[i]:=1; dec(i) end;

if i>0 then begin inc (X[i]); Yes:=true end

else Yes:=false

end;

begin

write ('M, N='); readln (M, N);

for i:=1 to N do X[i]:=1;

repeat

for i:=1 to N do write (X[i]); writeln;

Next (X, Yes)

until not Yes

end.

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

Hапечатать все перестановки чисел 1..N (то есть последовательности длины N, в которые каждое из чисел 1..N входит ровно по одному разу).

First = (1,2,…, N) Last = (N, N-1,…, 1)

Всего таких перестановок будет N!=N*(N-1)*…*2*1 (докажите!). Для составления алгоритма Next зададимся вопросом: в каком случае i-ый член перестановки можно увеличить, не меняя предыдущих? Ответ: если он меньше какого-либо из следующих членов (членов с номерами больше i).

Мы должны найти наибольшее i, при котором это так, т.е. такое i, что X[i]<X [i+1]>…>X[N] (если такого i нет, то перестановка последняя). После этого X[i] нужно увеличить минимально возможным способом, т.е. найти среди X [i+1],…, X[N] наименьшее число, большее его. Поменяв X[i] с ним, остается расположить числа с номерами i+1,…, N так, чтобы перестановка была наименьшей, то есть в возрастающем порядке. Это облегчается тем, что они уже расположены в убывающем порядке:

procedure Next;

begin {найти i: X[i]<X [i+1]>X [i+2]>…>X[N]};

{найти j: X[j]>X[i]>X [j+1]>…>X[N]};

{обменять X[i] и X[j]};

{X [i+1]>X [i+2]>…>X[N]};

{перевернуть X [i+1], X [i+2],…, X[N]};

end;

Теперь можно написать программу:

program Perestanovki;

type Pere=array [byte] of byte;

var N, i, j:byte;

X: Pere;

Yes:boolean;

procedure Next (var X: Pere; var Yes:boolean);

var i:byte;

procedure Swap (var a, b:byte); {обмен переменных} var c:byte;

begin c:=a; a:=b; b:=c end;

begin

i:=N-1;

{поиск i}

while (i>0) and (X[i]>X [i+1]) do dec(i);

if i>0 then

begin

j:=i+1;

{поиск j}

while (j<N) and (X[j+1]>X[i]) do inc(j);

Swap (X[i], X[j]);

for j:=i+1 to (N+i) div 2 do Swap (X[j], X [N-j+i+1]);

Yes:=true

end

else Yes:=false

end;

begin

write ('N='); readln(N);

for i:=1 to N do X[i]:=i;

repeat

for i:=1 to N do write (X[i]); writeln;

Next (X, Yes)

until not Yes

end.

1.3. Разбиения

Перечислить все разбиения целого положительного числа N на целые положительные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно).

Пример: N=4, разбиения: 1+1+1+1, 2+1+1, 2+2, 3+1, 4.

First = (1,1,…, 1) - N единиц Last = (N)

Чтобы разбиения не повторялись, договоримся перечислять слагаемые в невозрастающем порядке. Сказать, сколько их будет всего, не так-то просто (см. следующий пункт). Для составления алгоритма Next зададимся тем же вопросом: в каком случае i-ый член разбиения можно увеличить, не меняя предыдущих?

Во-первых, должно быть X [i-1]>X[i] или i=1. Во-вторых, i должно быть не последним эле ментом (увеличение i надо компенсировать уменьшением следующих). Если такого i нет, то данное разбиение последнее. Увеличив i, все следующие элементы надо взять минимально возможными, т.е. равными единице:

procedure Next;

begin {найти i: (i<L) and ((X [i-1]>X[i]) or (i=1))}

X[i]:=X[i]+1;

{L:= i + X [i+1]+ … +X[L] - 1}

X [i+1]:=…:=X[L]:=1

end;

Через L мы обозначили количество слагаемых в текущем разбиении (понятно, что 1<=L<=N). Программа будет выглядеть так:

program Razbieniya;

type Razb=array [byte] of byte;

var N, i, L:byte;

X: Razb; procedure Next (var X: Razb; var L:byte);

var i, j:byte;

s:word;

begin

i:=L-1; s:=X[L];

{поиск i}

while (i>1) and (X[i-1]<=X[i]) do begin s:=s+X[i]; dec(i) end;

inc (X[i]);

L:=i+s-1;

for j:=i+1 to L do X[j]:=1

end;

begin

write ('N='); readln(N);

L:=N; for i:=1 to L do X[i]:=1;

for i:=1 to L do write (X[i]); writeln;

repeat

Next (X, L);

for i:=1 to L do write (X[i]); writeln

until L=1

end.

1.4. Подсчет количеств

Иногда можно найти количество объектов с тем или иным свойством, не перечисляя их. Классический пример: C (n, k) - число всех k-элементных подмножеств n-элементного множества - можно найти, заполняя таблицу значений функции С по формулам:

C (n, 0) = C (n, n) = 1 (n>=1) C (n, k) = C (n-1, k-1) + C (n-1, k) (n>1, 0<k<n);

или по формуле n!/(k!*(n-k)!) (первый способ эффективнее, если надо вычислить много значений С (n, k)).

Попробуем посчитать таким способом количество разбиений из пункта 1.3. Обозначим через R (N, k) (при N>=0, k>=0) число разбие - ний N на целые положительные слагаемые, не превосходящие k (при этом R (0, k) считаем равным 1 для всех k>=0). Очевидно, что число R (N, N) и будет искомым. Все разбиения N на слагаемые, не превосходящие k, разобьем на группы в зависимости от максимального слагаемого (обозначим его i).

Число R (N, k) равно сумме (по всем i от 1 до k) количеств разбиений со слагаемыми не больше k и максимальным слагаемым, равным i. А разбиения N на слагаемые не более k с первым слагаемым, равным i, по существу представляют собой разбиения n-i на слагаемые, не превосходящие i (при i<=k). Так что

R (N, k) = R (N - 1,1)+R (N - 2,2)+ … +R (N-k, k).

Остальное вы сделаете сами в домашнем задании.

2. Рекурсия

Вы уже знаете, что рекурсивными называются процедуры и функции, которые вызывают сами себя. Рекурсия позволяет очень просто (без использования циклов) программировать вычисление функций, заданных рекуррентно, например факториала f(n)=n!:

f(0)=1 f(n)=n*f (n-1).

Оказывается, рекурсивные процедуры являются удобным способом порождения многих комбинаторных объектов. Мы заново решим здесь несколько задач предыдущей главы и вы убедитесь, что запись многих алгоритмов значительно упростится благодаря использованию рекурсии.

Примечание сайта: рекурсия, безусловно, весьма удобна, однако часто требует громадное количество ресурсов. В частности, программа для факториала на 7-мом десятке завесит самый быстрый Pentium - III+. Из-за времени выполнения. О том, как этого избежать, можно прочитать в статье Динамическое программирование.

2.1. Факториал

Еще раз напомним рекурсивный алгоритм вычисления факториала:

program Factorial;

var N:word;

function F (n:word):longint;

begin

if n=0 then F:=1 else F:=n*F (n-1)

end;

begin

write ('N='); readln(N);

writeln ('N!=', F(N))

end.

2.2. Ханойская башня

Игра «Ханойская башня» состоит в следующем. Есть три стержня. Hа первый из них надета пирамидка из N колец (большие кольца снизу, меньшие сверху). Требуется переместить кольца на другой стержень. Разрешается перекладывать кольца со стержня на стержень, но класть большее кольцо поверх меньшего нельзя. Составить программу, указывающую требуемые действия.

Напишем рекурсивную процедуру перемещения M верхних колец с A-го стержня на B-ый в предположении, что остальные кольца больше по размеру и лежат на стержнях без движения:

procedure Move (M, A, B:integer);

var C:integer;

begin

if M=1 then begin writeln ('сделать ход ', A, '->', B) end

else

begin

C:=6-A-B; {C - третий стержень: сумма номеров равна 6}

Move (M-1, A, C);

Move (1, A, B);

Move (M-1, C, B)

end

end;

Сначала переносится пирамидка из M-1 колец на третий стержень C. После этого M-ое кольцо освобождается, и его можно перенести на B. Остается перенести пирамиду из N-1 кольца с C на B. Чем это проще первоначальной задачи? Тем, что количество колец стало на единицу меньше. Теперь основную программу можно записать в несколько строк:

program Hanoi;

var N:integer;

procedure Move (M, A, B:integer);

………….

begin

write ('N='); readln(N);

Move (N, 1,2)

end.

Если вы владеете основами компьютерной графики, можете попробовать «нарисовать» каждый ход на экране.

Таким образом, ОСHОВHАЯ ИДЕЯ любого рекурсивного решения - свести задачу к точно такой же, но с меньшим значением параметра. При этом какое-то минимальное значение параметра (например, 1 или 0) должно давать решение без рекурсивного вызова - иначе программа «зациклится» (последовательность рекурсивных вызовов будет бесконечной). Это напоминает метод математической индукции в математике. В некоторых задачах удобно наоборот, увеличивать значение параметра при рекурсивном вызове. Тогда, естественно, «безрекурсивное» решение должно предусматриваться для некоторого максимального значения параметра. Попробуем использовать эту идею для перебора комбинаторных объектов.



2.3 Последовательности (рекурсивный алгоритм)

Задача та же, что в пункте 1.1. Опишем рекурсивную процедуру Generate(k), предъявляющую все последовательности длины N из чисел 1,…, M, у которых фиксировано начало X[1], X[2],…, X[k]. Понятно, что при k=N мы имеем тривиальное решение: есть только одна такая последовательность - это она сама. При k<N будем сводить задачу к k+1:

procedure Generate (k:byte);

var i, j:byte;

begin

if k=N then

begin for i:=1 to N do write (X[i]); writeln end

else

for j:=1 to M do

begin X [k+1]:=j; Generate (k+1) end

end;

Основная программа теперь выглядит очень просто:

program SequencesRecursion;

type Sequence=array [byte] of byte;

var M, N:byte;

X: Sequence; procedure Generate (k:byte);

………… begin

write ('M, N='); readln (M, N);

Generate(0)

end.



2.4 Перестановки (рекурсивный алгоритм)

Задача та же, что в пункте 1.2. Опишем рекурсивную процедуру Generate(k), предъявляющую все перестановки чисел 1,…, N, у которых фиксировано начало X[1], X[2],…, X[k]. После выхода из процедуры массив X будут иметь то же значение, что перед входом (это существенно!). Понятно, что при k=N мы снова имеем только тривиальное решение - саму перестановку. При k<N будем сводить задачу к k+1:

procedure Generate (k:byte);

var i, j:byte;

procedure Swap (var a, b:byte);

var c:byte;

begin c:=a; a:=b; b:=c end;

begin

if k=N then

begin for i:=1 to N do write (X[i]); writeln end

else

for j:=k+1 to N do

begin

Swap (X[k+1], X[j]);

Generate (k+1);

Swap (X[k+1], X[j])

end

end;

Основная программа:

program PerestanovkiRecursion;

type Pere=array [byte] of byte;

var N, i, j:byte;

X: Pere; procedure Generate (k:byte);

…………… begin

write ('N='); readln(N);

for i:=1 to N do X[i]:=i;

Generate(0)

end.

Чтобы до конца разобраться в этой непростой программе, советуем выполнить ее на бумаге при N=3. Обратите внимание, что порядок вывода перестановок не будет лексикографическим!



3. Перебор с отходом назад

Как вы уже поняли, перебор комбинаторных объектов - задача весьма трудоемкая даже для компьютера. Hапример, перестановок из восьми чисел будет 8! = 40320 - число немаленькое. Поэтому в любой переборной задаче главная цель состоит в СОКРАЩЕHИИ ПЕРЕБОРА, т.е. в исключении тех объектов, которые заведомо не могут стать решением задачи. Предположим, что нам требуется рассмотреть только те перестановки, для которых сумма |X[i] - i| равна 8. Понятно, что их будет гораздо меньше: например, все перестановки, начинающиеся на 8,7,… рассматривать не нужно! Как можно модифицировать наш переборный алгоритм в этом случае? Если на каком-то этапе сумма

|X[1] - 1| + |X[2] - 2| +… + |X[k] - k|

уже больше 8, то рассматривать все перестановки, начинающиеся на X[1],…, X[k] уже не нужно - следует вернуться к X[k] и изменить его значение («отойти назад» - отсюда название метода).

Для такой ситуации мы рассмотрим один общий метод, который почти всегда позволяет значительно сократить перебор. Пусть искомое решение находится среди последовательностей вида

X[1],…, X[N],

где каждое X[i] выбирается из некоторого множества вариантов A[i]. Предположим мы уже построили начало этой последовательности X[1],…, X[k] (k<N) и хотим продолжить его до решения.

Предположим также, что у нас есть некоторый простой метод P (X[1],…, X[k]), который позволяет получить ответ на вопрос: можно продолжить X[1],…, X[k] до решения (true) или нет (false). Заметим, что значение true еще HЕ ГАРАHТИРУЕТ существование такого продолжения, но зато значение false ГАРАHТИРУЕТ непродолжаемость («не стоит дальше и пробовать»). Получаем простую рекурсивную процедуру ПЕРЕБОРА С ОТХОДОМ HАЗАД:

procedure Backtracking(k);

begin

for (y in A[k]) do

if P (X[1],…, X [k-1], y) then

begin

X[k]:=y;

if k=N then {X[1],…, X[N] - решение}

Backtracking (k+1)

end

end;



Заключение

В данной курсовой работе было проведено исследование ряда различных методов порождения и перебора комбинаторных объектов, свойств, преимуществ и недостатков. Кроме того, были рассмотрены и проанализированы основные принципы, по которым строятся различные методы порождения и перебора комбинаторных объектов, а так же возможные ситуации, оптимальные для применения того или иного метода. Помимо этого, настоящая работа содержит небольшой экскурс в более чем тысячелетнюю историю задачи перебора комбинаторных объектов.

Рассматривая вопрос перебора комбинаторных объектов, можно сделать вывод, что методы перебора комбинаторных объектов представляют собой частный пример того, как следует подходить к решению проблем вообще.



Список использованной литературы

1. Федоряева Т.И. Комбинаторые алгоритмы: Учебное пособие

2. Ксавье Ж.В. Перечислительная комбинаторика и информатика

3. https://www.mdpi.com

4. https://en.wikipedia.org

Размещено на Allbest.ru

...