Это база: Зачем нужна математика в повседневной жизни - Йэн Стюарт
Шрифт:
Интервал:
Закладка:
Для задачи коммивояжера с конечным числом городов, расположенных произвольным образом, решение определенно существует, потому что число возможных маршрутов тоже конечно. Это гарантирует, что попытки найти кратчайший маршрут не будут пустой тратой времени, но ничего не говорит о том, каким будет этот маршрут. Если вы охотитесь за спрятанными сокровищами, вам вряд ли сильно поможет сообщение о том, что это сокровище определенно где-то есть: предложение перекопать всю планету непрактично.
Ученый-компьютерщик Дональд Кнут заметил когда-то, что при вычислениях нужно нечто большее, чем доказательство существования ответа. Необходимо выяснить, сколько будет стоить его вычисление. Не в долларах и центах, а в вычислительных затратах. Область математики, которая занимается этим вопросом, называется теорией вычислительной сложности. Из нескольких простых идей она превратилась в сложный набор теорем и методов совсем недавно, однако есть одно базовое отличие, которое помогает понять, в очень упрощенной форме, разницу между решением практичным и непрактичным.
Главный вопрос звучит так: насколько быстро возрастает время вычислений (измеренное как число вычислительных шагов) в любом методе вычисления ответа в сравнении с объемом данных, необходимых для постановки задачи? То есть если для описания задачи необходимо n двоичных знаков, то как будет зависеть от n время вычислений? Для практичных алгоритмов время расчета обычно растет как степень n, скажем, n2 или n3. Говорят, что эти алгоритмы выполняются за полиномиальное время. Символически их обозначают как класс P. Время выполнения непрактичных алгоритмов растет много быстрее, часто экспоненциально, как 2n или 10n. Алгоритм «просчитать все маршруты» для задачи коммивояжера примерно таков – он выполняется за факториальное время 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}. Если P ≠ NP, то любой алгоритм для ее решения потребует время выполнения, превышающее полиномиальное.
Флуд был прав.
* * *
Это, впрочем, не повод опускать руки, потому что существует по крайней мере два потенциально возможных пути вперед.
Один, который я разберу прямо сейчас, основан на опыте решения практических задач. Если задача не относится к классу P, то решать ее в случае наихудшего сценария – дело безнадежное. Но наихудшие сценарии часто оказываются очень надуманными и нетипичными для тех примеров, с которыми мы сталкиваемся в реальном мире. Поэтому математики, занимающиеся исследованием операций, начали выяснять, с каким количеством городов они могли бы справиться в реальных задачах. И оказалось, что вариации метода линейного программирования, предложенного Данцигом, Фалкерсоном и Джонсоном, часто позволяют добиться замечательных результатов.
В 1980 году рекорд составлял 318 городов; к 1987 году их уже было 2392. К 1994 году рекорд увеличился до 7397 городов и ответ потребовал около трех лет вычислительного времени сети очень мощных компьютеров. В 2001 году точное решение для 15 112 немецких городов было получено с использованием сети из 110 процессоров. На обычном настольном компьютере этот расчет занял бы более 20 лет. В 2004 году задача коммивояжера была решена для маршрута
