Читать «Золотой билет» онлайн - страница 24

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

Задача о числе паросочетаний

В Королевстве заклятых друзей залог счастливых отношений – это прежде всего крепкая дружба. Правда, дружеские связи возникают совершенно бессистемно; хорошо, если вам встретился подходящий партнер, но ведь не всем так везет!

Институтские исследователи вскоре поняли, что их база может принести пользу обществу, и решили с ее помощью повысить число удачных браков. На сайте института появилось объявление о наборе 200 волонтеров: по 100 мужчин и женщин гетеросексуальной ориентации. Волонтеры откликнулись очень быстро. Теперь ученым предстояло «поженить» как можно больше участников.

Сколько вариантов должен рассмотреть каждый участник? Первому мужчине потенциально подходят 100 женщин. Когда выбор сделан, у второго мужчины остается 99 вариантов, у третьего – 98, и так далее. Итого получается 100 умножить на 99 умножить на 98 умножить на… умножить на 2 умножить на 1 – величина, называемая факториалом числа 100 и записываемая в виде «100!». Факториал числа 100 состоит из 158 цифр и намного превосходит гугол – число, изображаемое единицей со ста нулями. Термин «гугол» изобрел девятилетний племянник математика Эдварда Казнера, когда тот попросил мальчика придумать числу название.

Название компании Google призвано отражать огромный объем информации, обрабатываемый поисковыми сереверами: это искажение от «гугол» (англ. «googol»). Впрочем, отражает оно этот объем, мягко говоря, некорректно. Интернет, конечно, большой, и измерить его точно не представляется возможным, однако объем содержащейся в нем информации и близко не подходит к гуголу, какими бы мелкими единицами мы его ни измеряли. Если мы даже составим вместе все когда-либо созданные нами компьютеры, то и тогда, вне всяких сомнений, не получим гугол (и уж тем более факториал числа сто).

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