Page 199 - Bkhargava_-_Grokaem_algoritmy

198 Глава 8. Жадные алгоритмы

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

Два города = два возможных маршрута.

Три города

Теперь добавим к двум городам еще один. Сколько возможных маршрутов
существует в этой конфигурации?

Если начать в Беркли, вы можете посетить два города.

НАЧИНАЕМ
& БЕ.РКЛИ:
БЕРКЛИ

САН-ФРАНЦИСКО САН-ФРАНЦИСКО

www.trk.kg