Грокаем а Иллюстрированное пособие для программистов и любопытствующих

НАЧИНАЕМ НАЧИНАЕМ С САН­С МАРИНА ФРАНЦИСКО
(
9 О
6
ИЗ МАРИНА 6 САН- ИЗ САН-ФРАНЦИСКО ФРАНЦИСКО ₆ МАРИН
Логично спросить: в задаче о коммивояжере существует ли конкретный город, с которого нужно начинать? Допустим, коммивояжер живет в Сан- Франциско и должен посетить еще четыре города. Сан-Франциско должен быть первым городом в маршруте.
Однако в каких-то ситуациях начальный город не задан. Допустим, вы ра­ботаете в курьерской службе FedEx и должны доставить пакет в пределах города. Пакет перевозится из Чикаго в один из 50 филиалов FedEx. Затем
пакет будет перегружен в машину, которая разъезжает по разным местам и доставляет пакеты. В какой филиал отгрузить пакет? На этот раз началь­ная точка неизвестна, и в задаче о коммивояжере вам придется вычислить как оптимальный путь, так и начальную точку.
Время выполнения обеих версий одинаково. Однако отсутствие определен­ного начального города упрощает пример, поэтому я выберу эту версию.
Два города = два возможных маршрута.
СКОЛЬКО МАРШРУТОВ?
На первый взгляд может показаться, что это один маршрут. Разве расстояние СФ>Марин не совпадает с расстоянием Марин>СФ? Не всегда. В некоторых городах (в том числе и в Сан-Франциско) много улиц с односторонним движением, и тогда вам не удается вернуть­ся по тому пути, по которому вы приехали. Иногда приходится про­ехать лишнюю пару миль, чтобы найти выезд на шоссе. Так что эти два маршрута не всегда совпадают.
Три города
Теперь добавим к двум городам еще один. Сколько возможных маршрутов существует в этой конфигурации?
Если начать в Беркли, вы можете посетить два города.