Рис. 3.3. Паросочетания (не максимальное число)
Посмотрим, каким образом можно из друзей составить романтические пары. Начнем с Артура и соединим его с Евой. Боб и Фелисити пока одиноки; соединим их, а также Карла с Гейл. На рис. 3.4 романтические связи обозначены пунктирной линией.
Рис. 3.4. Максимальное число паросочетаний
Теперь у нас не осталось пар друзей, в которых оба были бы свободны. Может, это означает, что мы составили максимальное паросочетание? А вот и нет.
У Дэвида нет пары, однако он дружит с Фелисити, которую мы сочетали с Бобом. Боб дружит с Гейл, но чету они не образуют. Гейл соединена с Карлом, а Карл дружит с одинокой Хелен. Разлучим Боба с Фелисити и Карла с Гейл и составим новые связи. Теперь пара есть у всех!
Вернемся к рис. 3.3. Цепь из чередующихся сплошных и пунктирных линий, первый и последний элемент которой не имеет пары, т. е. не принадлежит паросочетанию, называется увеличивающим путем. При наличии увеличивающего пути мы всегда можем увеличить наше паросочетание. В 1957 году математик Клод Берж показал, что для любого паросочетания, не являющегося максимальным, существует увеличивающий путь. Программисты Королевского технологического реализовали алгоритм нахождения увеличивающих путей, основанный на методе последовательного поиска, и в результате смогли подобрать пару для 98 процентов участников эксперимента.
Вскоре после описанных событий Королевский верховный суд вынес постановление, разрешающее однополые браки. На сайте института тут же вывесили объявление о наборе волонтеров любых сексуальных ориентаций. Схемы заметно усложнились; появились даже любовные треугольники, которые к тому же частично пересекались друг с другом (см. ниже).
Простыми методами находить увеличивающие пути уже не получалось, и исследователи обратились к трудам Джека Эдмондса. В 1965 году Эдмондс написал работу с изящным названием "Пути, деревья и цветы", в которой представил усложненный алгоритм поиска увеличивающих путей, подходящий для совершенно произвольных схем. Реализовав метод Эдмондса, специалисты института сумели подобрать пару для 97 процентов участников второго эксперимента.
"Пути, деревья и цветы" дали нам не только эффективный способ решения задачи о паросочетаниях для случая произвольной схемы. В группе из 100 человек алгоритм Эдмондса находит максимальное паросочетание примерно за 100, т. е. 100000000 (сто миллионов) шагов, что для современного компьютера сущий пустяк. Методичный перебор всех возможных сочетаний вылился бы примерно в два квинвигинтиллиона шагов, а один квинвигинтиллион – это, между прочим, единица и 78 нулей! В работе Эдмондса есть довольно длинное отступление на тему эффективных алгоритмов. Понимая, что для такого, в сущности, интуитивного понятия, как эффективность, подобрать полноценное формальное определение очень сложно, Эдмондс все-таки предлагает некий критерий. Он называет алгоритм эффективным, если тот находит решение за "алгебраическое" время, т. е. время, "алгебраически" зависящее от размера входных данных. Для 100 человек это может быть, к примеру, 100, 100 или 100. В дальнейшем класс задач, для которых существуют такие алгоритмы, получил обозначение "P" – от слова "полиномиальный", заменившего эдмондсовское понятие "алгебраический". Таким образом, класс P представляет собой все многообразие задач, которые можно решить относительно быстро. Ну что ж – в споре "P против NP" мы выслушали мнение первой стороны.
Рис. 3.5. Нетрадиционные потенциальные пары
В поисках клики
В рамках проводимого исследования институтскому профессору социологии понадобилось найти 50 жителей Королевства, которые дружили бы между собой. Своими силами справиться с задачей не удалось, и профессор обратилась на факультет компьютерных наук, где один из специалистов рассказал ей о базе дружеских связей и уверенно заявил, что клика из 50 друзей найдется без труда.
На деле выяснилось, что труд здесь требуется совершенно непосильный. Количество различных групп размера 50 оказалось непомерно огромным и выражалось числом из 151 цифры; не было и речи о том, чтобы проверить хотя бы сотую долю вариантов. Круг поиска пытались сузить всеми возможными способами – в частности, отсекли тех жителей, у которых было меньше 49 друзей, поскольку они-то уж точно не могли входить в искомую клику. Однако, несмотря на свою высокую квалификацию, исследователи не набрали и 25 друзей и при этом не смогли представить убедительное доказательство того, что клики размера 50 в Королевстве не существует.
Работа встала. Исследователи опустили руки. Внезапно одного из аспирантов осенило: "Слушайте, у нас же есть "Альфа"!" "Альфой" называлось известное, но при этом полусекретное сообщество, все члены которого, по слухам, дружили между собой. Пятьдесят "альфовцев" удалось найти довольно быстро: ведь, в конце концов, секретным сообщество было лишь наполовину. Оставалось только перебрать 1225 пар, чтобы проверить дружеские связи. К изумлению исследователей (но не самих "альфовцев", разумеется), все пятьдесят действительно оказались друзьями. Клика нашлась.
Передай скипетр
Иногда достаточно внести лишь одно незначительное изменение, чтобы задача, решение которой находится очень легко, стала прямо-таки неприступной, и сейчас мы с вами в этом убедимся.
Дети в Королевстве любят играть в игру под названием "Передай скипетр", в которой участники по очереди передают друг другу небольшую палку. Передачей считается тот момент, когда палку держат двое – передающий и принимающий.
Правила игры:
1. Палку можно передавать только друзьям.
2. Между любыми двумя друзьями палка должна переместиться ровно один раз.
Пусть в игре участвуют пятеро детей. Одно из возможных решений таково: начинают с Барбары, она передает палку Эрику, Эрик – Алексу, Алекс – Кэти, Кэти – снова Эрику, а Эрик – Дэвиду.
Рис. 3.6. Дети
Дети, которые играют в "Передай скипетр" часто, вскоре понимают: решение существует, когда нечетное число друзей среди игроков имеется не более чем у двух участников. В данном случае таких участников у нас ровно два – это Дэвид и Барбара, у каждого из которых среди играющих есть только один друг. У остальных детей количество друзей четно: у Алекса и Кэти – по два, у Эрика – четыре. Вы спросите, причем тут четность? А вот причем: чтобы передать кому-то палку, нужно сначала получить ее, поэтому каждый игрок, кроме первого и последнего, обязательно участвует в четном количестве передач.
Рис. 3.7. Дети: число друзей у всех четно
Когда у всех участников число друзей четно, в случае успешного исхода палка возвращается к тому, с кого начали.
В данной ситуации решение может быть таким: начинают с Алекса, он передает палку Эрику, Эрик – Дэвиду, Дэвид – Барбаре, Барбара – снова Эрику, Эрик – Кэти, а Кэти – Алексу.
Прообразом игры "Передай скипетр" послужила одна очень известная головоломка XVIII века. В прусском городе Кёнигсберге (а ныне российском Калининграде) через реку Прегель и ее рукава было перекинуто семь мостов (см. карту на рис. 3.8).
Рис. 3.8. Старинная карта мостов Кёнигсберга
Жителям долгое время не давал покоя вопрос: можно ли посетить все районы города, проходя по каждому мосту ровно один раз? В 1735 году знаменитый математик Леонард Эйлер придумал, как изобразить задачу в виде схемы (см. рис. 3.9).
Рис. 3.9. Схема Эйлера
Очень похоже на игру со скипетром, и критерий существования решения здесь тот же; единственное отличие заключается в том, что узами дружбы связаны уже не дети, а районы города – Северный, Восточный, Южный и Остров. Эйлер доказал, что пройти по каждому мосту ровно один раз невозможно, поскольку во всех районах города количество мостов нечетно.
Так и выяснилось, что задача о семи мостах не имеет решения. В память об этом в игре со скипетром любой подходящий путь (а их бывает несколько) называется эйлеровым. Эйлеров путь можно искать по-разному, в том числе и простым перебором, однако при увеличении количества участников число вариантов заметно возрастает. Дети в Королевстве первым делом пересчитывают игроков с нечетным числом друзей, чтобы понять, существует ли вообще решение; если оно существует, то найти искомый путь уже не составляет особого труда. Поиск эйлерова пути – еще один пример задачи из класса P, т. е. задачи, для которой существует эффективный алгоритм.