Графы и их применение. Комбинаторные алгоритмы для программистов

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

2-е издание, исправленное

Костюкова Н.И.

Национальный Открытый Университет “ИНТУИТ”
2016

2

УДК 519.1(07)
ББК 16
К72
Графы и их применение. Комбинаторные алгоритмы для программистов / Костюкова Н.И. - M.:
Национальный Открытый Университет “ИНТУИТ”, 2016 (Основы информационных технологий)
ISBN 978-5-9556-0069-7

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

(c) ООО “ИНТУИТ.РУ”, 2007-2016
(c) Костюкова Н.И., 2007-2016

3

Комбинаторные вычисления

Введение. Проблема представления: коды, сохраняющие разности. Классы алгоритмов.
Анализ алгоритмов. Программа.

Введение

Комбинаторная математика является старой дисциплиной. Она получила свое
наименование в 1666 г. от Лейбница в его “Dissertation de Arte Combinatori”.
Комбинаторные алгоритмы с их акцентом на разработку, анализ и реализацию
практических алгоритмов являются продуктом века вычислительных машин.

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

Комбинаторные вычисления находятся в таком же отношении к комбинаторной
математике (дискретной, конечной математике), как численные методы анализа - к
анализу. Комбинаторные вычисления развиваются в следующем направлении:

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

В отличие от некоторых других разделов математики, комбинаторные вычисления не
имеют “ядра”, то есть некоторого количества “фундаментальных теорем”,
составляющих суть предмета, из которых выводится большинство результатов.
Сначала может показаться, что в целом эта область состоит из наборов специальных
методов и хитрых приемов. Однако после того, как было исследовано достаточно
много комбинаторных алгоритмов, стали вырисовываться некоторые общие принципы.
Именно эти принципы делают комбинаторные вычисления связной областью знаний и
позволяют изложить ее в систематизированном виде.

Проблема представления: коды, сохраняющие разности

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

Приведем примеры, в которых задаются весьма специфические операции над целыми.

4

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

1. Необходимы целые, больше имеющихся непосредственно в аппаратном

оборудовании.

2. Необходимы только небольшие целые, и требуется сэкономить память,

упаковывая их по несколько в одну ячейку.

3. Действия с целыми производятся не общепринятыми арифметическими

операциями.

4. Целые используются для представления других типов объектов, и необходимо

иметь возможность легко обращать целое в соответствующий ему объект и
обратно.

Проблемы кодов, сохраняющих разности, касаются случаев 2 и 3. В задачах
распознавания образов и классификации для решения вопроса, будут ли два объекта

 эквивалентными,стандартной является следующая процедура. 

представляются векторами признаков 
 соответственно, где

каждая компонента означает признак объекта, выраженный целым значением.
Считается, что 
эквиваленты тогда и только тогда, если

где  — целое, называемое порогом.

Классы алгоритмов

Одной из причин быстрого прогресса комбинаторных вычислений является усиление
внимания к исследованию классов алгоритмов в противоположность изучению
отдельных из них. Для того чтобы утверждать, например, что “все алгоритмы,
предназначенные для выполнения того-то и того-то, должны обладать такими-то и
такими-то свойствами” или “не существует алгоритма, удовлетворяющего тому-то и
тому-то”, необходимо иметь дело с четко определенным классом алгоритмов. Именно
при таком определении становится возможным говорить, что данный алгоритм
является оптимальным по отношению к некоторому свойству, если он работает по
крайней мере так же хорошо (относительно этого свойства), как любой другой
алгоритм из рассматриваемого класса.

Как можно строго определить, возможно, бесконечный, класс алгоритмов? Исследуем
этот вопрос на примере задачи о фальшивой монете. Рассматриваемый в этом примере
класс алгоритмов порождает более обширный и более важный класс алгоритмов - так
называемые деревья решений.

5

Задача. Имеется  монет, о которых известно, что 
 из них являются настоящими и

не более чем одна монета, фальшивая (легче или тяжелее остальных монет).
Дополнительно к группе из  сомнительных монет дается еще одна монета, причем
заведомо известно, что она настоящая. Имеются также весы, с помощью которых
можно сравнить общий вес любых 
 монет с общим весом любых других 
 монет и

тем самым установить, имеют ли две группы по 
 монет одинаковый вес либо одна из

групп легче другой. Задача состоит в том, чтобы найти фальшивую монету, если она
есть, за наименьшее число взвешиваний, или сравнений.

Решение Пусть сомнительные монеты занумерованы числами 
. Монете, о

которой известно, что она настоящая, поставим в соответствие номер 0. Пусть 

 - множество монет. Если 
 — непересекающиеся непустые

подмножества множества 
, то через 
 обозначим операцию сравнения весов

множества 
. При сравнении возможны три исхода, которые обозначим

следующим образом: 
 в зависимости от того, является ли вес 

меньшим, равным или большим веса 
.

Рассматриваемые алгоритмы можно представить в форме дерева решений.

Рис. 1.1.  Дерево решений для задачи о фальшивой монете с четырьмя монетами

Корень дерева на рисунке изображен полой окружностью и помечен отношением 
.

Это означает, что алгоритм начинает работу сравнением весов монет с номерами 1 и 2.
Три исходящие из корня ветви ведут к поддеревьям, определяющим продолжение
работы алгоритма после каждого из трех возможных исходов первого сравнения.
Окружности, залитые черной краской, называются листьями дерева и означают, что
работа алгоритма заканчивается. Метки соответствуют исходам: “1л” - монета 1 легкая,
“1т” - монета 1 тяжелая, “н” - все монеты настоящие. Непомеченная вершина дерева
означает, что при наших предположениях этот случай возникнуть не может.

Алгоритм, приведенный на рис. 1.1, требует двух сравнений в одних случаях и трех - в
других. Скажем, что он требует “трех сравнений в худшем случае”. Обычно важно

6

знать, сколько работы требует алгоритм в среднем, однако для этого требуется задать
вероятности различных исходов. Если предположим, что все восемь исходов 1л, 1т, 2л,
2т, 3л, 3т, 4л, 4т, - равновероятны, то тогда этот алгоритм требует в среднем 7/3
сравнений.

На одну чашку весов можем положить больше одной монеты. Например, можно начать
сравнения, положив на одну чашку весов монеты 1 и 2, а на другую - монеты 3 и 4 (рис.
1.2).

Рис. 1.2.  Корень другого дерева решений для задачи о четырех монетах

Если посчастливится, задачу можно решить за одно сравнение - это может произойти,
когда все монеты настоящие. Независимо от того, как дополняется это дерево решений,
в худшем случае задача все равно потребует тех же трех сравнений, поскольку
единственное тернарное решение не может идентифицировать один из четырех
исходов, которые возможны на ветви, помеченной символом ” 
 “, так же как и один

из четырех исходов на ветви, помеченной символом ” 
 “. К тому же, независимо от

того, как дополняется это дерево решений, оно потребует в среднем по крайней мере
7/3 сравнений, и в этом случае оно не лучше, чем дерево на рис.1.1.

Используя монету 0, о которой известно, что она настоящая, можно получить
приведенное на рис. 1.3 дерево решений (полное двухъярусное тернарное дерево),
которое и в худшем, и в среднем случае требует двух сравнений.

Рис. 1.3.  Оптимальное дерево решений для задачи о четырех монетах

Рассматриваемый класс алгоритмов решения задачи о фальшивой монете есть
множество тернарных деревьев решений (примеры на рис.1.1, рис.1.2, рис.1.3),
обладающих следующими свойствами:

7

каждый узел помечен сравнением 
, где 
 и 
 - непересекающиеся

непустые подмножества множества 
 всех монет;

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

Поскольку в задаче о четырех монетах требуется различить девять возможных исходов,
любое дерево решений для этой задачи должно иметь, по крайней мере, девять листьев
и, следовательно, не менее двух ярусов. Поэтому дерево на рис.1.3 является
оптимальным и для худшего случая, и для среднего. Существуют ли другие
оптимальные деревья? Для ответа на этот вопрос нужно рассмотреть множество всех
деревьев решений для задачи о четырех монетах. Попытаемся исключить из
дальнейшего рассмотрения какую-либо часть этого множества. Прежде всего видно,
что путем любой перестановки множества 
 сомнительных монет из одного

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

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

разбиение исходов по трем ветвям, выходящим из корня, как показано на рис.1.2. Для
получения такого, как на рис.1.3, полного двухъярусного тернарного дерева, девять
возможных исходов должны были бы быть разбиты в отношении (3, 3, 3). Они же
вместо этого разбиваются, соответственно, в отношении (2, 5, 2) и (4,1,4). Таким
образом, заключаем, что задачу для четырех монет нельзя решить за два сравнения, не
используя дополнительную настоящую монету.

Наконец, рассмотрим те деревья решений, которые используют монету 0 в корне. В
этом случае видно, что в корне фактически возможны только два сравнения: 
 и 

. Для первого сравнения набор исходов будет (1, 7, 1), в связи с чем все

алгоритмы, начинающиеся таким способом, для нас непригодны. Набор исходов (3, 3,
3) приводит к оптимальному дереву, показанному на рис.1.3. Аналогичным образом
устанавливается, что для оптимального дерева сравнения в первом от корня ярусе
определяются единственным образом. Отсюда заключаем, что для задачи о четырех
монетах фактически существует только одно оптимальное дерево.

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

8

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

Поскольку число листьев в дереве решений должно быть по крайней мере таким же,
как и число возможных исходов задачи ( 
 для задачи о монетах), сразу же можно

получить нижнюю оценку необходимого числа сравнений (или, что эквивалентно,
верхнюю оценку числа монет для данного сравнения).

Анализ алгоритмов

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

Из-за трудностей анализа им зачастую просто пренебрегают. Вместо этого программа
выполняется для того, чтобы увидеть, что получается (например, измеряется время
работы). Такой подход можно признать удовлетворительным, если есть основание
полагать, что тестовые задачи достаточно хорошо характеризуют работу алгоритма в
общем случае; если же это не так, то описанный подход даст мало ценной информации.
Даже если тест прекрасно характеризует работу алгоритма, он никогда не даст ответ на
придирчивый вопрос, могут ли существовать лучшие алгоритмы для решения той же
самой задачи. Проблему оптимальности алгоритма можно решить только путем его
анализа.

В анализе алгоритмов существуют две фундаментальные проблемы:

Какими свойствами обладает данный алгоритм?
Какие свойства должен иметь любой алгоритм, решающий данную проблему?

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

Программа

9

Программа 1.Поиск фальшивой монеты

//Монета ищется простым перебором.
//Алгоритм реализован на языке программирования Turbo-C++.
#include <stdlib.h>
#include <conio.h>
#include <stdio.h>
int main() {
        clrscr();
        int k, n, flag = -1;
        int *mas;
    printf("Введите число монет: ");
        scanf("%i", &n);
        mas = (int*)malloc(sizeof(n));
        randomize();
        k = random (10) + 1;
        for (int i = 0; i < n; i++) {
                mas[i] = k;
        }
        for (i = k; i == k; i = random (20));
        mas[random (n)] = i;
        printf("Масса монет: ");
        for (i = 0; i < n; i++) {
                printf("%5i", mas[i]);
                if (mas[i] != k) {
                        flag = i;
                }
        }
        printf("\nФальшивая монета под номером %i ее вес %i", flag+1,
mas[flag]);
        getch();
        free(mas);
        return 0;
}

10