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

Такие приложения, как задача установления эквивалентности имен переменных, описанная в предыдущем абзаце, требует, чтобы целое число было сопоставлено с каждым отдельным именем переменной. Это сопоставление подразумевается также в описанных приложениях сетевого соединения и соединения в электрической цепи. В главах 10-16 мы рассмотрим ряд алгоритмов, которые могут эффективно обеспечить такое сопоставление. Таким образом, в этой главе без ущерба для общности можно предположить, что имеется N объектов с целочисленными именами от О до Л- 1.

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

Например, приведенное определение задачи связности требует только, чтобы программа как-либо узнавала, является ли данная пара p-q связанной, но не была способна демонстрировать любой или все способы соединения этой пары. Добавление в определение такого требования усложняет задачу и привело бы к другому семейству алгоритмов, которое будет кратко рассматриваться в главе 5 и подробно - в части 7.

Упомянутые в предыдущем абзаце определения требуют больше информации, чем первоначальное; может также требоваться меньше информации. Например, может требоваться просто ответить на вопрос: Достаточно ли М связей для соединения всех N объектов? . Эта задача служит иллюстрацией того, что для разработки эффективных алгоритмов часто требуется выполнение умозаключений об абстрактных обрабатываемых объектах на высоком уровне. В данном случае из фундаментальных положений теории графов следует, что все N объектов связаны тогда и только тогда, когда количество пар, образованных алгоритмом решения задачи связности, равно точно N- 1 (см. раздел 5.4). Иначе говоря, алгоритм решения задачи связности никогда не образует более Л- 1 пар, поскольку как только он образует Л- 1 пару, любая встретившаяся после этого пара будет уже связанной. Соответственно, можно создать программу, отвечающую да-нет на только что поставленный вопрос, изменив программу, которая решает задачу связности, на такую, которая увеличивает значение

счетчика, а не записывает ранее не связанную пару, отвечая да , когда значение счетчика достигает Л - 1, и нет , если это не происходит. Этот вопрос - всего лишь один из множества, которые могут возникнуть относительно связности. Входной набор пар называется графом (Graph), а выходной набор пар - остовным деревом (spanning tree) этого графа, которое связывает все объекты. Свойства графов, остов-ных деревьев и всевозможные связанные с ними алгоритмы будут рассматриваться в части 7.

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

находить набор, содержащий данный элемент

замещать наборы, содержащие два данных элемента, их объединением.

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

Задача связности легко решается посредством абстрактных операций find (поиск) и union (объединение). После считывания новой пары p-q из ввода мы выполняем операцию find для каждого члена пары. Если члены пары находятся в одном наборе, мы переходим к следующей паре; если нет, то выполняем операцию union и записываем пару. Наборы представляют связанные компоненты: поднаборы объектов, характеризующиеся тем, что любые два объекта в данном компоненте связаны. Этот подход сводит разработку алгоритмического решения задачи связности к задачам определения структуры данных, которая представляет наборы, и разработке алгоритмов union и find, которые эффективно используют эту структуру данных.

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

Упражнения

1.1 Приведите вывод, который должен создаваться алгоритмом связности при заданном вводе 0-2, 1-4, 2-5, 3-6, 0-4, 6-0 и 1-3.

1.2 Перечислите все различные способы связывания двух различных объектов, показанных в примере на рис. 1.1.

1.3 Опишите простой метод подсчета количества наборов, остающихся после использования операций union и find для решения задачи связности, как описано в тексте.

1.3 Алгоритмы объединение-поиск

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

Первое что приходит в голову - как-либо сохранить все вводимые пары, а затем создать функцию для их просмотра, чтобы попытаться выяснить, связана ли следующая rtapa объектов. Однако нам придется использовать другой подход. Во-первых, количество пар может быть достаточно велико, что не позволит сохранить их все в памяти в используемом на практике приложении. Во-вторых, что гораздо важнее, не существует никакого простого метода, который сам по себе позволяет определить, связаны ли два объекта в наборе всех соединений, даже если бы удалось их все сохранить! Базовый метод, использующий этот подход, рассматривается в главе 5, методы, которые исследуются в этой главе, проще, поскольку они решают менее сложную задачу, и эффективнее, поскольку не требуют сохранения всех пар. Все они используют массив целых чисел, каждое из которых соответствует отдельному объекту, для хранения информации, необходимой для реализации операций union и Jind.

Массивы - это элементарные структуры данных, которые подробно изучаются в разделе 3.2. Здесь же они используются в простейшей форме: мы объявляем, что собираемся использовать, скажем, 1000 целых чисел, записывая а[1000]; затем обращаемся к /-ому целому числу в массиве, записывая a[i] для 0</< 1000.

Программа 1.1 - реализация простого алгоритма, называемого алгоритмом быстрого поиска, решающего задачу связности. В основе этого алгоритма лежит использование массива целых чисел, обладающих тем свойством, что р и д связаны тогда и только тогда, когда р-ая и -ая записи массива равны. Мы инициализируем /-ую запись массива значением / при 0< i < N. Чтобы реализовать операцию union для р д, мы просматриваем массив, изменяя все записи с именем р на записи с именем д. Этот выбор произволен - можно было бы все записи с именем д изменять на записи с именем р.

Программа 1.1 Решение задачи связности методом быстрого поиска

Эта программа считывает последовательность пар неотрицательных целых чисел, меньших чем N, из стандартного ввода (интерпретируя пару р q, как связать объект р с объектом q ) и выводит пары, представляющие объекты, которые еще не связаны. Она поддерживает массив id, содержащий запись для каждого объекта и характеризующийся тем, что элементы ld[p] и id[q] равны тогда и только тогда, когда