Page 198 - Bkhargava_-_Grokaem_algoritmy

NР-полные задачи 197

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

\) или 'l ·~д.
или

l'S'3
120 мили
миль

Сколько маршрутов необходимо вычислить для пяти городов?

Задача о коммивояжере - шаг за шагом

Начнем с малого. Допустим, городов всего два. Выбирать приходится всего
из двух маршрутов.

НАЧИНАЕМ НАЧИНАЕМ С САН-
с МАРИНА ФРАНЦИСКО

llJ МАРИНА 6 САН- llJ САН-ФРАНЦИСКО
ФРАНЦИСКО 6 МАРИН

Логично спросить: в задаче о коммивояжере существует ли конкретный
город, с которого нужно начинать? Допустим, коммивояжер живет в Сан­
Франциско и должен посетить еще четыре города. Сан-Франциско должен
быть первым городом в маршруте.
Однако в каких-то ситуациях начальный город не задан. Допустим, вы ра­
ботаете в курьерской службе FedEx и должны доставить пакет в пределах
города. Пакет перевозится из Чикаго в один из 50 филиалов FedEx. Затем

www.trk.kg