Текст книги "Это база: Зачем нужна математика в повседневной жизни"

3
Пусть голубь ведет автобус

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

БРЕТТ ГИБСОН, МЭТТЬЮ УИЛКИНСОН И ДЕББИ КЕЛЛИ.

Animal cognition

Мо Виллемс рисовал забавные картинки с трехлетнего возраста. Опасаясь, что взрослые могут хвалить его не от чистого сердца, он начал писать смешные истории. Ему казалось, что фальшивый смех легче распознать. В 1993 году он присоединился к команде сценаристов и мультипликаторов классической «Улицы Сезам», что принесло ему за 10 лет шесть премий «Эмми». Главным героем его детского мультсериала «Баран в большом городе» стал баран по имени Баран, чья идиллическая жизнь на ферме рушится, когда тайная военная организация начинает гоняться за ним и ловить для создания лучевой пушки на бараньей силе. Первым опытом Виллемса в жанре детской книги стала книжка «Не позволяйте голубю вести автобус!», продолжавшая тему животных. Мультфильм по этой книге принес автору медаль Карнеги, а сама книга – премию Калдекотта, которую получают те, кто попадает в шорт-лист претендентов на медаль Калдекотта. Главный герой книги – голубь – использует все возможное и невозможное, пытаясь убедить читателя, что ему можно доверить управление автобусом, когда обычному водителю внезапно приходится покинуть транспортное средство.

В 2012 году книга Виллемса получила неожиданное научное продолжение – солидную статью в уважаемом журнале Animal Cognition, авторами которой стали заслуживающие доверия исследователи Бретт Гибсон, Мэттью Уилкинсон и Дебби Келли. Они экспериментально доказали, что голуби способны находить решения, близкие к оптимальным, для простых случаев известной математической диковинки – задачи коммивояжера. Их статья называлась «Позвольте голубю вести автобус: голуби способны планировать маршруты в помещении»{19}19
  B. Gibson, M. Wilkinson and D. Kelly. «Let the pigeon drive the bus: pigeons can plan future routes in a room», Animal Cognition 15 (2012) 379–391.


[Закрыть].

И пусть никто не говорит, что у ученых нет чувства юмора. Или что остроумные заголовки не помогают добиться популярности.

Задача коммивояжера – не просто любопытная диковинка. Это хороший пример целого класса задач, имеющих громадное практическое значение и известных как задачи комбинаторной оптимизации. У математиков есть привычка формулировать глубокие и значительные вопросы тривиальным на первый взгляд языком. Американские конгрессмены осудили напрасное расходование бюджетных денег на теорию узлов, не понимая, что эта область математики принципиально важна для понимания топологии малых размерностей, которая используется в теории ДНК и квантовой теории. Основные методы топологии включают в себя теорему о причесывании ежика и теорему о бутерброде, так что, я полагаю, мы сами на это напросились, но дело не только в нас. Я не осуждаю тех, кто чего-то не знает, – с каждым случается, – но почему бы этим людям просто не спросить?{20}20
  Мой любимый пример – это политик, который поднял грандиозный шум по поводу напрасной траты денег на то, что он назвал «теорией лжи» (Lie theory). Слово lie он произносил «лай», то есть «ложь, неправда», и считал, что теория говорит именно об этом. На самом деле все не так. Софус Ли (Sophus Lie) был норвежским математиком, работа которого по непрерывным группам симметрий (группам Ли) и связанным с ними алгебрам имеет фундаментальное значение для обширных областей математики и еще большее – для физики. Политику указали на его заблуждение… но он продолжил выступать ровно так же, как прежде.


[Закрыть]

Как бы то ни было, та показательная чепуха, которая вдохновила меня на эту главу, берет свое начало в одной полезной книге для – как вы, наверное, уже догадались – коммивояжеров. Тех, что обходили дома и предлагали свой товар. Я еще помню их, даже если вы не помните. Они часто продавали пылесосы. Как любые разумные деловые люди, немецкие коммивояжеры в 1832 году (а в те времена все они, конечно, были мужчинами) очень трепетно относились к эффективности использования своего времени и снижению расходов. К счастью, помощь всегда была под рукой в виде руководства: «Коммивояжер. Каким ему следует быть и что ему следует делать, чтобы получать заказы и быть уверенным в успехе своего дела. Советы старого коммивояжера» (Der Handlungsreisende – wie er sein soll und was er zu thun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiss zu sein – von einem alten Commis-Voyageur). Этот пожилой странствующий торговец указывал, что:

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

Руководство не предлагало математических принципов решения этой задачи, а приводило примеры пяти предположительно оптимальных маршрутов по Германии (один из них проходил через территорию Швейцарии). Большинство маршрутов содержали подциклы, предусматривавшие посещение одних и тех же мест дважды, что вполне естественно, если вы останавливаетесь на ночь в гостинице, а днем объезжаете окрестности. Но в одном из маршрутов не было повторных визитов. Современное решение этой задачи показывает, что предложенный руководством ответ достаточно хорош, как видно на рисунке.

Маршрут (1285 км) по 45 немецким городам из руководства 1832 года, показанный сплошными (толстыми и тонкими) линиями. Сплошными толстыми и пунктирными линиями показан кратчайший маршрут (1248 км), найденный современными методами

Задача коммивояжера – а именно такое название она получила – стала первым фундаментальным примером математической области, известной сегодня как комбинаторная оптимизация, что означает «нахождение лучшего варианта среди множества возможностей, слишком большого, чтобы проверять их последовательно». Забавно, но название «задача коммивояжера» не использовалось явно ни в одной публикации на эту тему до 1984 года[4]4
  Возможно, это справедливо для англоязычных публикаций, но на русском языке популярная книга В. Мудрова «Задача коммивояжера» вышла еще в 1969 году. – Прим. науч. ред.


[Закрыть], хотя в неформальных дискуссиях математиков оно вовсю фигурировало и до этого.

Несмотря на свое приземленное практическое происхождение, задача коммивояжера завела математическое сообщество в реальные глубины, вплоть до одной из «задач тысячелетия» «P ≠ NP?», приз за решение которой размером $1 млн до сих пор ожидает своего получателя. В задаче спрашивается в строгой математической форме: если имеется задача, предполагаемый ответ на которую – догадка, если угодно, – может быть эффективно проверен, то может ли этот ответ быть эффективно найден во всех случаях? Большинство математиков и компьютерщиков считают, что ответ должен быть «нет»: безусловно, проверка любой конкретной догадки может быть проведена намного быстрее, чем поиск корректного ответа. В конце концов, если кто-то показывает вам собранный пазл из 500 элементов, то быстрого взгляда, как правило, хватает, чтобы понять, все ли правильно собрано, но собрать весь пазл с самого начала – совершенно другое дело. К несчастью, пазлы не дают нам ответа: это всего лишь удобная метафора, строго говоря, они не имеют отношения к вопросу. Так что сейчас никто не может ни доказать, ни опровергнуть предположение о том, что P отличается от NP, – именно поэтому решение вопроса принесет вам круглую сумму $1 млн{21}21
  По техническим причинам мое замечание о пазлах не решает призовую задачу. Если бы решало, я был бы первым.


[Закрыть]. Я вернусь к задаче P ≠ NP позже, а сначала рассмотрим первые успехи в решении задачи коммивояжера.

* * *

Время коммивояжеров давно прошло. В век интернета компании редко продают свой товар, отправляя путешествовать по городам и весям человека с чемоданом образцов. Они выставляют свои товары в Сети. Но, как обычно (все та же непостижимая эффективность), задача коммивояжера не устарела из-за этих изменений в культуре. Онлайн-продажи растут экспоненциально, потребность в эффективных способах определения маршрутов и графиков приобретает все большее значение для доставки всего, от посылок до пиццы и заказов в супермаркетах. Задачу коммивояжера можно было бы, наверное, переименовать в задачу курьера-доставщика: какой маршрут будет наилучшим для фургончика, доставляющего заказы?

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

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

Среди других применений можно назвать и эффективное прокладывание авиамаршрутов, и разработку и производство компьютерных микрочипов и печатных плат. Приближенные решения задачи коммивояжера используются для нахождения эффективных маршрутов доставки еды нуждающимся (программа Meals on Wheels) и оптимизации доставки крови в больницы. Один из вариантов задачи коммивояжера засветился даже в программе «Звездных войн» или, как ее правильнее называть, в гипотетической Стратегической оборонной инициативе президента США Рональда Рейгана, где мощный лазер, находящийся на околоземной орбите, должен был наводиться на ряд приближающихся ядерных ракет.

* * *

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

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

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

Одна из причин, по которым метод ближайшего соседа не работает. Начните с точки A и всегда переходите к ближайшей из точек, которые вы еще не посетили. Маршрут слева будет выглядеть как ABCDE. Однако маршрут справа – ACBDE – короче

Менгер шесть месяцев в 1930 и 1931 годах читал в Гарвардском университете лекции, часть из которых прослушал великий тополог Хасслер Уитни. Годом позже Уитни выступил с лекцией, где высказался о том, как следует подходить к поиску кратчайшего пути по всем 48 (на тот момент) штатам Америки. Некоторое время в математических кругах эту проблему называли «задачей 48 штатов», но потом кто-то придумал более изящное название «задача коммивояжера». В печати оно впервые было упомянуто в 1949 году в докладе Джулии Робинсон.

Менгер продолжал работать над задачей коммивояжера и родственными вопросами. В 1940 году Ласло Фейеш Тот заинтересовался, по существу, этой же задачей: нахождением кратчайшего пути через n точек единичного квадрата. В 1951 году Самюэл Верблунски доказал, что ответ составляет меньше чем 2 +√2 · 8n. Позже математики доказывали, что минимальная длина пути через n точек в фиксированной области не превышает определенной константы, умноженной на квадратный корень из n, причем величина константы с каждым разом все уменьшалась.

В конце 1940-х годов одной из ведущих организаций, занимавшихся исследованием операций, была RAND Corporation в Санта-Монике (штат Калифорния). Исследователи RAND немало сил посвятили решению родственной задачи о перевозках, и Джордж Данциг с Тьяллингом Купмансом высказали предположение, что их работа над тем, что сейчас называется линейным программированием, может иметь значение и для решения задачи коммивояжера. Линейное программирование – эффективный и практичный метод решения многих задач комбинаторной оптимизации. Это метод максимизации линейной комбинации переменных с ограничениями в виде неравенств, утверждающих, что другие их линейные комбинации должны быть положительными или отрицательными. Данциг придумал первый практический алгоритм – симплексный метод, широко используемый до сих пор. Неравенства определяют многомерный выпуклый многогранник, а алгоритм перемещает точку вдоль ребер этого многогранника до тех пор, пока величина, которую мы хотим максимизировать, увеличивается.

Первого по-настоящему значимого успеха в решении задачи коммивояжера добились в 1954 году исследователи RAND Данциг, Делберт Фалкерсон и Селмер Джонсон при помощи метода линейного программирования Данцига. Они адаптировали метод к решению именно этой задачи и предложили систематические новые методы, в частности использование «секущих плоскостей». В результате был найден нижний предел длины оптимального маршрута. Если вам удается находить маршрут лишь ненамного длиннее, то вы на правильном пути и внутреннее чутье не обманывает вас. Данциг, Фалкерсон и Джонсон воспользовались этими идеями, чтобы получить первое решение задачи коммивояжера для разумного числа городов, а именно найти кратчайший маршрут через 49 городов: по одному в каждом из 48 штатов США плюс столичный Вашингтон. Это, похоже, та самая задача, которую упоминал Уилкинсон в 1930-е годы, и определенно та самая, о которой писала Джулия Робинсон в 1949 году.

* * *

В 1956 году пионер исследования операций Меррилл Флуд заявил, что задача коммивояжера сложна. Возникает ключевой вопрос: насколько сложна? Чтобы ответить, мы должны вернуться к P и NP – показателям вычислительной сложности ценой миллион долларов. Похоже, что Флуд был прав, причем очень сильно.

Математики всегда внимательно относились к практичности методов решения задач, хотя, когда дело стопорится, все сходятся во мнении, что любой метод лучше, чем ничего. С чисто теоретической точки зрения возможность просто доказать, что решение задачи существует, может стать серьезным шагом вперед. Почему? Потому что, если нет уверенности в существовании решения, можно напрасно потерять много времени на его поиски.

Мой любимый пример – то, что я называю Шатром Матушки Мушки. Малышка Мушка парит в футе (в метре, в километре – на любой ненулевой высоте) над полом. Матушка Мушка хочет сшить шатер с основанием на полу, чтобы он прикрывал Малышку, и использовать при этом как можно меньше материи. Какой шатер имеет минимальную площадь? Если мы представим Малышку Мушку в виде точки, то ответ будет «такого шатра не существует». Сшить можно конический шатер любой ненулевой площади, если площадь нулевая, то это линия, а не шатер. Для любого заданного шатра существует другой, вдвое меньшей площади, который тоже выполняет свою задачу. Поэтому наименьшей площади не существует.

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

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

Главный вопрос звучит так: насколько быстро возрастает время вычислений (измеренное как число вычислительных шагов) в любом методе вычисления ответа в сравнении с объемом данных, необходимых для постановки задачи? То есть если для описания задачи необходимо n двоичных знаков, то как будет зависеть от n время вычислений? Для практичных алгоритмов время расчета обычно растет как степень n, скажем, n² или n³. Говорят, что эти алгоритмы выполняются за полиномиальное время. Символически их обозначают как класс P. Время выполнения непрактичных алгоритмов растет много быстрее, часто экспоненциально, как 2ⁿ или 10ⁿ. Алгоритм «просчитать все маршруты» для задачи коммивояжера примерно таков – он выполняется за факториальное время n!, которое растет быстрее любой экспоненты. В промежутке находится серая зона, где время выполнения больше любого полинома, но меньше экспоненты. Иногда такие алгоритмы практичны, иногда нет. В целях настоящей книги мы можем принять очень строгий взгляд и отправить их все в корзину с надписью «непрактичные».

Это не то же самое, что NP.

Эта аббревиатура обозначает куда более тонкое понятие: недетерминированное полиномиальное время. Это время выполнения алгоритма, который может решить, является ли каждое конкретное предложенное решение верным. Вспомним, что число называется простым, если не имеет других делителей, кроме 1 и самого себя, так что числа 2, 3, 5, 7, 11, 13 и т. д. являются простыми. В противном случае число называется составным. Так что 26 – составное число, поскольку равно 2 × 13. Числа 2 и 13 – простые сомножители числа 26. Предположим, что вы хотите найти простой делитель числа, состоящего из 200 десятичных знаков. Вы тратите год на безрезультатный поиск такого числа, а затем в отчаянии обращаетесь за советом к Дельфийскому оракулу. Оракул называет в качестве ответа конкретное большое число. Вы понятия не имеете, откуда оно взялось (в конце концов, оракул обладает волшебным даром предсказания), но вы можете сесть и подсчитать, действительно ли число, названное оракулом, разделит нацело то очень большое число, о котором шла речь. Такой расчет намного, намного проще, чем собственно поиск простого делителя.

Предположим, что всякий раз, когда оракул предлагает ответ, вы можете проверить его при помощи алгоритма с полиномиальным временем выполнения (P). Тогда сама задача относится к классу NP – недетерминированному полиномиальному. Задача оракула намного сложнее вашей, но вы всегда можете решить, верный ли ответ он вам дал.

Очевидно, что проверка предложенного ответа должна быть намного проще его отыскания. Проверить, спрятано ли сокровище в месте, отмеченном крестиком на карте, намного проще, чем выяснить, где этот крестик должен стоять. Или возьмем математический пример: почти все верят, что нахождение простых делителей намного сложнее, чем проверка, является ли делителем данное простое число. В пользу этого свидетельствует, в частности, то серьезное обстоятельство, что быстрые алгоритмы проверки любого предложенного делителя известны, а их поиска – нет. Если P = NP, то для любой задачи, имеющей быстро проверяемый ответ, найти ответ тоже быстро. Это звучит слишком хорошо, чтобы быть правдой, и опыт математиков в решении задач говорит прямо противоположное. Поэтому почти все убеждены, что P ≠ NP.

Однако все попытки доказать это – или опровергнуть – зашли в тупик. Вы можете доказать, что задача принадлежит к классу NP, записав детальный алгоритм и подсчитав время его выполнения, но для доказательства того, что задача не относится к классу P, вам придется рассмотреть все возможные алгоритмы ее решения и показать, что ни один из них не относится к классу P. Как это сделать? Никто не знает.

Из этих попыток проистекает тот любопытный факт, что в одну и ту же категорию попадает огромное число задач-кандидатов. Все эти задачи относятся к NP. Более того, если для какой-то из них можно доказать, что она не принадлежит P, то и все остальные не принадлежат P. Они живут или умирают вместе. Подобные задачи называют NP-полными. Связанную с ними более крупную категорию называют NP-трудными задачами: она состоит из алгоритмов, способных эмулировать решение любой NP-задачи за полиномиальное время. Если выяснится, что данный алгоритм выполняется за полиномиальное время, это автоматически докажет, что то же верно для любой NP-задачи. В 1979 году Майкл Гэри и Дэвид Джонсон доказали, что задача коммивояжера относится к классу NP-трудных{22}22
  M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco (1979).


[Закрыть]. Если P ≠ NP, то любой алгоритм для ее решения потребует время выполнения, превышающее полиномиальное.

Флуд был прав.

* * *

Это, впрочем, не повод опускать руки, потому что существует по крайней мере два потенциально возможных пути вперед.

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

В 1980 году рекорд составлял 318 городов; к 1987 году их уже было 2392. К 1994 году рекорд увеличился до 7397 городов и ответ потребовал около трех лет вычислительного времени сети очень мощных компьютеров. В 2001 году точное решение для 15 112 немецких городов было получено с использованием сети из 110 процессоров. На обычном настольном компьютере этот расчет занял бы более 20 лет. В 2004 году задача коммивояжера была решена для маршрута по 24 978 городам Швеции. В 2005 году группа Concorde TSP Solver решила задачу коммивояжера для маршрута по 33 810 точкам на печатной плате. Рекорды не единственный мотив для таких исследований: методы, использованные в рекордных достижениях, работают необычайно быстро при решении менее масштабных задач. Задачу при числе городов не более сотни обычно можно решить за несколько минут, а не более тысячи – за несколько часов на типовом настольном компьютере.

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

* * *

Один из методов поиска хороших, но не оптимальных решений задачи коммивояжера родился из таких глупых препятствий. Несколько десятилетий на переломе XIX и XX веков математика находилась в состоянии перехода. Царивший ранее авантюризм почти исчерпал себя, а игнорирование таких фундаментальных вопросов, как «о чем, собственно, идет речь?» и «действительно ли все так очевидно, как всем кажется?», сеяло смятение и растерянность там, где требовались ясность и понимание. Беспокойство по поводу таких продвинутых областей, как дифференциальное и интегральное исчисление, где математики легко и непринужденно разбрасывались бесконечными процессами, постепенно переходило с изотерических вещей на повседневные. Вместо сомнений в интегралах сложных математических функций вроде комплексного логарифма математики стали задаваться вопросом о том, что такое функция. Вместо того чтобы определять непрерывную кривую как кривую, которую можно «свободно нарисовать от руки», они стремились к большей строгости и обнаруживали ее отсутствие. Даже природа такого фундаментального и очевидного объекта, как число, вдруг оказалась весьма туманной. И речь здесь не только о новых конструктах, таких как комплексные числа: речь шла о добрых старых натуральных числах 1, 2, 3. Традиционная математика продолжала идти вперед, опираясь на предположение, что вопросы такого рода со временем непременно разъяснятся и все будет хорошо. Логический статус основ можно было без опаски оставить занудам и педантам. И все же… постепенно формировалось мнение о том, что такой неосмотрительный подход к дисциплине долго не продержится.

Дело по-настоящему осложнилось, когда прежние сумасбродные методы стали давать противоречащие друг другу ответы. Теоремы, издавна считавшиеся правильными, оказывались неверными в особых обстоятельствах. Интеграл, вычисленный двумя способами, давал разные ответы. Последовательности, сходившиеся, как считалось, при всех значениях переменной, иногда расходились. Конечно, все было не настолько плохо, как если бы вдруг обнаружилось, что 2 + 2 иногда равно 5, но все эти странности заставили некоторых ученых задуматься о том, что такое на самом деле 2 и 5, не говоря уже о знаках + и =.

Так что, не прислушиваясь к скептическому большинству – или прислушиваясь не слишком сильно, чтобы изменить свое мнение, – немногочисленные педанты разворошили математическое здание сверху донизу в поисках прочной основы, а затем начали перестраивать его с самого фундамента.

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

Одно из наиболее фундаментальных свойств кривых, настолько очевидное, что никто даже не пытался в нем усомниться, состоит в том, что эти кривые тонкие. Как писал Евклид в «Началах», «линия – это то, что не имеет толщины». Площадь линии – просто линии, а не того, что она окружает, – очевидно, равна нулю. Но в 1890 году Джузеппе Пеано предложил способ построения непрерывной кривой, которая полностью заполняет внутренность квадрата{23}23
  G. Peano. «Sur une courbe qui remplit toute une aire plane», Mathematische Annalen 36 (1890) 157–160.


[Закрыть]. Она не просто блуждает внутри квадрата, создавая сложные каракули и приближаясь к каждой точке: она проходит через каждую точку квадрата. Кривая Пеано «не имеет толщины» в том смысле, что вы проводите ее карандашом, кончик которого представляет собой единственную геометрическую точку, но эта линия блуждает по квадрату, раз за разом посещая те области, которые ранее покинула. Пеано понял, что если заставить эту линию бесконечно извиваться, причем определенным образом, то она полностью заполнит квадрат. При этом площадь кривой будет равна площади квадрата, то есть ненулевой.

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