Кит Йейтс - Математика жизни и смерти. 7 математических принципов, формирующих нашу жизнь

Кстати, о жадности: вы когда-нибудь пробовали заказать 43 макнаггетса в «Макдоналдсе»? Как ни странно, эти жареные во фритюре панированные кусочки курицы породили интересную математику. В Великобритании макнаггетсы первоначально подавали в коробках по 6, 9 или 20 штук. Обедая с сыном в «Макдоналдсе», математик Анри Пиччотто решил подсчитать, сколько наггетсов он не сможет заказать одномоментно, используя комбинации из трех коробок. Ответом стал числовой ряд 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37 и 43. Все остальные «наборы» наггетсов составить было можно; эти числа с того дня стали известны как числа Макнаггетса. Самое большое число, которое нельзя получить, комбинируя с кратными величинами заданного набора чисел, называется числом Фробениуса. Числом Фробениуса для куриных макнаггетсов, таким образом, было 43. К сожалению, когда «Макдоналдс» добавил в ассортимент упаковки по 4 наггетса, число Фробениуса упало до 11. Забавно, что даже с добавлением этой новой коробки, жадный алгоритм не позволит набрать 43 наггетса (две порции по 20 дадут сразу 40, а порции из 3 наггетсов нет), так что получить на заказ 43 наггетса в «Макавто» сегодня все еще непросто – хотя набрать это количество и возможно.

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

Одна из процедур, известная как муравьиный алгоритм, посылает армии компьютерных «муравьев» для исследования виртуальной среды, отражающей реальную проблему. Так, при решении задачи коммивояжера муравьи снуют между близлежащими пунктами назначения, отражая способность настоящих муравьев воспринимать лишь ближайшее для них окружение. Если муравьи находят короткий маршрут по всем точкам, то они метят его феромонами, чтобы направить по нему других муравьев. Более востребованные и, соответственно, более короткие маршруты привлекают больше муравьиного трафика. Как и в реальном мире, выделенный феромон испаряется, позволяя муравьям гибко менять оптимальную маршрутизацию при изменении пунктов назначения. Муравьиный алгоритм используется для поиска эффективных решений проблем NP-группы – таких как проблема маршрутизации транспортных потоков, – а также для моделирования сложнейших биологических процессов, включая особенности формирования многокомпонентных трехмерных белковых структур из простых одномерных цепочек аминокислот.

Муравьиный алгоритм – всего лишь один из целого семейства так называемых алгоритмов роевого интеллекта, вдохновленных природой. Стаи скворцов или косяки рыб способны очень резко – и при этом согласованно и синхронно – менять направление движения, несмотря на то что каждая особь может коммуницировать лишь с небольшим числом особей по соседству. Информация о появлении хищника неподалеку от одного края косяка рыбы, например, быстро распространяется на другой его край. Заимствуя эти принципы локального взаимодействия, разработчики алгоритмов могут использовать огромные «стаи» исполнительных устройств, объединенных в информационную сеть, для исследования окружающей среды. Их быстрое, «роевое» взаимодействие позволяет им узнавать об открытиях, сделанных другими участниками «роя» в поисках оптимального окружения.

Самый известный природный алгоритм – эволюция. В своей простейшей форме эволюция объединяет признаки родителей, чтобы производить детей. Дети, которые лучше подготовлены к выживанию и размножению в своем окружении, в следующем поколении передадут свои признаки бóльшему числу потомков. Иногда между поколениями происходят мутации, что привносит в популяцию новые признаки, которые могут быть лучше или хуже уже имеющихся. Для создания биоразнообразия, способного решить некоторые из самых сложных проблем планеты, достаточно исполнять всего лишь три простые процедуры – отбирать, комбинировать и мутировать.

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