Искусство мыслить рационально. Шорткаты в математике и в жизни - Маркус Дю Сотой Страница 86

А как насчет задачи коммивояжера? Можно ли найти шорткат к ней при помощи нетрадиционных средств? Одну из задач, родственных задаче коммивояжера, исследователям удалось решить, применив компьютер очень необычного типа. В этой задаче – так называемой задаче о гамильтоновом пути – нужно проложить маршрут по сети дорог с односторонним движением, соединяющих нанесенные на карту города́.

Рис. 10.4. Задача о гамильтоновом пути: как попасть из города А в город E, посетив все остальные города только по одному разу?

Требуется найти маршрут, начинающийся из одного города, скажем А, и заканчивающийся в другом городе – Е, – нопроходящий через все остальные города по одному, и только одному, разу. Возможен ли такой маршрут? Оказывается, найти его так же трудно, как решить задачу коммивояжера. Но и эта задача прекрасно подходит для применения параллельной обработки информации. Однако математик Леонард Адлеман не стал обращаться к квантовому миру, а придумал интересный биологический подход к ее решению. К слову, именно фамилию Адлемана обозначает буква А в аббревиатуре RSA, названии шифровальной системы, использующей простые числа для обеспечения безопасности сетевых транзакций.

В 1994 году Адлеман объявил на семинаре в MIT об изобретении суперкомпьютера, который он построил для решения задачи о гамильтоновом пути. Он назвал его TT-100, но его слушатели очень удивились, когда он достал из кармана пиджака обычную пробирку. Буквы ТТ означали test tube ^[132], а число 100 – объем этой пластмассовой пробирки, 100 миллилитров. Роль микропроцессоров, работавших в пробирке, играли небольшие нити ДНК.

Нити ДНК составляются из четырех оснований, которые обозначают буквами A, T, C и G ^[133]. Эти основания стремятся попарно соединяться друг с другом: А с Т, а C – с G. Если получить короткие одиночные нити, составленные из этих оснований, – так называемые олигонуклеотиды, – каждая из них попытается найти другую нить, основания которой могут образовывать пары с ее собственными. Например, нить АСА попытается найти нить TGT, с которой она может соединиться и образовать устойчивую двойную нить ДНК.

Идея Адлемана состояла в следующем: присвоим каждому городу на карте, по которой мы пытаемся проложить маршрут, метку, представляющую собой нить из 8 оснований. Затем, если между двумя городами есть односторонняя дорога, создадим нить ДНК с 16 основаниями, первые 8 из которых содержатся в метке города отправления, а вторые 8 – это основания, дополнительные к содержащимся в метке города, в который ведет дорога. Если есть дорога, ведущая в город А, и дорога, ведущая из него, две нити этих дорог, содержащие по 16 оснований, соединятся: последние 8 оснований дороги, ведущей в город А, свяжутся с первыми 8 основаниями дороги, ведущей из него.

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

Например, у города А может быть метка ATGTACCA, у города B – GGTCCACG, а у города C – TCGACCGG. Тогда дороге из А в B будет соответствовать нить