Представьте себе, что вы планируете путешествовать по миру и посетить десять городов. Ваша собственная версия проблемы коммивояжера: вы улетаете и прилетаете в Сан-Франциско и планируете побывать в Сиэтле, Лос-Анджелесе, Нью-Йорке, Буэнос-Айресе, Лондоне, Амстердаме, Копенгагене, Стамбуле, Дели и Киото. Вас не слишком волнует общая протяженность маршрута, но вы, вероятно, стремитесь снизить расходы на поездку. Первое, что стоит здесь отметить: хотя десять городов – это не так уж и много, но количество возможных вариантов маршрута – это 10! (10 факториал) – более 3,5 млн. Иными словами, у вас нет никакой практической возможности проверить каждую комбинацию и выбрать самую низкую цену. Придется получше пораскинуть мозгами.
В качестве первой попытки построить маршрут вы можете рассмотреть самый дешевый рейс из Сан-Франциско (скажем, в Сиэтл), а затем найти самый дешевый рейс оттуда в любой из оставшихся городов (пусть это будет Лос-Анджелес), потом самый дешевый оттуда (например, в Нью-Йорк) и т. д., пока вы не дойдете до десятого города, откуда вам нужно будет лететь обратно в Сан-Франциско. Это пример так называемого жадного алгоритма, который можно еще назвать близоруким: на каждом этапе пути он близоруко выбирает лучший вариант из тех, что под рукой. В теории планирования, которую мы рассмотрели в главе 5, жадный алгоритм – например, выполнение самой простой и занимающей меньше всего времени работы из доступных, не заглядывая далеко вперед, – порой может стать именно тем, что требуется для решения проблемы. В этом случае решение проблемы коммивояжера, которое может предложить жадный алгоритм, не самое плохое, но далекое от лучшего из возможных.
После того как вы построили базовый маршрут, вам стоит проверить возможные альтернативы, меняя последовательность городов, и посмотреть, получается ли лучше. Например, если мы решили сперва лететь в Сиэтл, а потом в Лос-Анджелес, можно попробовать поменять их местами: сначала Лос-Анджелес, затем Сиэтл. Для любого заданного маршрута мы, таким образом, можем переставить местами два города 11 раз. Скажем, мы перепробуем все варианты и выберем тот, который позволит нам максимально сэкономить. С этого момента у нас есть новый построенный маршрут, с которым мы будем работать дальше, и мы можем снова заняться перестановкой, чтобы извлечь какие-то дополнительные выгоды. Этот алгоритм называется «восхождение на холм», поскольку поиск лучших и худших решений среди множества вариантов можно рассматривать как путешествие по холмистой местности с целью взобраться на самую высокую гору.