Читать книгу Золотой билет. P, NP и границы возможного - Лэнс Фортноу - Страница 7

Иногда найти билет все же удается. Предположим, мне нужно поехать из Чикаго в Нью-Йорк на машине. Не долго думая, я забиваю адрес в навигатор, который уже через минуту-другую показывает оптимальный маршрут, и жму на газ. Подробная карта США со всеми городами и улицами занимает миллионы байт; возможные маршруты исчисляются гораздо более крупными цифрами. Сколько маршрутов можно проложить из Чикаго в Нью-Йорк? Грубейший подсчет даст нам свыше вигинтиллиона (единица и 63 нуля) вариантов, и запрет движения по встречке на односторонних улицах мало что изменит. У навигатора просто нет времени на такое количество проверок; как же он умудряется найти самый быстрый маршрут?

На самом деле маршруты обладают одной интересной особенностью. Добавим в программу промежуточный пункт назначения – скажем, Питтсбург. Кратчайший маршрут из Чикаго в Нью-Йорк через Питтсбург – это сумма кратчайших маршрутов из Чикаго в Питтсбург и из Питтсбурга в Нью-Йорк. Без заезда в Питтсбург до Нью-Йорка можно добраться и быстрее, однако при наличии промежуточной точки наилучшим решением будет склеить два кратчайших маршрута.

Именно так и сужают круг поиска навигационные программы. Десять тысяч или даже сто тысяч вариантов – это уже не вигинтиллион; современный процессор проверит их без труда.

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