Читать «Золотой билет. P, NP и границы возможного» онлайн - страница 3

Неважно, каким образом вы будете искать билет: вам, как и мистеру Солту, понадобится много времени и денег – или удача, когда и того, и другого дефицит. Возможно, однажды какой-нибудь умный человек изобретет недорогой прибор для быстрого поиска билетов. А возможно, и нет.

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

Где у нас самый большой массив данных? В интернете, наверно? Сложите вместе все видео– и аудиофайлы, электронные письма и вообще все, что там есть, – и получите около 1000000000000000000 байт информации, плюс-минус два нуля. А один байт – это примерно то же, что набранный на клавиатуре символ. Чудовищное число; однако не стоит забывать, что современные компьютеры очень, очень быстрые. Средний ноутбук способен выполнить триллион операций в секунду, а значит, весь интернет он теоретически пересмотрел бы за четыре месяца – если бы, конечно, кому-то удалось загрузить все это ему в память. Компания Google с ее сотнями тысяч мощнейших компьютеров имеет возможность прочесывать интернет непрерывно.

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

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

Рис. 1.1. Задача коммивояжера

Однако транспортный отдел попросил ее подумать еще и постараться уложиться в 17000 километров. Мэри написала программу, которая в поисках самого короткого маршрута перебирала все возможные перестановки из сорока восьми городов. Прошла неделя, а программа все работала. Тогда Мэри решила кое-что прикинуть. Первый город можно было выбрать сорока восемью способами. Второй – сорока семью. Третий – сорока шестью, и так далее. Итого потенциальных маршрутов набралось 48 × 47 × 46 × … × 2 × 1. Для записи этого числа требуется 62 цифры. Вот оно: 12413915592536072670862289047373375038521486354677760000000000.