: все округа включают в себя примерно равное число избирателей.
• Компактность по Полсби – Попперу: все округа имеют тест Полсби – Поппера, превышающий определенное законом значение.
• Ограниченный разрыв в эффективности: более формальный параметр. Грубо говоря, если население любых двух округов не превышает некоторой фиксированной доли полного населения всех округов, то разрыв в эффективности составляет меньше 50 %.
Затем они доказывают, что никакая система нарезки избирательных округов не может во всех случаях удовлетворять этим трем критериям.
Демократия не может быть идеальной. Поразительно, что она вообще работает, если учесть, что ее цель – убедить миллионы людей, имеющих собственное мнение, согласиться по какому-то важному вопросу, затрагивающему всех. Диктаторские режимы намного проще. Один диктатор – один голос.
3Пусть голубь ведет автобус
Водителя автобуса может беспокоить, что голубь не способен безопасно вести автобус. Еще больше его может беспокоить то, что голубь не сумеет выбрать маршрут, позволяющий подобрать всех пассажиров на остановках города.
Мо Виллемс рисовал забавные картинки с трехлетнего возраста. Опасаясь, что взрослые могут хвалить его не от чистого сердца, он начал писать смешные истории. Ему казалось, что фальшивый смех легче распознать. В 1993 году он присоединился к команде сценаристов и мультипликаторов классической «Улицы Сезам», что принесло ему за 10 лет шесть премий «Эмми». Главным героем его детского мультсериала «Баран в большом городе» стал баран по имени Баран, чья идиллическая жизнь на ферме рушится, когда тайная военная организация начинает гоняться за ним и ловить для создания лучевой пушки на бараньей силе. Первым опытом Виллемса в жанре детской книги стала книжка «Не позволяйте голубю вести автобус!», продолжавшая тему животных. Мультфильм по этой книге принес автору медаль Карнеги, а сама книга – премию Калдекотта, которую получают те, кто попадает в шорт-лист претендентов на медаль Калдекотта. Главный герой книги – голубь – использует все возможное и невозможное, пытаясь убедить читателя, что ему можно доверить управление автобусом, когда обычному водителю внезапно приходится покинуть транспортное средство.
В 2012 году книга Виллемса получила неожиданное научное продолжение – солидную статью в уважаемом журнале Animal Cognition, авторами которой стали заслуживающие доверия исследователи Бретт Гибсон, Мэттью Уилкинсон и Дебби Келли. Они экспериментально доказали, что голуби способны находить решения, близкие к оптимальным, для простых случаев известной математической диковинки – задачи коммивояжера. Их статья называлась «Позвольте голубю вести автобус: голуби способны планировать маршруты в помещении»{19}.
И пусть никто не говорит, что у ученых нет чувства юмора. Или что остроумные заголовки не помогают добиться популярности.
Задача коммивояжера – не просто любопытная диковинка. Это хороший пример целого класса задач, имеющих громадное практическое значение и известных как задачи комбинаторной оптимизации. У математиков есть привычка формулировать глубокие и значительные вопросы тривиальным на первый взгляд языком. Американские конгрессмены осудили напрасное расходование бюджетных денег на теорию узлов, не понимая, что эта область математики принципиально важна для понимания топологии малых размерностей, которая используется в теории ДНК и квантовой теории. Основные методы топологии включают в себя теорему о причесывании ежика и теорему о бутерброде, так что, я полагаю, мы сами на это напросились, но дело не только в нас. Я не осуждаю тех, кто чего-то не знает, – с каждым случается, – но почему бы этим людям просто не спросить?{20}
Как бы то ни было, та показательная чепуха, которая вдохновила меня на эту главу, берет свое начало в одной полезной книге для – как вы, наверное, уже догадались – коммивояжеров. Тех, что обходили дома и предлагали свой товар. Я еще помню их, даже если вы не помните. Они часто продавали пылесосы. Как любые разумные деловые люди, немецкие коммивояжеры в 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], хотя в неформальных дискуссиях математиков оно вовсю фигурировало и до этого.
Несмотря на свое приземленное практическое происхождение, задача коммивояжера завела математическое сообщество в реальные глубины, вплоть до одной из «задач тысячелетия» «P ≠ NP?», приз за решение которой размером $1 млн до сих пор ожидает своего получателя. В задаче спрашивается в строгой математической форме: если имеется задача, предполагаемый ответ на которую – догадка, если угодно, – может быть эффективно проверен, то может ли этот ответ быть эффективно найден во всех случаях? Большинство математиков и компьютерщиков считают, что ответ должен быть «нет»: безусловно, проверка любой конкретной догадки может быть проведена намного быстрее, чем поиск корректного ответа. В конце концов, если кто-то показывает вам собранный пазл из 500 элементов, то быстрого взгляда, как правило, хватает, чтобы понять, все ли правильно собрано, но собрать весь пазл с самого начала – совершенно другое дело. К несчастью, пазлы не дают нам ответа: это всего лишь удобная метафора, строго говоря, они не имеют отношения к вопросу. Так что сейчас никто не может ни доказать, ни опровергнуть предположение о том, что P отличается от NP, – именно поэтому решение вопроса принесет вам круглую сумму $1 млн{21}. Я вернусь к задаче P ≠ NP позже, а сначала рассмотрим первые успехи в решении задачи коммивояжера.
Время коммивояжеров давно прошло. В век интернета компании редко продают свой товар, отправляя путешествовать по городам и весям человека с чемоданом образцов. Они выставляют свои товары в Сети. Но, как обычно (все та же непостижимая эффективность), задача коммивояжера не устарела из-за этих изменений в культуре. Онлайн-продажи растут экспоненциально, потребность в эффективных способах определения маршрутов и графиков приобретает все большее значение для доставки всего, от посылок до пиццы и заказов в супермаркетах. Задачу коммивояжера можно было бы, наверное, переименовать в задачу курьера-доставщика: какой маршрут будет наилучшим для фургончика, доставляющего заказы?
И здесь на сцену выходит переносимость математики. Применение задачи коммивояжера не ограничивается поездками между городами или по улицам большого города. На стене нашей гостиной висит большой квадрат из черной ткани с вышитым на нем из блесток элегантным спиральным узором, основанным на знаменитых числах Фибоначчи. Дизайнер называет этот узор «блестками Фибоначчи». Изготовлен он был при помощи машины под управлением компьютера, способной вышить все что угодно размером вплоть до покрывала на большую кровать. Игла, делающая стежки, прикреплена к стержню, который перемещает ее в продольном направлении, а сам стержень может еще двигаться в поперечном направлении. Сочетание этих двух движений позволяет переместить иглу в любую точку. По чисто практическим причинам (потеря времени, лишняя нагрузка на машину, шум) никто не хочет, чтобы игла скакала туда-сюда по всему полотну, так что суммарное пройденное ею расстояние необходимо минимизировать. Получается задача, очень похожая на задачу коммивояжера. Родословная таких машин восходит к ранней компьютерной графике и к устройству, известному как плоттер, где перо двигалось примерно так же.