Рис. 3.1. Дружеские связи в Королевстве
Чтобы добраться от Элис до Джорджа, нужно пройти по цепочке из шести связей: Элис дружит с Бобом, Боб – с Кэти, Кэти – с Дэвидом, Дэвид – с Евой, Ева – с Фредом, а Фред – с Джорджем. Исследователи задумались: можно ли любую пару жителей соединить относительно короткой цепочкой дружеских связей? Проявится ли здесь феномен "тесного мира"? Кстати, название феномена пошло вовсе не от аттракциона в Диснейленде, а от слов "мир тесен", которые мы обычно произносим, когда знакомимся с кем-то и выясняем, что нас связывает нечто общее (пусть даже очень отдаленно).
В 1967 году психолог Стэнли Милгрэм поставил свой знаменитый эксперимент по проверке теории "тесного мира". Сначала он выбрал некоего биржевого маклера, проживающего в Бостоне. Имя маклера сохранялось в секрете; для удобства назовем его Том Джонс. Далее совершенно случайным образом в Небраске были выбраны сто держателей акций. Потом – сто людей, не являвшихся акционерами. И, наконец, в Бостоне по объявлению в газетах были найдены еще сто участников. Вторая группа из Небраски и группа из Бостона не имели никакого отношения к инвестиционному миру. Каждому из трехсот участников Милгрэм отослал пакет, в который вложил список инструкций, реестр и пятнадцать почтовых открыток с маркой, адресованных ему в Гарвардский университет. Инструкции выглядели так:
1. Занесите свое имя в реестр.
2. Заполните одну из открыток и бросьте ее в почтовый ящик.
3. Если вы лично знаете бостонского биржевого маклера по имени Том Джонс, перешлите пакет ему.
4. В противном случае выберите среди своих знакомых кого-нибудь, кто, по-вашему, с большей степенью вероятности знает Тома Джонса и чье имя пока не значится в реестре, и перешлите пакет ему (или ей).
Из трехсот участников двести семнадцать переслали пакет своим друзьям. Шестьдесят четыре письма в конце концов добрались до цели, т. е. до Тома Джонса. Средняя длина цепочки оказалась равна 5,2; в результате возникло понятие "шесть степеней отчуждения", означающее, что любых двух человек на планете в среднем разделяет цепочка из шести связей. Отдельные аспекты эксперимента подверглись резкой критике; впрочем, Милгрэм и сам не возводил феномен шести степеней в статус закона, однако его эксперимент показал, что мы связаны гораздо теснее, чем можно было бы ожидать.
Придумывая различные определения понятия связи – более специфические, чем простое знакомство, – можно исследовать и анализировать людские сообщества. Иногда таким образом возникают салонные игры, в которых требуется вычислить расстояние от произвольного человека до некой "центровой" персоны, обладающей, как правило, большим количеством связей. В 1994 году Кевин Бэйкон, выступая в поддержку своего фильма "Дикая река", в шутку заметил, что все актеры в Голливуде снимались либо с ним самим, либо с теми, кто с ним снимался. Тут же родилась игра под названием "Шесть шагов до Кевина Бэйкона", цель которой – найти кратчайший путь между заданным актером и Бэйконом через актеров, с которыми они вместе снимались. Для многих актеров путь до Бэйкона (и, соответственно, друг до друга) оказался очень коротким. Например, Чарли Чаплин находится от Бэйкона всего в трех шагах: в 1967 году он снял фильм "Графиня из Гонконга", в котором сам сыграл второстепенную роль; графиню играла Софи Лорен, которая в 1979 году снялась в малоизвестном фильме "Сила огня"; одну из главных ролей в этом фильме сыграл Илай Уоллак, позднее появившийся в эпизодической роли в фильме "Таинственная река"; в этом же фильме снимался и Бэйкон.
У математиков тоже есть похожая игра: через совместные публикации они ищут расстояние до Пола Эрдёша – гения комбинаторики и рекордсмена по количеству публикаций.
В Королевском технологическом решили выяснить, выполняется ли закон "шести степеней" для дружеских связей между жителями Королевства. Как проверить, существует ли цепочка из шести связей между Элис и Джорджем? Простейший способ – перебрать все существующие цепочки длины шесть. Вот только в Королевстве, насчитывающем 20000 жителей, таких цепочек может набраться 3198400279980000480000. Даже если предположить, что компьютер будет проверять триллион цепочек в секунду, на решение задачи уйдет более ста лет. Неужели нет способа получше?
Оказывается, есть. Существует совсем не сложная процедура, позволяющая быстро определить расстояние между Элис и Джорджем.
• Присвоим Элис число 0.
• Присвоим всем друзьям Элис число 1.
• Присвоим число 2 всем друзьям тех, кто получил число 1 и у кого пока еще нет числа.
• Присвоим число 3 всем друзьям тех, кто получил число 2 и у кого пока еще нет числа.
• Продолжаем до тех пор, пока Джордж не получит число.
• Число Джорджа и будет расстоянием между ним и Элис.
Подобные неформальные описания вычислительных процессов называются алгоритмами. Своим названием алгоритмы обязаны персидскому математику по имени Мухаммад ибн Муса Аль-Хорезми, жившему в VIII–IX веке н. э. В 825 году Аль-Хорезми написал трактат "Книга об индийском счете", благодаря которому индийская система счисления широко распространилась сначала на Востоке, а затем и в Европе. В латинском переводе книга получила название Algoritmi de numero Indorum. Имя Аль-Хорезми превратилось на латыни в Algoritmi, что в конечном итоге и привело к возникновению термина "алгоритм".
Упомянутый выше алгоритм вычисляет длину пути между Элис и Джорджем приблизительно за полмиллиона шагов. Если мы захотим найти степень отчуждения для всех пар жителей Королевства, нам потребуется средство помощнее: алгоритм Флойда – Уоршелла, который справится с задачей примерно за восемь триллионов шагов. Вам кажется, что триллион – это ужасно много? Но ведь компьютеры и сейчас уже способны выполнять миллиарды операций в секунду, так что мощные институтские процессоры вообще посчитали все за пару минут. В результате выяснилось, что средняя степень отчуждения в Королевстве чуть больше шести. При этом были найдены совершенно изолированные группы друзей, не имеющие дружеских связей с остальными жителями Королевства.
Не стоит недооценивать важность этого события. В институте, конечно, могли бы написать программу, которая методично перебирает все возможные пути, пытаясь найти минимальное количество связей между Элис и Джорджем; вот только этой программе пришлось бы проверить столько путей, что она просто не закончила бы работу за разумное время. Более эффективный алгоритм позволил вычислить степень отчуждения для Элис и Джорджа за ничтожную долю секунды, а для всех пар жителей – за каких-то две минуты.
Задача о числе паросочетаний
В Королевстве заклятых друзей залог счастливых отношений – это прежде всего крепкая дружба. Правда, дружеские связи возникают совершенно бессистемно; хорошо, если вам встретился подходящий партнер, но ведь не всем так везет!
Институтские исследователи вскоре поняли, что их база может принести пользу обществу, и решили с ее помощью повысить число удачных браков. На сайте института появилось объявление о наборе 200 волонтеров: по 100 мужчин и женщин гетеросексуальной ориентации. Волонтеры откликнулись очень быстро. Теперь ученым предстояло "поженить" как можно больше участников.
Сколько вариантов должен рассмотреть каждый участник? Первому мужчине потенциально подходят 100 женщин. Когда выбор сделан, у второго мужчины остается 99 вариантов, у третьего – 98, и так далее. Итого получается 100 умножить на 99 умножить на 98 умножить на… умножить на 2 умножить на 1 – величина, называемая факториалом числа 100 и записываемая в виде "100!". Факториал числа 100 состоит из 158 цифр и намного превосходит гугол – число, изображаемое единицей со ста нулями. Термин "гугол" изобрел девятилетний племянник математика Эдварда Казнера, когда тот попросил мальчика придумать числу название.
Название компании Google призвано отражать огромный объем информации, обрабатываемый поисковыми сереверами: это искажение от "гугол" (англ. "googol"). Впрочем, отражает оно этот объем, мягко говоря, некорректно. Интернет, конечно, большой, и измерить его точно не представляется возможным, однако объем содержащейся в нем информации и близко не подходит к гуголу, какими бы мелкими единицами мы его ни измеряли. Если мы даже составим вместе все когда-либо созданные нами компьютеры, то и тогда, вне всяких сомнений, не получим гугол (и уж тем более факториал числа сто).
Однако у ученых все же оставался шанс соединить как можно больше пар, т. е. найти максимальное число паросочетаний. Для этого просто нужно было воспользоваться специальным алгоритмом. На рисунке ниже представлены несколько пар друзей.
Рис. 3.2. Потенциальные пары в Королевстве