Новости
20.08.2024
В число алгоритмов, рассмотренных в книге, вошли различные методы сортировки, перебор, поиск в глубину и ширину, обход графов, четыре алгоритма поиска кратчайшего пути, два алгоритма минимального остовного дерева, алгоритмы определения вершин и ребер разреза, а также поиск наибольшего паросочетания в двудольных графах и многое другое.
Борьба с преступностью
Мы рассмотрели применение деревьев для реализации куч. Где еще можно использовать деревья? Например, в борьбе с преступностью.
Перед новогодними праздниками в городе Сени резко выросло число ограблений. Полиция решила выяснить состав преступных группировок. Вот данные, которые им удалось собрать:
В городе действуют 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 года. Такие люди никогда не сидят без дела, они работают, чтобы менять мир.
Ну вот и подошла к концу очередная глава. На самом деле существует множество разновидностей деревьев и вариантов их применений. Это, например, танцующие деревья, префиксные деревья, красно-черные деревья (разновидность сбалансированного дерева двоичного поиска) и т. д. Такие структуры данных имеют более высокую сложность, поэтому не рассматриваются в нашей книге.
На подведении итогов 40-й юбилейной Национальной олимпиады по информатике (NOI) он был признан выдающимся педагогом, а его студенты добились огромных успехов, завоевав четыре золотые, восемнадцать серебряных и тринадцать бронзовых медалей, а также более пятисот первых мест в национальных олимпиадах по информатике.
Тираж его книг по алгоритмам и языку Си превышает 300 тысяч экземпляров.
Более подробно с книгой можно ознакомиться на сайте издательства
Комментарии: 0
Пока нет комментариев