В общем случае при создании компьютерной программы мы реализуем метод, который ранее был разработан для решения какой-либо задачи. Часто этот метод не зависит от конкретного используемого компьютера — он примерно одинаково пригоден для многих компьютеров и многих компьютерных языков. именно метод, а не саму программу нужно исследовать для выяснения способа решения задачи. Для метода решения задачи, пригодного для реализации в виде компьютерной программы, в компьютерных науках используется термин алгоритм. Алгоритмы составляют основу компьютерных наук: это основные объекты изучения во многих, если не в большинстве областей этих наук.
В основном представляющие интерес алгоритмы тесно связаны с методами организации данных, участвующих в вычислениях. Созданные таким образом объекты называются структурами данных, и они также являются центральными объектами изучения в компьютерных науках. То есть алгоритмы и структуры данных идут рука об руку. В этом курсе мы покажем, что структуры данных существуют в качестве побочных или конечных продуктов алгоритмов и, следовательно, их нужно изучить, чтобы понять алгоритмы. Простые алгоритмы могут порождать сложные структуры данных и наоборот, сложные алгоритмы могут использовать простые структуры данных. В этом курсе будут изучены свойства множества структур данных, так что курс вполне мог бы называться "Алгоритмы и структуры данных на C++".
Когда компьютер используется для решения той или иной задачи, как правило, имеется целый ряд возможных различных подходов. При решении простых задач выбор того или иного подхода вряд ли имеет особое значение, если только выбранный подход приводит к правильному решению. Однако при решении очень сложных задач (или в приложениях, в которых приходится решать очень большое количество простых задач) мы сталкиваемся с необходимостью разработки методов, в которых время или память используются с максимальной эффективностью.
Основная побудительная причина изучения алгоритмов состоит в том, что это позволяет обеспечить огромную экономию ресурсов, вплоть до получения решений задач, которые в противном случае были бы невозможны. В приложениях, в которых обрабатываются миллионы объектов, часто хорошо разработанный алгоритм позволяет ускорить работу программы в миллионы раз. Подобный пример приводится в разделе 1.2 и в множестве других разделов курса. Для сравнения: затраты дополнительных денег или времени для приобретения и установки нового компьютера потенциально позволяет ускорить работу программы всего в 10—100 раз. Тщательная разработка алгоритма — исключительно эффективная часть процесса решения сложной задачи в любой области применения.
При разработке очень большой или сложной компьютерной программы значительные усилия должны затрачиваться на уяснение и формулировку задачи, которая должна быть решена, осознание ее сложности и разбиение ее на менее сложные подзадачи, решения которых можно легко реализовать. Зачастую реализация многих алгоритмов, требуемых после разбиения, тривиальна. Однако в большинстве случаев существует несколько алгоритмов, выбор которых критичен, поскольку для их выполнения требуется большая часть системных ресурсов. Именно этим типам алгоритмов уделяется основное внимание в данном курсе. Мы изучим ряд основополагающих алгоритмов, которые полезны при решении сложных задач во многих областях применения.
Совместное использование программ в компьютерных системах становится все более распространенным, поэтому, хотя можно ожидать, что использовать придется многие из рассмотренных в курсе алгоритмов, одновременно можно надеяться, что реализовывать придется лишь немногие из них. Например, библиотека стандартных шаблонов (Standard Template Library) C++ содержит реализации множества базовых алгоритмов. Однако реализация простых версий основных алгоритмов позволяет лучше их понять и, следовательно, эффективнее использовать и настраивать более совершенные библиотечные версии. И что еще важнее, очень часто возникает необходимость самостоятельной реализации основных алгоритмов. Основная причина состоит в том, что мы очень часто сталкиваемся с совершено новыми вычислительными средами (аппаратными и программными), новые свойства которых не могут наилучшим образом использоваться старыми реализациями. То есть чтобы наши решения были более переносимыми и применимыми, часто приходится реализовывать базовые алгоритмы, приспособленные к конкретной задаче, а не основывающиеся на системных подпрограммах. Другая часто возникающая причина самостоятельной реализации базовых алгоритмов заключается в том, что несмотря на усовершенствования, встроенные в C++, механизмы, используемые для совместного использования программ, не всегда достаточно мощны, чтобы библиотечные программы можно было легко приспособить к эффективному выполнению конкретных задач.
Компьютерные программы часто чрезмерно оптимизированы. Обеспечение наиболее эффективной реализации конкретного алгоритма может не стоить затраченных усилий, если только алгоритм не должен использоваться для решения очень сложной задачи или же многократно. В противном случае вполне сгодится качественная, сравнительно простая реализация: достаточно быть уверенным в ее работоспособности и в том, что, скорее всего, в худшем случае она будет работать в 5—10 раз медленнее наиболее эффективной версии, что может означать увеличение времени выполнения на несколько дополнительных секунд. И напротив, правильный выбор алгоритма может ускорить работу в 100—1000 и более раз, что во время выполнения может сэкономить минуты, часы и даже более того. В этом курсе основное внимание уделяется простейшим приемлемым реализациям наилучших алгоритмов.
Выбор наилучшего алгоритма выполнения конкретной задачи может оказаться сложным процессом, возможно, требующим нетривиального математического анализа. Направление компьютерных наук, занимающееся изучением подобных вопросов, называется анализом алгоритмов. Анализ многих изучаемых алгоритмов показывает, что они имеют прекрасную производительность; о хорошей работе других известно просто из опыта их применения. Наша основная цель — изучение приемлемых алгоритмов выполнения важных задач, хотя значительное внимание будет уделено также сравнительной производительности различных методов. Не следует использовать алгоритм, не имея представления о ресурсах, которые могут потребоваться для его выполнения, поэтому мы стараемся узнать, как могут выполняться используемые алгоритмы.
Предположим, что имеется последовательность пар целых чисел, в которой каждое целое число представляет объект некоторого типа, а пара .
(рис 1.1) Пример связности
При заданной последовательности пар целых чисел, представляющих связи между объектами (слева) алгоритм определения связности должен выводить только те пары, которые определяют новые связи (в центре). Например, пара 2-9 не должна выводиться, поскольку связь 2-3-4-9 определяется ранее указанными связями (подтверждение этого показано справа).
Задача состоит в разработке программы, которая может запомнить достаточный объем информации о просмотренных парах, чтобы решить, связана ли новая пара объектов. Неформально задачу разработки такого метода мы назовем задачей связности. Эта задача возникает в ряде важных приложений. Для подтверждения всеобщего характера этой задачи мы кратко рассмотрим три примера.
Например, целые числа могли бы представлять компьютеры в большой сети, а пары могли бы представлять соединения в сети. Тогда такая программа могла бы использоваться для определения того, нужно ли устанавливать новое прямое соединение между p и q, чтобы они могли обмениваться информацией, или же для установки коммуникационного пути можно использовать существующие соединения. В подобных приложениях может потребоваться обработка миллионов точек и миллиардов или более соединений. Как мы увидим, решить задачу для такого приложения было бы невозможно без эффективного алгоритма. Аналогично, целые числа могли бы представлять контакты в электрической сети, а пары могли бы представлять связывающие их проводники. В этом случае программу можно было бы использовать для определения способа соединения всех точек без каких-либо избыточных соединений, если это возможно. Не существует никакой гарантии, что связей в списке окажется достаточно для соединения всех точек — действительно, вскоре мы увидим, что определение факта, так ли это, может быть основным применением нашей программы.
На рис 1.2 показаны эти два типа применений на более сложном примере. Изучение этого рисунка дает представление о сложности задачи связности: как можно быстро выяснить, являются ли любые две заданные точки в такой сети связанными?
Еще один пример встречается в некоторых средах программирования, в которых два имени переменных можно объявлять эквивалентными. Задача заключается в возможности определения, являются ли два заданных имени эквивалентными, после считывания последовательности таких объявлений. Это применение — одно из первых, обусловивших разработку нескольких алгоритмов, которые мы рассмотрим ниже. Как будет показано далее, оно устанавливает непосредственную связь между рассматриваемой задачей и простой абстракцией, предоставляющей способ сделать алгоритмы полезными для широкого множества приложений.
Такие приложения, как задача установления эквивалентности имен переменных, описанная в предыдущем абзаце, требует, чтобы с каждым отдельным именем переменной было сопоставлено целое число. Это сопоставление подразумевается также и в описанных приложениях сетевого соединения и соединения в электрической цепи. В лекциях 10—16 мы рассмотрим ряд алгоритмов, которые могут эффективно обеспечить такое сопоставление. Таким образом, в этой лекции без ущерба для общности можно предположить, что имеется N объектов с целочисленными именами от 0 до N — 1 .
(рис 1.2) Большой пример задачи связности
Объекты, задействованные в задаче связности, могут представлять собой точки соединений, а пары могут быть соединениями между ними — как показано в этом идеализированном примере, который мог бы представлять провода, соединяющие здания в городе или компоненты в компьютерной микросхеме. Это графическое представление позволяет человеку выявить несвязанные узлы, но алгоритм должен работать только с переданными ему парами целых чисел. Связаны ли два узла, помеченные большими черными точками?
Нам требуется программа, которая выполняет конкретную, вполне определенную задачу. Существует множество других связанных с этой задач, решение которых также может потребоваться. Один из первых вопросов, который необходимо решить при разработке алгоритма — это убедиться, что задача определена приемлемым образом. Чем выше требования к алгоритму, тем больше времени и объема памяти может потребоваться для выполнения задачи. Это соотношение невозможно в точности определить заранее, и часто определение задачи приходится изменять, когда выясняется, что ее трудно решить, либо решение требует слишком больших затрат, или же когда, при удачном стечении обстоятельств, выясняется, что алгоритм может предоставить более полезную информацию, чем требовалось от него в исходном определении.
Например, приведенное определение задачи связности требует только, чтобы программа как-либо узнавала, является ли данная пара и подробно — в части VII.
Упомянутые в предыдущем абзаце определения требуют больше информации, чем первоначальное; может также требоваться и меньше информации. Например, может потребоваться просто ответить на вопрос: "Достаточно ли ). Иначе говоря, алгоритм решения задачи связности никогда не выводит более N — 1 пар, поскольку как только он выведет N — 1 пару, любая встретившаяся после этого пара будет уже связанной. Соответственно, можно создать программу, отвечающую "да-нет" на только что поставленный вопрос, изменив программу, которая решает задачу связности, на такую, которая увеличивает значение счетчика, а не записывает ранее не связанную пару, отвечая "да", когда значение счетчика достигает N— 1 , и "нет", если это не происходит. Этот вопрос — всего лишь один из множества вопросов, которые могут возникнуть относительно связности. Входной набор пар называется графом (graph), а выходной набор пар — остовным деревом (spanning tree) этого графа, которое связывает все объекты. Свойства графов, остовных деревьев и всевозможные связанные с ними алгоритмы будут рассматриваться в части VII.
Имеет смысл попытаться определить основные операции, которые будут выполняться для решения задачи связности, чтобы любой алгоритм, разрабатываемый для ее решения, был полезен и для ряда аналогичных задач. В частности, при получении каждой новой пары вначале необходимо определить, представляет ли она новое соединение, а затем внедрить информацию об обнаруженном соединении в общую картину о связности объектов для проверки соединений, которые будут наблюдаться в будущем. Мы инкапсулируем эти две задачи в виде абстрактных операций, считая целочисленные вводимые значения представляющими элементы в абстрактных наборах, а затем разработаем алгоритмы и структуры данных, которые могут:
Организация алгоритмов посредством этих абстрактных операций, похоже, не отсекает никакие варианты решения задачи связности, и эти операции могут оказаться полезными при решении других задач. Разработка уровней абстракции с еще большими возможностями — важный процесс в компьютерных науках в целом и в разработке алгоритмов в частности, и в этом курсе мы будем обращаться к нему многократно. В данной лекции для разработки программ решения задачи связности мы используем неформальное абстрактное представление; а в эти абстракции будут выражены в коде C++.
Задача связности легко решается с помощью абстрактных операций поиск (find) и объединение (union). После считывания новой пары p-q мы выполняем операцию поиск для каждого члена пары. Если оба члена пары находятся в одном множестве, мы переходим к следующей паре; если нет, то выполняем операцию объединение и записываем пару. Наборы представляют собой связанные компоненты: подмножества объектов, характеризующиеся тем, что любые два объекта в данном компоненте связаны. Этот подход сводит разработку алгоритмического решения задачи связности к задачам определения структуры данных, которая представляет множества, и разработке алгоритмов объединение и поиск, которые эффективно используют эту структуру данных.
Существует много возможных способов представления и обработки абстрактных множеств. В этой лекции основное внимание уделяется поиску представления, которое может эффективно поддерживать операции объединение и поиск, необходимые для решения задачи связности.
Упражнения
1.1. Приведите выходные данные, которые должен выдавать алгоритм связности для входных пар 0-2, 1-4, 2-5, 3-6, 0-4, 6-0 и 1-3.
1.2. Перечислите все различные способы связывания двух различных объектов, показанных в примере на рис 1.1.
1.3. Опишите простой метод подсчета количества наборов, остающихся после применения операций объединение и поиск для решения задачи связности, как описано в тексте.
Первый шаг в процессе разработки эффективного алгоритма решения данной задачи — реализация простого алгоритма ее решения. Если нужно решить несколько вариантов конкретной задачи, которые оказываются простыми, это может быть выполнено посредством простой реализации. Если требуется более сложный алгоритм, то простая реализация предоставляет возможность проверить правильность работы алгоритма для простых случаев и может служить базовым замером для оценки характеристик производительности. Эффективность важна всегда, но при разработке первой программы решения задачи в первую очередь необходимо убедиться в том, что программа обеспечивает правильное решение.
Первое, что приходит в голову — организовать способ сохранения всех вводимых пар, а затем создать функцию для их просмотра, чтобы попытаться выяснить, связана ли очередная пара объектов. Однако мы используем другой подход. Во-первых, количество пар может быть настолько велико, что не позволит хранить их все в памяти в используемом на практике приложении. Во-вторых, что гораздо важнее, не существует никакого простого метода, который сам по себе позволяет определить, связаны ли два объекта в наборе всех соединений, даже если бы удалось их все сохранить! Базовый метод, использующий этот подход, рассматривается в , а методы, которые рассматриваются в этой лекции, проще, поскольку они решают менее сложную задачу, и эффективнее, поскольку не требуют хранения всех пар. Для хранения информации, необходимой для реализации операций объединение и поиск, все эти методы используют массив целых чисел, каждое из которых соответствует отдельному объекту.
Массивы — это элементарные структуры данных, которые подробно будут рассмотрены в . Здесь же они используются в простейшей форме: мы объявляем, что собираемся использовать, скажем, 1000 целых чисел, записывая a[1000], а затем обращаемся к i-ому целому числу в массиве с помощью записи a[i] для $$${0}\leq{i}<1000$$$.
Программа 1.1 — реализация простого алгоритма, называемого алгоритмом быстрого поиска, который решает задачу связности. В основе этого алгоритма лежит использование массива целых чисел, обладающих тем свойством, что p и q связаны тогда и только тогда, когда p-й и q-й элементы массива равны. Вначале i-й элемент массива инициализируется значением i, $$${0}\leq{i}<N$$$. Чтобы реализовать операцию объединение для p и q, мы просматриваем массив, заменяя все элементы с тем же именем, что и p, на элементы с тем же именем, что и q. Этот выбор произволен — можно было бы все элементы с тем же именем, что и q, заменять на элементы с тем же именем, что и p.
Изменения в массиве при выполнении операций объединение в примере из рис 1.1 показаны на рис 1.3. Для реализации операции поиск достаточно проверить указанные записи массива на предмет равенства — отсюда и название быстрый поиск (quick find). Однако операция объединение требует просмотра всего массива для каждой вводимой пары.
Лемма 1.1. Алгоритм быстрого поиска выполняет не менее M x N инструкций для решения задачи связности при наличии N объектов, для которых требуется выполнение M операций объединения.
Для каждой из M операций объединение цикл for выполняется N раз. Для каждой итерации требуется выполнение, по меньшей мере, одной инструкции (если только проверять, завершился ли цикл). $$$\blacksquare$$$
Программа 1.1. Решение задачи связности методом быстрого поиска
Эта программа считывает из стандартного ввода последовательность пар неотрицательных целых чисел, меньших чем N (интерпретируя пару p
).
#include <iostream.h>
static const int N = 10000;
int main() {
int i, p, q, id[N];
for ( i = 0; i < N; i++) id[i] = i;
while (cin >> p >> q) {
int t = id[p];
if (t == id[q]) continue;
for ( i = 0; i < N; i++)
if (id[i] == t) id[i] = id[q];
cout << " " << p << " " << q << endl;
}
}
(рис 1.3) Пример быстрого поиска (медленное объединение)
Здесь изображено содержимое массива id после обработки каждой пары, приведенной слева, алгоритмом быстрого поиска (программа 1.1). Затененные записи — те, которые изменяются для выполнения операции объединение. При обработке пары p
q во все записи со значением id[p] заносится значение из id[q].
Современные компьютеры могут выполнять десятки или сотни миллионов инструкций в секунду, поэтому для малых значений .
Графическое представление массива, показанного на рис 1.3, приведено на рис 1.4. Можно считать, что некоторые объекты представляют множество, к которому они принадлежат, а остальные указывают на представителя их множества. Причина обращения к такому графическому представлению массива вскоре станет понятна. Обратите внимание, что связи между объектами в этом представлении не обязательно соответствуют связям во вводимых парах — они представляют собой информацию, запоминаемую алгоритмом, которая позволяет определить, соединены ли пары, которые будут вводиться в будущем.
А теперь мы рассмотрим дополнительный к предыдущему метод, который называется алгоритмом быстрого объединения. В его основе лежит та же структура данных — индексированный по именам объектов массив — но в нем используется иная интерпретация значений, что приводит к более сложной абстрактной структуре. Каждый объект указывает на другой объект в этом же множестве, образуя структуру, не содержащую циклов. Чтобы определить, находятся ли два объекта в одном множестве, мы следуем указателям для каждого из них до тех пор, пока не будет достигнут объект, который указывает на самого себя. Объекты находятся в одном множестве тогда и только тогда, когда этот процесс приводит от них к одному и тому же объекту. Если они не находятся в одном множестве, процесс завершится на разных объектах (которые указывают на себя). Тогда для образования объединения достаточно связать один объект с другим — отсюда и название быстрое объединение (quick union).
На рис 1.5 показано графическое представление, которое соответствует рис 1.4 при выполнении алгоритма быстрого объединения для массива, изображенного на рис 1.1, а на рис 1.6 показаны соответствующие изменения в массиве id. Графическое представление структуры данных позволяет сравнительно легко понять действие алгоритма — пары объектов, которые соединены во входных данных, связаны один с другим и в структуре данных. Обратите внимание: здесь, как и ранее, связи в структуре данных не обязательно совпадают со связями, заданными вводимыми парами; вместо этого они создаются алгоритмом так, чтобы обеспечить эффективную реализацию операций объединение и поиск.
(рис 1.4) Представление быстрого поиска в виде дерева
На этом рисунке показано графическое представление примера, приведенного на рис 1.3. Связи на этом рисунке не обязательно представляют связи во входных данных. Например, структура, показанная на нижнем рисунке, содержит связь 1-7, которая отсутствует во входных данных, но образуется в результате цепочки связей 7-3-4-9-5-6-1.
(рис 1.5) Представление быстрого объединения в виде дерева
Этот рисунок — графическое представление примера, показанного на рис 1.3. Мы проводим линию от объекта i к объекту id[i].
(рис 1.6) Пример быстрого объединения (не очень быстрый поиск)
Здесь изображено содержимое массива id после обработки каждой из показанных слева пар алгоритмом быстрого поиска (программа 1.1). Затененные элементы — те, которые изменяются для выполнения операции объединения (по одной на каждую операцию). При обработке пары p
q мы переходим по указателям из p до записи i, у которой id[i] == i; потом переходим по указателям из q до записи j, у которой id[j] == j; затем, если i и j различны, устанавливаем id[i] = id[j]. При выполнении операции поиска для пары 5-8 (последняя строка) i принимает значения 5 6 9 0 1, а j — значения 8 0 1.
Связанные компоненты, изображенные на . Деревья, изображенные на рис 1.5, удобны для выполнения операций объединение и поиск, поскольку их можно быстро построить, и они характеризуются тем, что два объекта связаны в дереве тогда и только тогда, когда объекты связаны во входных данных. Перемещаясь вверх по дереву, можно легко отыскать корень дерева, содержащего каждый объект, и, следовательно, можно выяснить, связаны они или нет. Каждое дерево содержит только один объект, указывающий сам на себя, называемый корнем (root) дерева. Указатель на себя на диаграммах не показан. Начав с любого объекта дерева и перемещаясь к объекту, на который он указывает, затем следующему указанному объекту и т.д., мы всегда со временем попадаем к корню. Справедливость этого свойства можно доказать методом индукции: это справедливо после инициализации массива, когда каждый объект указывает на себя, и если это справедливо до выполнения любой операции объединение, это безусловно справедливо и после нее.
Диаграммы для алгоритма быстрого поиска, показанные на рис 1.4, характеризуются теми же свойствами, которые описаны в предыдущем абзаце. Различие состоит в том, что в деревьях быстрого поиска мы достигаем корня из всех узлов, переходя лишь по одной ссылке, а в дереве быстрого объединения для достижения корня может потребоваться переход по нескольким ссылкам.
Программа 1.2 — реализация операций объединение и поиск, образующих алгоритм быстрого объединения для решения задачи связности. Похоже, что алгоритм быстрого объединения работает быстрее алгоритма быстрого поиска, поскольку для каждой вводимой пары ему не нужно просматривать весь массив; но насколько быстрее? В данном случае ответить на этот вопрос труднее, чем в случае быстрого поиска, поскольку время выполнения в большей степени зависит от характера входных данных. Выполнив экспериментальные исследования или математический анализ (см. ), можно показать, что программа 1.2 значительно эффективнее программы 1.1, и ее можно использовать для решения очень сложных реальных задач. Одно из таких экспериментальных исследований будет рассмотрено в конце этого раздела. А пока быстрое объединение можно считать усовершенствованием, поскольку оно устраняет основной недостаток алгоритма быстрого поиска (тот факт, что для выполнения M операций объединение между N объектами программе требуется выполнение, по меньшей мере, N M инструкций).
Программа 1.2. Решение задачи связности методом быстрого объединения
Если тело цикла while в программе 1.1 заменить этим кодом, мы получим программу, которая соответствует тем же спецификациям, что и программа 1.1, но выполняет меньше вычислений для операции объединение за счет выполнения большего количества вычислений для операции поиск. Циклы for и последующий оператор if в этом коде определяют необходимые и достаточные условия связности p и q в массиве id. Оператор присваивания id[i] = j реализует операцию объединение.
for (i = p; i != id[i]; i = id[i]) ;
for (j = q; j != id[j]; j = id[j]) ;
if (i == j) continue;
id[i] = j;
cout << " " << p << " " << q << endl;
Это различие между быстрым объединением и быстрым поиском действительно повышает производительность, однако у быстрого объединения есть недостаток: нельзя гарантировать, что оно будет выполняться существенно быстрее быстрого поиска в каждом случае, поскольку характер входных данных может замедлить операцию поиск.
Лемма 1.2. Для M пар из N объектов, когда M > N , решение задачи связности алгоритмом быстрого объединения может потребовать выполнения более чем MN/2 инструкций.
Предположим, что пары вводятся в следующем порядке: 1-2, 2-3, 3-4 и т.д. После ввода N — 1 таких пар мы получим N объектов, принадлежащих к одному множеству, а сформированное алгоритмом быстрого объединения дерево представляет собой прямую линию, где объект N указывает на объект N — 1 , тот, в свою очередь, — на объект N — 2, тот — на N — 3 и т.д. Чтобы выполнить операцию поиск для объекта N, программа должна перейти по N — 1 указателям. Таким образом, среднее количество указателей, по которым выполняются переходы для первых N пар, равно
(0 + 1 +...+ (N - 1))/N = (N-1)/2
Теперь предположим, что все остальные пары связывают объект N с каким-либо другим объектом. Чтобы выполнить операцию поиск для каждой из этих пар, требуется перейти, по меньшей мере, по (N - 1) указателям. Общий итог для M операций поиск при такой последовательности вводимых пар определенно больше M N/2. $$$\blacksquare$$$
К счастью, можно легко модифицировать алгоритм, чтобы худшие случаи, подобные этому, гарантированно не имели места. При выполнении операции объединение можно не произвольным образом соединять второе дерево с первым, а отслеживать количество узлов в каждом дереве и всегда соединять меньшее дерево с большим. Это изменение требует несколько более объемного кода и наличия еще одного массива для хранения счетчиков узлов, как показано в программе 1.3, но оно ведет к существенному повышению эффективности. Мы будем называть этот алгоритм алгоритмом взвешенного быстрого объединения (weighted quick-union algorithm).
Программа 1.3. Взвешенная версия быстрого объединения
Эта программа — модификация алгоритма быстрого объединения (см. программу 1.2), которая в служебных целях для каждого объекта, у которого id[i] == i, поддерживает дополнительный массив sz, где хранятся количества узлов в соответствующих деревьях, чтобы операция объединение могла связывать меньшее из двух указанных деревьев с большим, тем самым предотвращая разрастание длинных путей в деревьях.
#include <iostream.h>
static const int N = 10000;
int main() {
int i, j, p, q, id[N], sz[N];
for (i = 0; i < N; i++) {
id[i] = i; sz[i] = 1;
}
while ( cin >> p >> q) {
for (i = p; i != id[i]; i = id[i]) ;
for (j = q; j != id[j]; j = id[j]) ; if (i == j) continue;
if (sz[i] < sz[j]) {
id[i] = j; sz[j] += sz[i];
} else {
id[j] = i; sz[i] += sz[j];
}
cout << " " << p << " " << q << endl;
}
}
На рис 1.7 показан лес деревьев, созданных алгоритмом взвешенного поиска для примера входных данных с рис 1.1. Даже в этом небольшом примере пути в деревьях существенно короче, чем в случае невзвешенной версии, приведенной на рис 1.5.
На рис 1.8 демонстрируется, что происходит в худшем случае, когда размеры наборов, которые должны быть объединены в операции объединение, всегда равны (и являются степенью 2). Эти структуры деревьев выглядят сложными, но у них есть простое свойство: максимальное количество указателей, по которым необходимо перейти, чтобы добраться до корня в дереве, состоящем из
2n
узлов, равно п. При слиянии двух деревьев, состоящих из
2n
узлов, получается дерево, состоящее из
2n+1
узлов, а максимальное расстояние до корня увеличивается до п + 1. Это наблюдение можно обобщить для доказательства того, что взвешенный алгоритм значительно эффективнее невзвешенного.
Лемма 1.3. Для определения того, связаны ли два из N объектов, алгоритм взвешенного быстрого объединения переходит максимум по log N указателям.
Можно доказать, что для операции объединение сохраняется свойство, что количество указателей, проходимых из любого узла до корня в множестве к объектов, не превышает log к. При объединении набора, состоящего из i узлов, с набором, состоящим из j узлов, при $$${i}\leq{j}$$$ количество указателей, которые должны отслеживаться в меньшем наборе, увеличивается на 1, но теперь узлы находятся в наборе размера i + j, и свойство остается справедливым, поскольку $$$1+\log{i}={\log(i + i)}\leq{\log (i + j )}$$$. $$$\blacksquare$$$
(рис 1.7) Представление взвешенного быстрого объединения в виде дерева
На этой последовательности рисунков демонстрируется результат изменения алгоритма быстрого объединения, когда корень меньшего из двух деревьев связывается с корнем большего. Расстояние от каждого узла до корня его дерева невелико, поэтому операция поиска выполняется эффективно.
(рис 1.8) Взвешенное быстрое объединение (худший случай)
Наихудшая ситуация для алгоритма взвешенного быстрого объединения — когда каждая операция объединения связывает деревья одинакового размера. Если количество объектов меньше 2n, расстояние от любого узла до корня его дерева меньше п.
Практическая польза леммы 1.3 заключается в том, что количество инструкций, которые алгоритм взвешенного быстрого объединения использует для обработки M ребер между N объектами, не превышает Mlog N, умноженного на некоторую константу (см. упражнение 1.9). Этот вывод резко отличается от вывода, что алгоритм быстрого поиска всегда (а алгоритм быстрого объединения иногда) использует не менее M N/ 2 инструкций. Таким образом, при использовании взвешенного быстрого объединения можно гарантировать решение очень сложных встречающихся на практике задач за приемлемое время (см. упражнение 1.11). Ценой добавления нескольких дополнительных строк кода мы получаем программу, которая при решении очень сложных задач, которые могут встретиться на практике, работает буквально в миллионы раз быстрее, чем более простые алгоритмы.
Из приведенных диаграмм видно, что лишь сравнительно небольшое количество узлов располагаются далеко от корня; действительно, экспериментальное изучение очень сложных задач показывает, что, как правило, для решения практических задач посредством использования алгоритма взвешенного быстрого объединения, реализованного в программе 1.3, требуется линейное время. То есть затраты времени на выполнение алгоритма равны затратам времени на считывание входных данных с постоянным коэффициентом. Вряд ли можно было бы рассчитывать найти более эффективный алгоритм.
Тут же возникает вопрос: можно ли найти алгоритм, обеспечивающий гарантированную линейную производительность. Этот вопрос — исключительно трудный, который уже много лет не дает покоя исследователям (см. ). Существует множество способов дальнейшего совершенствования алгоритма взвешенного быстрого объединения. В идеале было бы желательно, чтобы каждый узел указывал непосредственно на корень своего дерева, но не хотелось бы расплачиваться за это изменением большого количества указателей, как в алгоритме быстрого объединения. К идеалу можно приблизиться, просто делая все проверяемые узлы указывающими на корень. На первый взгляд этот шаг кажется весьма радикальным, но его легко реализовать, а в структуре этих деревьев нет ничего неприкосновенного, и если их можно изменить, чтобы сделать алгоритм более эффективным, то так и следует сделать. Этот метод, названный сжатием пути (path compression), можно легко реализовать, добавляя еще один проход по каждому пути во время выполнения операции объединение и занося в элемент ). Анализ, устанавливающий этот факт, исключительно сложен, но сам метод прост и эффективен. Результат сжатия пути для большого примера показан на рис 1.11.
Существует множество других способов реализации сжатия пути. Например, программа 1.4 представляет собой реализацию, которая сжимает пути, сдвигая каждую ссылку на следующий узел в пути вверх по дереву (см. в контексте рассмотрения основных подходов к анализам алгоритмов.
(рис 1.9) Сжатие пути
Пути в деревьях можно сделать еще короче, просто занося во все просматриваемые объекты указатели на корень нового дерева во время операции объединения, как показано в этих двух примерах. В примере на верхнем рисунке показан результат, соответствующий рис 1.7. В случае коротких путей сжатие пути не оказывает никакого влияния, но после обработки пары 1 6 узлы 1, 5 и 6 указывают на узел 3, в результате чего дерево становится более плоским, чем на рис 1.7. В примере на нижнем рисунке показан результат, соответствующий рис 1.8. В деревьях могут появляться пути, которые содержат больше одной-двух связей, но при каждом прохождении они становятся более плоскими. В данном случае после обработки пары 6 8 дерево становится более плоским, а узлы 4, 6 и 8 указывают на узел 0.
(рис 1.10) Сжатие пути делением пополам
Можно уменьшить длину путей вверх по дереву почти вдвое, беря сразу по две ссылки и занося в нижнюю из них указатель на тот же узел, что и в верхней, как показано в этом примере. Конечный результат выполнения такой операции для каждого проходимого пути приближается к результату, получаемому в результате полного сжатия пути.
(рис 1.11) Большой пример влияния сжатия пути
Здесь отображен результат обработки случайных пар из 100 объектов алгоритмом взвешенного быстрого объединения со сжатием пути. Все узлы этого дерева, кроме двух, находятся на расстоянии одного-двух шагов от корня.
Программа 1.4. Сжатие пути делением пополам
Если циклы for в программе 1.3 заменить этим кодом, длина любого проходимого пути будет уменьшаться в два раза. Конечный результат этого изменения — превращение деревьев в почти совершенно плоские после выполнения длинной последовательности операций.
for (i = p; i != id[i]; i = id[i])
id[i] = id[id[i]];
for (j = q; j != id[j]; j = id[j])
id[j] = id[id[j]];
Конечный результат применения рассмотренных алгоритмов решения задачи связности приближается к наилучшему, на который можно было бы рассчитывать в любом практическом случае. Мы имеем легко реализуемые алгоритмы, время выполнения которых гарантированно пропорционально затратам времени на ввод данных с постоянным коэффициентом. Более того, алгоритмы являются оперативными: они рассматривают каждое ребро только один раз и используют объем памяти, который пропорционален количеству объектов; поэтому какие-либо ограничения на количество обрабатываемых ими ребер отсутствуют. Результаты экспериментального исследования, приведенные в табл. 1.1 .)
| N | M | F | U | W | P | H |
|---|---|---|---|---|---|---|
| 1000 | 6206 | 14 | 25 | 6 | 5 | 3 |
| 2500 | 20236 | 82 | 210 | 13 | 15 | 12 |
| 5000 | 41913 | 304 | 1172 | 46 | 26 | 25 |
| 10000 | 83857 | 1216 | 4577 | 91 | 73 | 50 |
| 25000 | 309802 | 219 | 208 | 216 | ||
| 50000 | 708701 | 469 | 387 | 497 | ||
| 100000 | 1545119 | 1071 | 1106 | 1096 |
Обозначения:
| F | быстрый поиск (программа 1.1) |
| U | быстрое объединение (программа 1.2) |
| W | взвешенное быстрое объединение (программа 1.3) |
| P | взвешенное быстрое объединение со сжатием пути (упражнение 1.16) |
| H | взвешенное быстрое объединение с делением пополам (программа 1.4) |
Эти сравнительные значения времени, затрачиваемого на решение случайных задач связности с использованием алгоритмов объединения-поиска, демонстрируют эффективность взвешенной версии алгоритма быстрого объединения. Дополнительный выигрыш благодаря использованию сжатия пути менее важен. Здесь M — количество случайных соединений, генерируемых до тех пор, пока все N объектов не оказываются связанными. Этот процесс требует значительно больше операций поиск, чем операций объединение, поэтому быстрое объединение выполняется существенно медленнее быстрого поиска. Ни быстрый поиск, ни быстрое объединение не годятся для очень больших N. Время выполнения при использовании взвешенных методов явно пропорционально значению N, поскольку оно уменьшается вдвое при уменьшении N вдвое.
Упражнения
1.4. Приведите содержимое массива id после выполнения каждой операции объединение при использовании алгоритма быстрого поиска (программа 1.1) для решения задачи связности для последовательности 0-2, 1-4, 2-5, 3-6, 0-4, 6-0 и 1-3. Укажите также количество обращений программы к массиву id для каждой вводимой пары.
1.5. Выполните упражнение 1.4, но для алгоритма быстрого объединения (программа 1.2).
1.6. Приведите содержимое массива и рис 1.8.
1.7. Выполните упражнение 1.4, но для алгоритма взвешенного быстрого объединения (программа 1.3).
1.8. Выполните упражнение 1.4, но для алгоритма взвешенного быстрого объединения со сжатием пути делением пополам (программа 1.4).
1.9. Определите верхнюю границу количества машинных инструкций, требующихся для обработки M соединений N объектов при использовании программы 1.3. Например, можно предположить, что для выполнения оператора присваивания C+ + всегда требуется выполнение менее c инструкций, где c — некоторая фиксированная константа.
1.10. Определите минимальное время (в днях), которое потребовалось бы для выполнения быстрого поиска (программа 1.1) для решения задачи с 109 объектов и 106 вводимых пар на компьютере, который может выполнять 109 инструкций в секунду. Считайте, что при каждой итерации внутреннего цикла for должно выполняться не менее 10 инструкций.
1.11. Определите максимальное время (в секундах), которое потребовалось бы для выполнения взвешенного быстрого объединения (программа 1.3) для решения задачи с 1099 объектов и 106 вводимых пар на компьютере, который может выполнять 109 инструкций в секунду. Считайте, что при каждой итерации внешнего цикла while должно выполняться не более 100 инструкций.
1.12. Вычислите среднее расстояние от узла до корня в худшем случае в дереве из 2n узлов, построенном алгоритмом взвешенного быстрого объединения.
1.13. Нарисуйте диаграмму, подобную рис 1.10, но начав с восьми узлов, а не девяти.
1.14. Приведите последовательность вводимых пар, для которой алгоритм взвешенного быстрого объединения (программа 1.3) создает путь длиной 4.
1.15. Приведите последовательность вводимых пар, для которой алгоритм взвешенного быстрого объединения с сжатием пути делением пополам (программа 1.4) создает путь длиной 4.
1.16. Покажите, как необходимо изменить программу 1.3, чтобы реализовать полное сжатие пути, при котором после каждой операции объединение все обработанные узлы указывают на корень нового дерева.
1.17. Выполните упражнение 1.4, но используйте алгоритм взвешенного быстрого объединения с полным сжатием пути (упражнение 1.16).
1.18. Приведите последовательность вводимых пар, для которой алгоритм взвешенного быстрого объединения с полным сжатием пути (см. упражнение 1.16) создает путь длиной 4.
1.19. Приведите пример, показывающий, что изменения быстрого объединения (программа 1.2) для реализации полного сжатия пути (см. упражнение 1.16) не достаточно, чтобы гарантировать отсутствие длинных путей в деревьях.
1.20. Измените программу 1.3, чтобы в ней для принятия решения, нужно ли устанавливать id[i] = j или id[j] = i, вместо веса использовалась высота деревьев (самый длинный путь от любого узла до корня). Экспериментально сравните этот вариант с программой 1.3.
1.21. Покажите, что лемма 1.3 справедлива для алгоритма, описанного в упражнении 1.20.
1.22. Измените программу 1.4, чтобы она генерировала случайные пары целых чисел в диапазоне от 0 до N— 1 вместо того, чтобы считывать их из стандартного ввода, и выполняла цикл до тех пор, пока не будет выполнено N — 1 операций объединение. Выполните программу для значений
N = 103, 104, 105 и 106
и выведите общее количество ребер, генерируемых для каждого значения N.
1.23. Измените программу из упражнения 1.22, чтобы она выводила в виде графика количество ребер, требующихся для соединения N элементов,100 < N< 1000.
1.24. Приведите приближенную формулу для определения количества случайных ребер, требующихся для соединения N объектов, как функции от N.
Каждый из алгоритмов, рассмотренных в разделе 1.3, кажется определенным усовершенствованием предыдущего, но, вероятно, процесс был искусственно упрощен, поскольку разработка самих этих алгоритмов уже была выполнена рядом исследователей в течение многих лет (см. раздел использованной литературы). Реализации просты, а задача четко определена, поэтому мы можем оценить различные алгоритмы непосредственно, экспериментальным путем. Более того, мы можем подкрепить эти исследования, количественно сравнив производительность алгоритмов (см. ). Не все задачи, рассмотренные в этом курсе, столь же хорошо проработаны, как эта, и мы обязательно встретимся с алгоритмами, которые трудно сравнить, и с математическими задачами, которые трудно решить. Мы стремимся принимать объективные научно обоснованные решения об используемых алгоритмах, изучая свойства реализаций на примере их выполнения применительно к реальным данным, полученным из приложений, или случайным тестовым наборам данных.
Этот процесс — прототип того, как различные алгоритмы решения фундаментальных задач рассматриваются в данном курсе. Когда это возможно, мы предпринимаем те же основные шаги, что и при рассмотрении алгоритмов объединения-поиска, описанных в разделе 1.2, часть из которых перечислена ниже:
Потенциальная возможность впечатляющего повышения производительности алгоритмов решения реальных задач, подобных рассмотренным в разделе 1.2, делает разработку алгоритмов увлекательной областью исследования; лишь немногие другие области разработки позволяют обеспечить экономию времени в миллионы, миллиарды и более раз.
Что еще важнее, по мере повышения вычислительных возможностей компьютеров и приложений разрыв между быстрыми и медленными алгоритмами увеличивается. Новый компьютер может работать в 10 раз быстрее и может обрабатывать в 10 раз больше данных, чем старый, но при использовании квадратичного алгоритма, наподобие быстрого поиска, новому компьютеру потребуется в 10 раз больше времени для выполнения новой задачи, чем требовалось старому для выполнению старой! Вначале это утверждение кажется противоречивым, но его легко подтвердить простым тождеством
(10N)2/10 = 10N2
, как будет показано в . По мере того как вычислительные мощности увеличиваются, позволяя решать все более сложные задачи, важность использования эффективных алгоритмов также возрастает.
Разработка эффективного алгоритма приносит моральное удовлетворение и непосредственно окупается на практике. Как видно на примере решения задачи связности, просто сформулированная задача может приводить к изучению множества алгоритмов, которые не только полезны и интересны, но и представляют увлекательную и сложную для понимания задачу. Мы встретимся со многими остроумными алгоритмами, которые были разработаны за долгие годы для решения множества практических проблем. По мере расширения области применения компьютерных решений для научных и экономических проблем возрастает важность использования эффективных алгоритмов для решения известных задач и разработки эффективных решений для новых проблем.
Упражнения
1.25. Допустим, что взвешенное быстрое объединение используется для обработки в 10 раз большего количества соединений на новом компьютере, который работает в 10 раз быстрее старого. На сколько больше времени потребуется для выполнения новой задачи на новом компьютере по сравнению с выполнением старой задачи на старом компьютере?
1.26. Выполните упражнение 1.25 для случая использования алгоритма, который требует выполнения N3 инструкций.
В этом разделе приведены краткие описания основных частей курса и раскрытых в них отдельных тем с указанием общего подхода к материалу. Выбор тем диктовался стремлением осветить как можно больше базовых алгоритмов. Некоторые из освещенных тем относятся к фундаментальным темам компьютерных наук, которые мы подробно изучаем для изучения основных алгоритмов широкого применения. Другие рассмотренные алгоритмы относятся к специализированным областям компьютерных наук и связанным с ними областям, таким как численный анализ и исследование операций — в этих случаях приведенный материал служит введением в эти области через исследование базовых методов.
В первых четырех частях, включенных в этот том, освещен наиболее широко используемый набор алгоритмов и структур данных — первый уровень абстракции для коллекций объектов с ключами, который может поддерживать широкое множество важных основополагающих алгоритмов. Рассматриваемые алгоритмы — результаты десятков лет исследований и разработки, и они продолжают играть важную роль во все более широком применении компьютеров.
В частях с V по VIII, которые вынесены в отдельные тома, описаны дополнительные применения описанных алгоритмов — второй уровень абстракций, характерный для ряда важных областей применения. Кроме того, в этих частях более глубоко рассмотрены технологии разработки и анализа алгоритмов. Многие из затрагиваемых проблем являются предметом предстоящих исследований.
Изучение алгоритмов представляет интерес, поскольку это новая отрасль (почти все изученные в этом курсе алгоритмы не старше 50 лет, а некоторые были открыты лишь недавно) с богатыми традициями (некоторые алгоритмы известны уже в течение тысяч лет). Постоянно делаются новые открытия, но лишь немногие алгоритмы исследованы полностью. В этом курсе мы рассмотрим замысловатые, сложные и трудные алгоритмы, наряду с изящными, простыми и легко реализуемыми алгоритмами. Наша задача — понять первые и оценить вторые в контексте множества различных потенциально возможных приложений. В процессе этого нам предстоит исследовать ряд полезных инструментов и выработать стиль алгоритмического мышления, который пригодится при решении предстоящих вычислительных задач.
В общем случае при создании компьютерной программы мы реализуем метод, который ранее был разработан для решения какой-либо задачи. Часто этот метод не зависит от конкретного используемого компьютера — он примерно одинаково пригоден для многих компьютеров и многих компьютерных языков. именно метод, а не саму программу нужно исследовать для выяснения способа решения задачи. Для метода решения задачи, пригодного для реализации в виде компьютерной программы, в компьютерных науках используется термин алгоритм. Алгоритмы составляют основу компьютерных наук: это основные объекты изучения во многих, если не в большинстве областей этих наук.
В основном представляющие интерес алгоритмы тесно связаны с методами организации данных, участвующих в вычислениях. Созданные таким образом объекты называются структурами данных, и они также являются центральными объектами изучения в компьютерных науках. То есть алгоритмы и структуры данных идут рука об руку. В этом курсе мы покажем, что структуры данных существуют в качестве побочных или конечных продуктов алгоритмов и, следовательно, их нужно изучить, чтобы понять алгоритмы. Простые алгоритмы могут порождать сложные структуры данных и наоборот, сложные алгоритмы могут использовать простые структуры данных. В этом курсе будут изучены свойства множества структур данных, так что курс вполне мог бы называться "Алгоритмы и структуры данных на C++".
Когда компьютер используется для решения той или иной задачи, как правило, имеется целый ряд возможных различных подходов. При решении простых задач выбор того или иного подхода вряд ли имеет особое значение, если только выбранный подход приводит к правильному решению. Однако при решении очень сложных задач (или в приложениях, в которых приходится решать очень большое количество простых задач) мы сталкиваемся с необходимостью разработки методов, в которых время или память используются с максимальной эффективностью.
Основная побудительная причина изучения алгоритмов состоит в том, что это позволяет обеспечить огромную экономию ресурсов, вплоть до получения решений задач, которые в противном случае были бы невозможны. В приложениях, в которых обрабатываются миллионы объектов, часто хорошо разработанный алгоритм позволяет ускорить работу программы в миллионы раз. Подобный пример приводится в разделе 1.2 и в множестве других разделов курса. Для сравнения: затраты дополнительных денег или времени для приобретения и установки нового компьютера потенциально позволяет ускорить работу программы всего в 10—100 раз. Тщательная разработка алгоритма — исключительно эффективная часть процесса решения сложной задачи в любой области применения.
При разработке очень большой или сложной компьютерной программы значительные усилия должны затрачиваться на уяснение и формулировку задачи, которая должна быть решена, осознание ее сложности и разбиение ее на менее сложные подзадачи, решения которых можно легко реализовать. Зачастую реализация многих алгоритмов, требуемых после разбиения, тривиальна. Однако в большинстве случаев существует несколько алгоритмов, выбор которых критичен, поскольку для их выполнения требуется большая часть системных ресурсов. Именно этим типам алгоритмов уделяется основное внимание в данном курсе. Мы изучим ряд основополагающих алгоритмов, которые полезны при решении сложных задач во многих областях применения.
Совместное использование программ в компьютерных системах становится все более распространенным, поэтому, хотя можно ожидать, что использовать придется многие из рассмотренных в курсе алгоритмов, одновременно можно надеяться, что реализовывать придется лишь немногие из них. Например, библиотека стандартных шаблонов (Standard Template Library) C++ содержит реализации множества базовых алгоритмов. Однако реализация простых версий основных алгоритмов позволяет лучше их понять и, следовательно, эффективнее использовать и настраивать более совершенные библиотечные версии. И что еще важнее, очень часто возникает необходимость самостоятельной реализации основных алгоритмов. Основная причина состоит в том, что мы очень часто сталкиваемся с совершено новыми вычислительными средами (аппаратными и программными), новые свойства которых не могут наилучшим образом использоваться старыми реализациями. То есть чтобы наши решения были более переносимыми и применимыми, часто приходится реализовывать базовые алгоритмы, приспособленные к конкретной задаче, а не основывающиеся на системных подпрограммах. Другая часто возникающая причина самостоятельной реализации базовых алгоритмов заключается в том, что несмотря на усовершенствования, встроенные в C++, механизмы, используемые для совместного использования программ, не всегда достаточно мощны, чтобы библиотечные программы можно было легко приспособить к эффективному выполнению конкретных задач.
Компьютерные программы часто чрезмерно оптимизированы. Обеспечение наиболее эффективной реализации конкретного алгоритма может не стоить затраченных усилий, если только алгоритм не должен использоваться для решения очень сложной задачи или же многократно. В противном случае вполне сгодится качественная, сравнительно простая реализация: достаточно быть уверенным в ее работоспособности и в том, что, скорее всего, в худшем случае она будет работать в 5—10 раз медленнее наиболее эффективной версии, что может означать увеличение времени выполнения на несколько дополнительных секунд. И напротив, правильный выбор алгоритма может ускорить работу в 100—1000 и более раз, что во время выполнения может сэкономить минуты, часы и даже более того. В этом курсе основное внимание уделяется простейшим приемлемым реализациям наилучших алгоритмов.
Выбор наилучшего алгоритма выполнения конкретной задачи может оказаться сложным процессом, возможно, требующим нетривиального математического анализа. Направление компьютерных наук, занимающееся изучением подобных вопросов, называется анализом алгоритмов. Анализ многих изучаемых алгоритмов показывает, что они имеют прекрасную производительность; о хорошей работе других известно просто из опыта их применения. Наша основная цель — изучение приемлемых алгоритмов выполнения важных задач, хотя значительное внимание будет уделено также сравнительной производительности различных методов. Не следует использовать алгоритм, не имея представления о ресурсах, которые могут потребоваться для его выполнения, поэтому мы стараемся узнать, как могут выполняться используемые алгоритмы.
Предположим, что имеется последовательность пар целых чисел, в которой каждое целое число представляет объект некоторого типа, а пара .
(рис 1.1) Пример связности
При заданной последовательности пар целых чисел, представляющих связи между объектами (слева) алгоритм определения связности должен выводить только те пары, которые определяют новые связи (в центре). Например, пара 2-9 не должна выводиться, поскольку связь 2-3-4-9 определяется ранее указанными связями (подтверждение этого показано справа).
Задача состоит в разработке программы, которая может запомнить достаточный объем информации о просмотренных парах, чтобы решить, связана ли новая пара объектов. Неформально задачу разработки такого метода мы назовем задачей связности. Эта задача возникает в ряде важных приложений. Для подтверждения всеобщего характера этой задачи мы кратко рассмотрим три примера.
Например, целые числа могли бы представлять компьютеры в большой сети, а пары могли бы представлять соединения в сети. Тогда такая программа могла бы использоваться для определения того, нужно ли устанавливать новое прямое соединение между p и q, чтобы они могли обмениваться информацией, или же для установки коммуникационного пути можно использовать существующие соединения. В подобных приложениях может потребоваться обработка миллионов точек и миллиардов или более соединений. Как мы увидим, решить задачу для такого приложения было бы невозможно без эффективного алгоритма. Аналогично, целые числа могли бы представлять контакты в электрической сети, а пары могли бы представлять связывающие их проводники. В этом случае программу можно было бы использовать для определения способа соединения всех точек без каких-либо избыточных соединений, если это возможно. Не существует никакой гарантии, что связей в списке окажется достаточно для соединения всех точек — действительно, вскоре мы увидим, что определение факта, так ли это, может быть основным применением нашей программы.
На рис 1.2 показаны эти два типа применений на более сложном примере. Изучение этого рисунка дает представление о сложности задачи связности: как можно быстро выяснить, являются ли любые две заданные точки в такой сети связанными?
Еще один пример встречается в некоторых средах программирования, в которых два имени переменных можно объявлять эквивалентными. Задача заключается в возможности определения, являются ли два заданных имени эквивалентными, после считывания последовательности таких объявлений. Это применение — одно из первых, обусловивших разработку нескольких алгоритмов, которые мы рассмотрим ниже. Как будет показано далее, оно устанавливает непосредственную связь между рассматриваемой задачей и простой абстракцией, предоставляющей способ сделать алгоритмы полезными для широкого множества приложений.
Такие приложения, как задача установления эквивалентности имен переменных, описанная в предыдущем абзаце, требует, чтобы с каждым отдельным именем переменной было сопоставлено целое число. Это сопоставление подразумевается также и в описанных приложениях сетевого соединения и соединения в электрической цепи. В лекциях 10—16 мы рассмотрим ряд алгоритмов, которые могут эффективно обеспечить такое сопоставление. Таким образом, в этой лекции без ущерба для общности можно предположить, что имеется N объектов с целочисленными именами от 0 до N — 1 .
(рис 1.2) Большой пример задачи связности
Объекты, задействованные в задаче связности, могут представлять собой точки соединений, а пары могут быть соединениями между ними — как показано в этом идеализированном примере, который мог бы представлять провода, соединяющие здания в городе или компоненты в компьютерной микросхеме. Это графическое представление позволяет человеку выявить несвязанные узлы, но алгоритм должен работать только с переданными ему парами целых чисел. Связаны ли два узла, помеченные большими черными точками?
Нам требуется программа, которая выполняет конкретную, вполне определенную задачу. Существует множество других связанных с этой задач, решение которых также может потребоваться. Один из первых вопросов, который необходимо решить при разработке алгоритма — это убедиться, что задача определена приемлемым образом. Чем выше требования к алгоритму, тем больше времени и объема памяти может потребоваться для выполнения задачи. Это соотношение невозможно в точности определить заранее, и часто определение задачи приходится изменять, когда выясняется, что ее трудно решить, либо решение требует слишком больших затрат, или же когда, при удачном стечении обстоятельств, выясняется, что алгоритм может предоставить более полезную информацию, чем требовалось от него в исходном определении.
Например, приведенное определение задачи связности требует только, чтобы программа как-либо узнавала, является ли данная пара и подробно — в части VII.
Упомянутые в предыдущем абзаце определения требуют больше информации, чем первоначальное; может также требоваться и меньше информации. Например, может потребоваться просто ответить на вопрос: "Достаточно ли ). Иначе говоря, алгоритм решения задачи связности никогда не выводит более N — 1 пар, поскольку как только он выведет N — 1 пару, любая встретившаяся после этого пара будет уже связанной. Соответственно, можно создать программу, отвечающую "да-нет" на только что поставленный вопрос, изменив программу, которая решает задачу связности, на такую, которая увеличивает значение счетчика, а не записывает ранее не связанную пару, отвечая "да", когда значение счетчика достигает N— 1 , и "нет", если это не происходит. Этот вопрос — всего лишь один из множества вопросов, которые могут возникнуть относительно связности. Входной набор пар называется графом (graph), а выходной набор пар — остовным деревом (spanning tree) этого графа, которое связывает все объекты. Свойства графов, остовных деревьев и всевозможные связанные с ними алгоритмы будут рассматриваться в части VII.
Имеет смысл попытаться определить основные операции, которые будут выполняться для решения задачи связности, чтобы любой алгоритм, разрабатываемый для ее решения, был полезен и для ряда аналогичных задач. В частности, при получении каждой новой пары вначале необходимо определить, представляет ли она новое соединение, а затем внедрить информацию об обнаруженном соединении в общую картину о связности объектов для проверки соединений, которые будут наблюдаться в будущем. Мы инкапсулируем эти две задачи в виде абстрактных операций, считая целочисленные вводимые значения представляющими элементы в абстрактных наборах, а затем разработаем алгоритмы и структуры данных, которые могут:
Организация алгоритмов посредством этих абстрактных операций, похоже, не отсекает никакие варианты решения задачи связности, и эти операции могут оказаться полезными при решении других задач. Разработка уровней абстракции с еще большими возможностями — важный процесс в компьютерных науках в целом и в разработке алгоритмов в частности, и в этом курсе мы будем обращаться к нему многократно. В данной лекции для разработки программ решения задачи связности мы используем неформальное абстрактное представление; а в эти абстракции будут выражены в коде C++.
Задача связности легко решается с помощью абстрактных операций поиск (find) и объединение (union). После считывания новой пары p-q мы выполняем операцию поиск для каждого члена пары. Если оба члена пары находятся в одном множестве, мы переходим к следующей паре; если нет, то выполняем операцию объединение и записываем пару. Наборы представляют собой связанные компоненты: подмножества объектов, характеризующиеся тем, что любые два объекта в данном компоненте связаны. Этот подход сводит разработку алгоритмического решения задачи связности к задачам определения структуры данных, которая представляет множества, и разработке алгоритмов объединение и поиск, которые эффективно используют эту структуру данных.
Существует много возможных способов представления и обработки абстрактных множеств. В этой лекции основное внимание уделяется поиску представления, которое может эффективно поддерживать операции объединение и поиск, необходимые для решения задачи связности.
Упражнения
1.1. Приведите выходные данные, которые должен выдавать алгоритм связности для входных пар 0-2, 1-4, 2-5, 3-6, 0-4, 6-0 и 1-3.
1.2. Перечислите все различные способы связывания двух различных объектов, показанных в примере на рис 1.1.
1.3. Опишите простой метод подсчета количества наборов, остающихся после применения операций объединение и поиск для решения задачи связности, как описано в тексте.
Первый шаг в процессе разработки эффективного алгоритма решения данной задачи — реализация простого алгоритма ее решения. Если нужно решить несколько вариантов конкретной задачи, которые оказываются простыми, это может быть выполнено посредством простой реализации. Если требуется более сложный алгоритм, то простая реализация предоставляет возможность проверить правильность работы алгоритма для простых случаев и может служить базовым замером для оценки характеристик производительности. Эффективность важна всегда, но при разработке первой программы решения задачи в первую очередь необходимо убедиться в том, что программа обеспечивает правильное решение.
Первое, что приходит в голову — организовать способ сохранения всех вводимых пар, а затем создать функцию для их просмотра, чтобы попытаться выяснить, связана ли очередная пара объектов. Однако мы используем другой подход. Во-первых, количество пар может быть настолько велико, что не позволит хранить их все в памяти в используемом на практике приложении. Во-вторых, что гораздо важнее, не существует никакого простого метода, который сам по себе позволяет определить, связаны ли два объекта в наборе всех соединений, даже если бы удалось их все сохранить! Базовый метод, использующий этот подход, рассматривается в , а методы, которые рассматриваются в этой лекции, проще, поскольку они решают менее сложную задачу, и эффективнее, поскольку не требуют хранения всех пар. Для хранения информации, необходимой для реализации операций объединение и поиск, все эти методы используют массив целых чисел, каждое из которых соответствует отдельному объекту.
Массивы — это элементарные структуры данных, которые подробно будут рассмотрены в . Здесь же они используются в простейшей форме: мы объявляем, что собираемся использовать, скажем, 1000 целых чисел, записывая a[1000], а затем обращаемся к i-ому целому числу в массиве с помощью записи a[i] для $$${0}\leq{i}<1000$$$.
Программа 1.1 — реализация простого алгоритма, называемого алгоритмом быстрого поиска, который решает задачу связности. В основе этого алгоритма лежит использование массива целых чисел, обладающих тем свойством, что p и q связаны тогда и только тогда, когда p-й и q-й элементы массива равны. Вначале i-й элемент массива инициализируется значением i, $$${0}\leq{i}<N$$$. Чтобы реализовать операцию объединение для p и q, мы просматриваем массив, заменяя все элементы с тем же именем, что и p, на элементы с тем же именем, что и q. Этот выбор произволен — можно было бы все элементы с тем же именем, что и q, заменять на элементы с тем же именем, что и p.
Изменения в массиве при выполнении операций объединение в примере из рис 1.1 показаны на рис 1.3. Для реализации операции поиск достаточно проверить указанные записи массива на предмет равенства — отсюда и название быстрый поиск (quick find). Однако операция объединение требует просмотра всего массива для каждой вводимой пары.
Лемма 1.1. Алгоритм быстрого поиска выполняет не менее M x N инструкций для решения задачи связности при наличии N объектов, для которых требуется выполнение M операций объединения.
Для каждой из M операций объединение цикл for выполняется N раз. Для каждой итерации требуется выполнение, по меньшей мере, одной инструкции (если только проверять, завершился ли цикл). $$$\blacksquare$$$
Программа 1.1. Решение задачи связности методом быстрого поиска
Эта программа считывает из стандартного ввода последовательность пар неотрицательных целых чисел, меньших чем N (интерпретируя пару p
).
#include <iostream.h>
static const int N = 10000;
int main() {
int i, p, q, id[N];
for ( i = 0; i < N; i++) id[i] = i;
while (cin >> p >> q) {
int t = id[p];
if (t == id[q]) continue;
for ( i = 0; i < N; i++)
if (id[i] == t) id[i] = id[q];
cout << " " << p << " " << q << endl;
}
}
(рис 1.3) Пример быстрого поиска (медленное объединение)
Здесь изображено содержимое массива id после обработки каждой пары, приведенной слева, алгоритмом быстрого поиска (программа 1.1). Затененные записи — те, которые изменяются для выполнения операции объединение. При обработке пары p
q во все записи со значением id[p] заносится значение из id[q].
Современные компьютеры могут выполнять десятки или сотни миллионов инструкций в секунду, поэтому для малых значений .
Графическое представление массива, показанного на рис 1.3, приведено на рис 1.4. Можно считать, что некоторые объекты представляют множество, к которому они принадлежат, а остальные указывают на представителя их множества. Причина обращения к такому графическому представлению массива вскоре станет понятна. Обратите внимание, что связи между объектами в этом представлении не обязательно соответствуют связям во вводимых парах — они представляют собой информацию, запоминаемую алгоритмом, которая позволяет определить, соединены ли пары, которые будут вводиться в будущем.
А теперь мы рассмотрим дополнительный к предыдущему метод, который называется алгоритмом быстрого объединения. В его основе лежит та же структура данных — индексированный по именам объектов массив — но в нем используется иная интерпретация значений, что приводит к более сложной абстрактной структуре. Каждый объект указывает на другой объект в этом же множестве, образуя структуру, не содержащую циклов. Чтобы определить, находятся ли два объекта в одном множестве, мы следуем указателям для каждого из них до тех пор, пока не будет достигнут объект, который указывает на самого себя. Объекты находятся в одном множестве тогда и только тогда, когда этот процесс приводит от них к одному и тому же объекту. Если они не находятся в одном множестве, процесс завершится на разных объектах (которые указывают на себя). Тогда для образования объединения достаточно связать один объект с другим — отсюда и название быстрое объединение (quick union).
На рис 1.5 показано графическое представление, которое соответствует рис 1.4 при выполнении алгоритма быстрого объединения для массива, изображенного на рис 1.1, а на рис 1.6 показаны соответствующие изменения в массиве id. Графическое представление структуры данных позволяет сравнительно легко понять действие алгоритма — пары объектов, которые соединены во входных данных, связаны один с другим и в структуре данных. Обратите внимание: здесь, как и ранее, связи в структуре данных не обязательно совпадают со связями, заданными вводимыми парами; вместо этого они создаются алгоритмом так, чтобы обеспечить эффективную реализацию операций объединение и поиск.
(рис 1.4) Представление быстрого поиска в виде дерева
На этом рисунке показано графическое представление примера, приведенного на рис 1.3. Связи на этом рисунке не обязательно представляют связи во входных данных. Например, структура, показанная на нижнем рисунке, содержит связь 1-7, которая отсутствует во входных данных, но образуется в результате цепочки связей 7-3-4-9-5-6-1.
(рис 1.5) Представление быстрого объединения в виде дерева
Этот рисунок — графическое представление примера, показанного на рис 1.3. Мы проводим линию от объекта i к объекту id[i].
(рис 1.6) Пример быстрого объединения (не очень быстрый поиск)
Здесь изображено содержимое массива id после обработки каждой из показанных слева пар алгоритмом быстрого поиска (программа 1.1). Затененные элементы — те, которые изменяются для выполнения операции объединения (по одной на каждую операцию). При обработке пары p
q мы переходим по указателям из p до записи i, у которой id[i] == i; потом переходим по указателям из q до записи j, у которой id[j] == j; затем, если i и j различны, устанавливаем id[i] = id[j]. При выполнении операции поиска для пары 5-8 (последняя строка) i принимает значения 5 6 9 0 1, а j — значения 8 0 1.
Связанные компоненты, изображенные на . Деревья, изображенные на рис 1.5, удобны для выполнения операций объединение и поиск, поскольку их можно быстро построить, и они характеризуются тем, что два объекта связаны в дереве тогда и только тогда, когда объекты связаны во входных данных. Перемещаясь вверх по дереву, можно легко отыскать корень дерева, содержащего каждый объект, и, следовательно, можно выяснить, связаны они или нет. Каждое дерево содержит только один объект, указывающий сам на себя, называемый корнем (root) дерева. Указатель на себя на диаграммах не показан. Начав с любого объекта дерева и перемещаясь к объекту, на который он указывает, затем следующему указанному объекту и т.д., мы всегда со временем попадаем к корню. Справедливость этого свойства можно доказать методом индукции: это справедливо после инициализации массива, когда каждый объект указывает на себя, и если это справедливо до выполнения любой операции объединение, это безусловно справедливо и после нее.
Диаграммы для алгоритма быстрого поиска, показанные на рис 1.4, характеризуются теми же свойствами, которые описаны в предыдущем абзаце. Различие состоит в том, что в деревьях быстрого поиска мы достигаем корня из всех узлов, переходя лишь по одной ссылке, а в дереве быстрого объединения для достижения корня может потребоваться переход по нескольким ссылкам.
Программа 1.2 — реализация операций объединение и поиск, образующих алгоритм быстрого объединения для решения задачи связности. Похоже, что алгоритм быстрого объединения работает быстрее алгоритма быстрого поиска, поскольку для каждой вводимой пары ему не нужно просматривать весь массив; но насколько быстрее? В данном случае ответить на этот вопрос труднее, чем в случае быстрого поиска, поскольку время выполнения в большей степени зависит от характера входных данных. Выполнив экспериментальные исследования или математический анализ (см. ), можно показать, что программа 1.2 значительно эффективнее программы 1.1, и ее можно использовать для решения очень сложных реальных задач. Одно из таких экспериментальных исследований будет рассмотрено в конце этого раздела. А пока быстрое объединение можно считать усовершенствованием, поскольку оно устраняет основной недостаток алгоритма быстрого поиска (тот факт, что для выполнения M операций объединение между N объектами программе требуется выполнение, по меньшей мере, N M инструкций).
Программа 1.2. Решение задачи связности методом быстрого объединения
Если тело цикла while в программе 1.1 заменить этим кодом, мы получим программу, которая соответствует тем же спецификациям, что и программа 1.1, но выполняет меньше вычислений для операции объединение за счет выполнения большего количества вычислений для операции поиск. Циклы for и последующий оператор if в этом коде определяют необходимые и достаточные условия связности p и q в массиве id. Оператор присваивания id[i] = j реализует операцию объединение.
for (i = p; i != id[i]; i = id[i]) ;
for (j = q; j != id[j]; j = id[j]) ;
if (i == j) continue;
id[i] = j;
cout << " " << p << " " << q << endl;
Это различие между быстрым объединением и быстрым поиском действительно повышает производительность, однако у быстрого объединения есть недостаток: нельзя гарантировать, что оно будет выполняться существенно быстрее быстрого поиска в каждом случае, поскольку характер входных данных может замедлить операцию поиск.
Лемма 1.2. Для M пар из N объектов, когда M > N , решение задачи связности алгоритмом быстрого объединения может потребовать выполнения более чем MN/2 инструкций.
Предположим, что пары вводятся в следующем порядке: 1-2, 2-3, 3-4 и т.д. После ввода N — 1 таких пар мы получим N объектов, принадлежащих к одному множеству, а сформированное алгоритмом быстрого объединения дерево представляет собой прямую линию, где объект N указывает на объект N — 1 , тот, в свою очередь, — на объект N — 2, тот — на N — 3 и т.д. Чтобы выполнить операцию поиск для объекта N, программа должна перейти по N — 1 указателям. Таким образом, среднее количество указателей, по которым выполняются переходы для первых N пар, равно
(0 + 1 +...+ (N - 1))/N = (N-1)/2
Теперь предположим, что все остальные пары связывают объект N с каким-либо другим объектом. Чтобы выполнить операцию поиск для каждой из этих пар, требуется перейти, по меньшей мере, по (N - 1) указателям. Общий итог для M операций поиск при такой последовательности вводимых пар определенно больше M N/2. $$$\blacksquare$$$
К счастью, можно легко модифицировать алгоритм, чтобы худшие случаи, подобные этому, гарантированно не имели места. При выполнении операции объединение можно не произвольным образом соединять второе дерево с первым, а отслеживать количество узлов в каждом дереве и всегда соединять меньшее дерево с большим. Это изменение требует несколько более объемного кода и наличия еще одного массива для хранения счетчиков узлов, как показано в программе 1.3, но оно ведет к существенному повышению эффективности. Мы будем называть этот алгоритм алгоритмом взвешенного быстрого объединения (weighted quick-union algorithm).
Программа 1.3. Взвешенная версия быстрого объединения
Эта программа — модификация алгоритма быстрого объединения (см. программу 1.2), которая в служебных целях для каждого объекта, у которого id[i] == i, поддерживает дополнительный массив sz, где хранятся количества узлов в соответствующих деревьях, чтобы операция объединение могла связывать меньшее из двух указанных деревьев с большим, тем самым предотвращая разрастание длинных путей в деревьях.
#include <iostream.h>
static const int N = 10000;
int main() {
int i, j, p, q, id[N], sz[N];
for (i = 0; i < N; i++) {
id[i] = i; sz[i] = 1;
}
while ( cin >> p >> q) {
for (i = p; i != id[i]; i = id[i]) ;
for (j = q; j != id[j]; j = id[j]) ; if (i == j) continue;
if (sz[i] < sz[j]) {
id[i] = j; sz[j] += sz[i];
} else {
id[j] = i; sz[i] += sz[j];
}
cout << " " << p << " " << q << endl;
}
}
На рис 1.7 показан лес деревьев, созданных алгоритмом взвешенного поиска для примера входных данных с рис 1.1. Даже в этом небольшом примере пути в деревьях существенно короче, чем в случае невзвешенной версии, приведенной на рис 1.5.
На рис 1.8 демонстрируется, что происходит в худшем случае, когда размеры наборов, которые должны быть объединены в операции объединение, всегда равны (и являются степенью 2). Эти структуры деревьев выглядят сложными, но у них есть простое свойство: максимальное количество указателей, по которым необходимо перейти, чтобы добраться до корня в дереве, состоящем из
2n
узлов, равно п. При слиянии двух деревьев, состоящих из
2n
узлов, получается дерево, состоящее из
2n+1
узлов, а максимальное расстояние до корня увеличивается до п + 1. Это наблюдение можно обобщить для доказательства того, что взвешенный алгоритм значительно эффективнее невзвешенного.
Лемма 1.3. Для определения того, связаны ли два из N объектов, алгоритм взвешенного быстрого объединения переходит максимум по log N указателям.
Можно доказать, что для операции объединение сохраняется свойство, что количество указателей, проходимых из любого узла до корня в множестве к объектов, не превышает log к. При объединении набора, состоящего из i узлов, с набором, состоящим из j узлов, при $$${i}\leq{j}$$$ количество указателей, которые должны отслеживаться в меньшем наборе, увеличивается на 1, но теперь узлы находятся в наборе размера i + j, и свойство остается справедливым, поскольку $$$1+\log{i}={\log(i + i)}\leq{\log (i + j )}$$$. $$$\blacksquare$$$
(рис 1.7) Представление взвешенного быстрого объединения в виде дерева
На этой последовательности рисунков демонстрируется результат изменения алгоритма быстрого объединения, когда корень меньшего из двух деревьев связывается с корнем большего. Расстояние от каждого узла до корня его дерева невелико, поэтому операция поиска выполняется эффективно.
(рис 1.8) Взвешенное быстрое объединение (худший случай)
Наихудшая ситуация для алгоритма взвешенного быстрого объединения — когда каждая операция объединения связывает деревья одинакового размера. Если количество объектов меньше 2n, расстояние от любого узла до корня его дерева меньше п.
Практическая польза леммы 1.3 заключается в том, что количество инструкций, которые алгоритм взвешенного быстрого объединения использует для обработки M ребер между N объектами, не превышает Mlog N, умноженного на некоторую константу (см. упражнение 1.9). Этот вывод резко отличается от вывода, что алгоритм быстрого поиска всегда (а алгоритм быстрого объединения иногда) использует не менее M N/ 2 инструкций. Таким образом, при использовании взвешенного быстрого объединения можно гарантировать решение очень сложных встречающихся на практике задач за приемлемое время (см. упражнение 1.11). Ценой добавления нескольких дополнительных строк кода мы получаем программу, которая при решении очень сложных задач, которые могут встретиться на практике, работает буквально в миллионы раз быстрее, чем более простые алгоритмы.
Из приведенных диаграмм видно, что лишь сравнительно небольшое количество узлов располагаются далеко от корня; действительно, экспериментальное изучение очень сложных задач показывает, что, как правило, для решения практических задач посредством использования алгоритма взвешенного быстрого объединения, реализованного в программе 1.3, требуется линейное время. То есть затраты времени на выполнение алгоритма равны затратам времени на считывание входных данных с постоянным коэффициентом. Вряд ли можно было бы рассчитывать найти более эффективный алгоритм.
Тут же возникает вопрос: можно ли найти алгоритм, обеспечивающий гарантированную линейную производительность. Этот вопрос — исключительно трудный, который уже много лет не дает покоя исследователям (см. ). Существует множество способов дальнейшего совершенствования алгоритма взвешенного быстрого объединения. В идеале было бы желательно, чтобы каждый узел указывал непосредственно на корень своего дерева, но не хотелось бы расплачиваться за это изменением большого количества указателей, как в алгоритме быстрого объединения. К идеалу можно приблизиться, просто делая все проверяемые узлы указывающими на корень. На первый взгляд этот шаг кажется весьма радикальным, но его легко реализовать, а в структуре этих деревьев нет ничего неприкосновенного, и если их можно изменить, чтобы сделать алгоритм более эффективным, то так и следует сделать. Этот метод, названный сжатием пути (path compression), можно легко реализовать, добавляя еще один проход по каждому пути во время выполнения операции объединение и занося в элемент ). Анализ, устанавливающий этот факт, исключительно сложен, но сам метод прост и эффективен. Результат сжатия пути для большого примера показан на рис 1.11.
Существует множество других способов реализации сжатия пути. Например, программа 1.4 представляет собой реализацию, которая сжимает пути, сдвигая каждую ссылку на следующий узел в пути вверх по дереву (см. в контексте рассмотрения основных подходов к анализам алгоритмов.
(рис 1.9) Сжатие пути
Пути в деревьях можно сделать еще короче, просто занося во все просматриваемые объекты указатели на корень нового дерева во время операции объединения, как показано в этих двух примерах. В примере на верхнем рисунке показан результат, соответствующий рис 1.7. В случае коротких путей сжатие пути не оказывает никакого влияния, но после обработки пары 1 6 узлы 1, 5 и 6 указывают на узел 3, в результате чего дерево становится более плоским, чем на рис 1.7. В примере на нижнем рисунке показан результат, соответствующий рис 1.8. В деревьях могут появляться пути, которые содержат больше одной-двух связей, но при каждом прохождении они становятся более плоскими. В данном случае после обработки пары 6 8 дерево становится более плоским, а узлы 4, 6 и 8 указывают на узел 0.
(рис 1.10) Сжатие пути делением пополам
Можно уменьшить длину путей вверх по дереву почти вдвое, беря сразу по две ссылки и занося в нижнюю из них указатель на тот же узел, что и в верхней, как показано в этом примере. Конечный результат выполнения такой операции для каждого проходимого пути приближается к результату, получаемому в результате полного сжатия пути.
(рис 1.11) Большой пример влияния сжатия пути
Здесь отображен результат обработки случайных пар из 100 объектов алгоритмом взвешенного быстрого объединения со сжатием пути. Все узлы этого дерева, кроме двух, находятся на расстоянии одного-двух шагов от корня.
Программа 1.4. Сжатие пути делением пополам
Если циклы for в программе 1.3 заменить этим кодом, длина любого проходимого пути будет уменьшаться в два раза. Конечный результат этого изменения — превращение деревьев в почти совершенно плоские после выполнения длинной последовательности операций.
for (i = p; i != id[i]; i = id[i])
id[i] = id[id[i]];
for (j = q; j != id[j]; j = id[j])
id[j] = id[id[j]];
Конечный результат применения рассмотренных алгоритмов решения задачи связности приближается к наилучшему, на который можно было бы рассчитывать в любом практическом случае. Мы имеем легко реализуемые алгоритмы, время выполнения которых гарантированно пропорционально затратам времени на ввод данных с постоянным коэффициентом. Более того, алгоритмы являются оперативными: они рассматривают каждое ребро только один раз и используют объем памяти, который пропорционален количеству объектов; поэтому какие-либо ограничения на количество обрабатываемых ими ребер отсутствуют. Результаты экспериментального исследования, приведенные в табл. 1.1 .)
| N | M | F | U | W | P | H |
|---|---|---|---|---|---|---|
| 1000 | 6206 | 14 | 25 | 6 | 5 | 3 |
| 2500 | 20236 | 82 | 210 | 13 | 15 | 12 |
| 5000 | 41913 | 304 | 1172 | 46 | 26 | 25 |
| 10000 | 83857 | 1216 | 4577 | 91 | 73 | 50 |
| 25000 | 309802 | 219 | 208 | 216 | ||
| 50000 | 708701 | 469 | 387 | 497 | ||
| 100000 | 1545119 | 1071 | 1106 | 1096 |
Обозначения:
| F | быстрый поиск (программа 1.1) |
| U | быстрое объединение (программа 1.2) |
| W | взвешенное быстрое объединение (программа 1.3) |
| P | взвешенное быстрое объединение со сжатием пути (упражнение 1.16) |
| H | взвешенное быстрое объединение с делением пополам (программа 1.4) |
Эти сравнительные значения времени, затрачиваемого на решение случайных задач связности с использованием алгоритмов объединения-поиска, демонстрируют эффективность взвешенной версии алгоритма быстрого объединения. Дополнительный выигрыш благодаря использованию сжатия пути менее важен. Здесь M — количество случайных соединений, генерируемых до тех пор, пока все N объектов не оказываются связанными. Этот процесс требует значительно больше операций поиск, чем операций объединение, поэтому быстрое объединение выполняется существенно медленнее быстрого поиска. Ни быстрый поиск, ни быстрое объединение не годятся для очень больших N. Время выполнения при использовании взвешенных методов явно пропорционально значению N, поскольку оно уменьшается вдвое при уменьшении N вдвое.
Упражнения
1.4. Приведите содержимое массива id после выполнения каждой операции объединение при использовании алгоритма быстрого поиска (программа 1.1) для решения задачи связности для последовательности 0-2, 1-4, 2-5, 3-6, 0-4, 6-0 и 1-3. Укажите также количество обращений программы к массиву id для каждой вводимой пары.
1.5. Выполните упражнение 1.4, но для алгоритма быстрого объединения (программа 1.2).
1.6. Приведите содержимое массива и рис 1.8.
1.7. Выполните упражнение 1.4, но для алгоритма взвешенного быстрого объединения (программа 1.3).
1.8. Выполните упражнение 1.4, но для алгоритма взвешенного быстрого объединения со сжатием пути делением пополам (программа 1.4).
1.9. Определите верхнюю границу количества машинных инструкций, требующихся для обработки M соединений N объектов при использовании программы 1.3. Например, можно предположить, что для выполнения оператора присваивания C+ + всегда требуется выполнение менее c инструкций, где c — некоторая фиксированная константа.
1.10. Определите минимальное время (в днях), которое потребовалось бы для выполнения быстрого поиска (программа 1.1) для решения задачи с 109 объектов и 106 вводимых пар на компьютере, который может выполнять 109 инструкций в секунду. Считайте, что при каждой итерации внутреннего цикла for должно выполняться не менее 10 инструкций.
1.11. Определите максимальное время (в секундах), которое потребовалось бы для выполнения взвешенного быстрого объединения (программа 1.3) для решения задачи с 1099 объектов и 106 вводимых пар на компьютере, который может выполнять 109 инструкций в секунду. Считайте, что при каждой итерации внешнего цикла while должно выполняться не более 100 инструкций.
1.12. Вычислите среднее расстояние от узла до корня в худшем случае в дереве из 2n узлов, построенном алгоритмом взвешенного быстрого объединения.
1.13. Нарисуйте диаграмму, подобную рис 1.10, но начав с восьми узлов, а не девяти.
1.14. Приведите последовательность вводимых пар, для которой алгоритм взвешенного быстрого объединения (программа 1.3) создает путь длиной 4.
1.15. Приведите последовательность вводимых пар, для которой алгоритм взвешенного быстрого объединения с сжатием пути делением пополам (программа 1.4) создает путь длиной 4.
1.16. Покажите, как необходимо изменить программу 1.3, чтобы реализовать полное сжатие пути, при котором после каждой операции объединение все обработанные узлы указывают на корень нового дерева.
1.17. Выполните упражнение 1.4, но используйте алгоритм взвешенного быстрого объединения с полным сжатием пути (упражнение 1.16).
1.18. Приведите последовательность вводимых пар, для которой алгоритм взвешенного быстрого объединения с полным сжатием пути (см. упражнение 1.16) создает путь длиной 4.
1.19. Приведите пример, показывающий, что изменения быстрого объединения (программа 1.2) для реализации полного сжатия пути (см. упражнение 1.16) не достаточно, чтобы гарантировать отсутствие длинных путей в деревьях.
1.20. Измените программу 1.3, чтобы в ней для принятия решения, нужно ли устанавливать id[i] = j или id[j] = i, вместо веса использовалась высота деревьев (самый длинный путь от любого узла до корня). Экспериментально сравните этот вариант с программой 1.3.
1.21. Покажите, что лемма 1.3 справедлива для алгоритма, описанного в упражнении 1.20.
1.22. Измените программу 1.4, чтобы она генерировала случайные пары целых чисел в диапазоне от 0 до N— 1 вместо того, чтобы считывать их из стандартного ввода, и выполняла цикл до тех пор, пока не будет выполнено N — 1 операций объединение. Выполните программу для значений
N = 103, 104, 105 и 106
и выведите общее количество ребер, генерируемых для каждого значения N.
1.23. Измените программу из упражнения 1.22, чтобы она выводила в виде графика количество ребер, требующихся для соединения N элементов,100 < N< 1000.
1.24. Приведите приближенную формулу для определения количества случайных ребер, требующихся для соединения N объектов, как функции от N.
Каждый из алгоритмов, рассмотренных в разделе 1.3, кажется определенным усовершенствованием предыдущего, но, вероятно, процесс был искусственно упрощен, поскольку разработка самих этих алгоритмов уже была выполнена рядом исследователей в течение многих лет (см. раздел использованной литературы). Реализации просты, а задача четко определена, поэтому мы можем оценить различные алгоритмы непосредственно, экспериментальным путем. Более того, мы можем подкрепить эти исследования, количественно сравнив производительность алгоритмов (см. ). Не все задачи, рассмотренные в этом курсе, столь же хорошо проработаны, как эта, и мы обязательно встретимся с алгоритмами, которые трудно сравнить, и с математическими задачами, которые трудно решить. Мы стремимся принимать объективные научно обоснованные решения об используемых алгоритмах, изучая свойства реализаций на примере их выполнения применительно к реальным данным, полученным из приложений, или случайным тестовым наборам данных.
Этот процесс — прототип того, как различные алгоритмы решения фундаментальных задач рассматриваются в данном курсе. Когда это возможно, мы предпринимаем те же основные шаги, что и при рассмотрении алгоритмов объединения-поиска, описанных в разделе 1.2, часть из которых перечислена ниже:
Потенциальная возможность впечатляющего повышения производительности алгоритмов решения реальных задач, подобных рассмотренным в разделе 1.2, делает разработку алгоритмов увлекательной областью исследования; лишь немногие другие области разработки позволяют обеспечить экономию времени в миллионы, миллиарды и более раз.
Что еще важнее, по мере повышения вычислительных возможностей компьютеров и приложений разрыв между быстрыми и медленными алгоритмами увеличивается. Новый компьютер может работать в 10 раз быстрее и может обрабатывать в 10 раз больше данных, чем старый, но при использовании квадратичного алгоритма, наподобие быстрого поиска, новому компьютеру потребуется в 10 раз больше времени для выполнения новой задачи, чем требовалось старому для выполнению старой! Вначале это утверждение кажется противоречивым, но его легко подтвердить простым тождеством
(10N)2/10 = 10N2
, как будет показано в . По мере того как вычислительные мощности увеличиваются, позволяя решать все более сложные задачи, важность использования эффективных алгоритмов также возрастает.
Разработка эффективного алгоритма приносит моральное удовлетворение и непосредственно окупается на практике. Как видно на примере решения задачи связности, просто сформулированная задача может приводить к изучению множества алгоритмов, которые не только полезны и интересны, но и представляют увлекательную и сложную для понимания задачу. Мы встретимся со многими остроумными алгоритмами, которые были разработаны за долгие годы для решения множества практических проблем. По мере расширения области применения компьютерных решений для научных и экономических проблем возрастает важность использования эффективных алгоритмов для решения известных задач и разработки эффективных решений для новых проблем.
Упражнения
1.25. Допустим, что взвешенное быстрое объединение используется для обработки в 10 раз большего количества соединений на новом компьютере, который работает в 10 раз быстрее старого. На сколько больше времени потребуется для выполнения новой задачи на новом компьютере по сравнению с выполнением старой задачи на старом компьютере?
1.26. Выполните упражнение 1.25 для случая использования алгоритма, который требует выполнения N3 инструкций.
В этом разделе приведены краткие описания основных частей курса и раскрытых в них отдельных тем с указанием общего подхода к материалу. Выбор тем диктовался стремлением осветить как можно больше базовых алгоритмов. Некоторые из освещенных тем относятся к фундаментальным темам компьютерных наук, которые мы подробно изучаем для изучения основных алгоритмов широкого применения. Другие рассмотренные алгоритмы относятся к специализированным областям компьютерных наук и связанным с ними областям, таким как численный анализ и исследование операций — в этих случаях приведенный материал служит введением в эти области через исследование базовых методов.
В первых четырех частях, включенных в этот том, освещен наиболее широко используемый набор алгоритмов и структур данных — первый уровень абстракции для коллекций объектов с ключами, который может поддерживать широкое множество важных основополагающих алгоритмов. Рассматриваемые алгоритмы — результаты десятков лет исследований и разработки, и они продолжают играть важную роль во все более широком применении компьютеров.
В частях с V по VIII, которые вынесены в отдельные тома, описаны дополнительные применения описанных алгоритмов — второй уровень абстракций, характерный для ряда важных областей применения. Кроме того, в этих частях более глубоко рассмотрены технологии разработки и анализа алгоритмов. Многие из затрагиваемых проблем являются предметом предстоящих исследований.
Изучение алгоритмов представляет интерес, поскольку это новая отрасль (почти все изученные в этом курсе алгоритмы не старше 50 лет, а некоторые были открыты лишь недавно) с богатыми традициями (некоторые алгоритмы известны уже в течение тысяч лет). Постоянно делаются новые открытия, но лишь немногие алгоритмы исследованы полностью. В этом курсе мы рассмотрим замысловатые, сложные и трудные алгоритмы, наряду с изящными, простыми и легко реализуемыми алгоритмами. Наша задача — понять первые и оценить вторые в контексте множества различных потенциально возможных приложений. В процессе этого нам предстоит исследовать ряд полезных инструментов и выработать стиль алгоритмического мышления, который пригодится при решении предстоящих вычислительных задач.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.