Золотой билет. P, NP и границы возможного - стр. 20
Оказывается, есть. Существует совсем не сложная процедура, позволяющая быстро определить расстояние между Элис и Джорджем.
• Присвоим Элис число 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 цифр и намного превосходит гугол – число, изображаемое единицей со ста нулями. Термин «гугол» изобрел девятилетний племянник математика Эдварда Казнера, когда тот попросил мальчика придумать числу название.