Книга: Золотой билет
В поисках билета
В поисках билета
Иногда найти билет все же удается. Предположим, мне нужно поехать из Чикаго в Нью-Йорк на машине. Не долго думая, я забиваю адрес в навигатор, который уже через минуту-другую показывает оптимальный маршрут, и жму на газ. Подробная карта США со всеми городами и улицами занимает миллионы байт; возможные маршруты исчисляются гораздо более крупными цифрами. Сколько маршрутов можно проложить из Чикаго в Нью-Йорк? Грубейший подсчет даст нам свыше вигинтиллиона (единица и 63 нуля) вариантов, и запрет движения по встречке на односторонних улицах мало что изменит. У навигатора просто нет времени на такое количество проверок; как же он умудряется найти самый быстрый маршрут?
На самом деле маршруты обладают одной интересной особенностью. Добавим в программу промежуточный пункт назначения – скажем, Питтсбург. Кратчайший маршрут из Чикаго в Нью-Йорк через Питтсбург – это сумма кратчайших маршрутов из Чикаго в Питтсбург и из Питтсбурга в Нью-Йорк. Без заезда в Питтсбург до Нью-Йорка можно добраться и быстрее, однако при наличии промежуточной точки наилучшим решением будет склеить два кратчайших маршрута.
Именно так и сужают круг поиска навигационные программы. Десять тысяч или даже сто тысяч вариантов – это уже не вигинтиллион; современный процессор проверит их без труда.
Поиск кратчайшего пути не охватывает все аспекты проблемы равенства P и NP. Задача коммивояжера доказывает, что при наличии огромного числа вариантов совсем не обязательно перебирать их все; главный вопрос, однако, заключается в том, всегда ли можно обойтись без такого перебора.
- Раздел VI Управление глобальной инфраструктурой Сети: в поисках оптимальной модели
- 10.7. В поисках аксиом
- Глава 8 В поисках квантовой теории гравитации
- Получение пользователем билета TGT на билеты
- Получение пользователем билета на доступ к серверу
- В поисках дара к бизнесу
- В поисках клики
- В поисках правильной утки
- Два авиабилета по цене одного
- Решения в поисках проблем
- HP Labs в поисках новых бизнес-решений
- В поисках мотивации: четыре ключевых вопроса