Привет, Хаброжители!

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

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

Борьба с преступностью

Мы рассмотрели применение деревьев для реализации куч. Где еще можно использовать деревья? Например, в борьбе с преступностью.


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

В городе действуют 11 бандитов.

Бандит 1 связан с бандитом 2.
Бандит 3 связан с бандитом 4.
Бандит 5 связан с бандитом 2.
Бандит 4 связан с бандитом 6.
Бандит 2 связан с бандитом 6.
Бандит 7 связан с бандитом 11.
Бандит 8 связан с бандитом 7.
Бандит 9 связан с бандитом 7.
Бандит 9 связан с бандитом 11.
Бандит 1 связан с бандитом 6.

Задача — выяснить, сколько преступных группировок имеется в городе.

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

Создадим одномерный массив f, в элементах которого будем хранить информацию о связях грабителей. Поскольку мы считаем, что вначале каждый грабитель работает сам по себе, элементам массива присваиваются значения номеров соответствующих грабителей, например f[1] = 1, а f[11] = 11.


Начнем «формировать» банды: если выясняется, что два грабителя связаны, значит, они входят в одну преступную группировку. Теперь возникает вопрос: кого будем считать боссом преступной группировки? Например, если бандиты 1 и 2 — подельники, то кого к кому следует присоединить, первого ко второму или наоборот? Давайте договоримся считать главным бандита, который упоминается первым. Поэтому изменим число в f [2] на 1.


Переходим к следующей информации от полиции: «бандиты 3 и 4 — партнеры». Согласно принципу упоминания, первым бандит 4 подчиняется бандиту 3, поэтому значение f[4] изменяем на 3.


Далее нам нужно обработать сообщение о связи бандитов 5 и 2. При этом мы знаем, что бандит 2 подчиняется бандиту 1, а бандит 5 до этого момента считался действующим в одиночку. Согласно принципу упоминания, первым следует подчинить бандита 2 бандиту 5, однако вряд ли это понравится бандиту 1.


Как гласит старая поговорка, «чтобы поймать вора, сначала поймайте короля». Будем считать, что бандит 1 добровольно согласился подчиниться бандиту 5, который на время становится королем преступного мира. При этом информация о взаимоотношениях бандитов 1 и 2 остается неизменной.


Следующее сообщение говорит о связи бандитов 4 и 6. Поскольку f [4] имеет значение 3, бандит 6 присоединяется к преступной группировке, возглавляемой бандитом 3, — изменим значение f [6] на 3.


Далее выясняется, что сообщниками являются бандиты 2 и 6. f [2] имеет значение 1, а f [1] — значение 5, то есть боссом бандита 2 является бандит 5. f [6] имеет значение 3, то есть бандит 6 подчиняется бандиту 3. Согласно нашим принципам, мы подчиним бандита 3 бандиту 5, поэтому изменим значение f [3] на 5. Таким образом, бандит 3 приведет своих людей под начало бандита 5.

На этом этапе мы также подчиним бандита 2 непосредственно бандиту 5, изменив значение f [2] с 1 на 5. Продвижение в иерархии — в порядке вещей в бандах и компаниях. И в алгоритмах проверки на вхождение в множество есть специальный термин «сжатие пути», а соответствующий код будет показан позже.


Внимательные читатели могут заметить, что переподчинение бандита 2 изменяет его отношения с бандитом 1. Однако это не так. Оба бандита по-прежнему принадлежат одной преступной группировке, а прямое подчинение боссу только повышает ее эффективность.

Из следующей полицейской наводки мы узнаем о связи бандитов 7 и 11. f [11] имеет значение 11, а f [7] — значение 7. По принципу подчинения первому упомянутому нам следует изменить значение f [11] на 7.


Затем мы узнаем, что сообщниками являются бандиты 8 и 7. f [8] имеет значение 8, а f [7] — 7. Значит, необходимо изменить значение f [7] на 8.


Далее выясняется связь бандитов 9 и 7. f [9] имеет значение 9, а f [7] — 8. В соответствии с нашими принципами нужно изменить значение f [8] на 9.


В следующей наводке говорится, что бандиты 9 и 11 действуют сообща. f [9] имеет значение 9, а f [11] — значение 7. Смотрим на схему и убеждаемся, что они уже обозначены как члены одной преступной группировки, однако бандит 11 подчиняется бандиту 9 не напрямую, а через бандитов 7 и 8. Процесс проверки подчинения на самом деле является рекурсивным. Чтобы упростить задачу, подчиним бандитов 11 и 7 непосредственно бандиту 9.


И наконец, нам известно о связи бандитов 1 и 6. Это хороший повод для еще одного «сжатия пути», поскольку на схеме оба грабителя уже принадлежат к одной банде. Переставим бандита 6 в прямое подчинение бандиту 5, который руководит бандитом 1.


Итак, полицейская информация проанализирована, осталось выяснить, сколько же всего преступных группировок действует в городе. Из приведенной схемы видно, что их три: первая состоит из бандитов 5, 1, 2, 3, 4 и 6; вторая — из бандитов 9, 8, 7 и 11; третья — из одного бандита 10. Очевидно, что если f [i] = i, значит, соответствующий грабитель является главарем банды, а количество главарей равно числу банд. В последнем варианте массива f [5] = 5, f [9] = 9, f [10] = 10, следовательно, существует три самостоятельные преступные группировки.


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

#include <stdio.h>
int f[1001]={0},n,m,sum=0;
// инициализация массива с присвоением элементам значений их индексов
void init()
{
    int i;
    for(i=1;i<=n;i++)
        f[i]=i;
    return;
}
// рекурсивная функция поиска корня - босса группировки
int getf(int v)
{
    if(f[v]==v)
        return v;
    else
    {
        // сжатие пути – повышение в иерархии для упрощения структуры банды
        f[v]=getf(f[v]);
        return f[v];
    }
}
// функция, объединяющая два дерева (банды)
void merge(int v,int u)
{
    int t1,t2; // t1 и t2 – номера главарей банд v и u соответственно
    t1=getf(v);
    t2=getf(u);
    if( t1!=t2 ) // проверка наличия общего босса
    {
        f[t2]=t1. // принцип упоминания первым, при котором правое множество
                  // считается подмножеством левого множества
    }
    return;
}

// начинать чтение программы с main - хорошая привычка
int main()
{
    int i,x,y;
    scanf("%d %d",&n,&m);

    init(); // инициализация обязательна
    for(i=1;i<=m;i++)
    {
        // анализ преступных группировок
        scanf("%d %d",&x,&y);
        merge(x,y);
}

    // определение количества самостоятельных преступных группировок
    for(i=1;i<=n;i++)
    {
        if(f[i]==i)
sum++;
    }
    printf("%d\n",sum);
    getchar(); getchar();
    return 0;
}

Проверьте программу, введя приведенные ниже данные. Числа n и m в первой строке обозначают число грабителей и собранных полицией сведений соответственно. В каждой из следующих m строк записаны числа a и b, указывающие на связи между грабителями.

11 10
1 2
3 4
5 2
4 6
2 6
7 11
8 7
9 7
9 11
1 6

Результат прогона:

3

Рассмотренную структуру данных называют системой непересекающихся множеств. В разработку этого алгоритма внесли большой вклад Роберт Тарьян, Джон Хопкрофт и Джеффри Ульман. Знакомые фамилии? Действительно, это те самые Тарьян и Хопкрофт, которые изобрели поиск в глубину и стали лауреатами премии Тьюринга 1986 года. Такие люди никогда не сидят без дела, они работают, чтобы менять мир.

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

Более подробно с книгой можно ознакомиться на сайте издательства:

» Оглавление
» Отрывок

По факту оплаты бумажной версии книги на e-mail высылается электронная книга.
Для Хаброжителей скидка 25% по купону — Алгоритмы