Page 39 - Bkhargava_-_Grokaem_algoritmy

38 Глава 1. Знакомство с алгоритмами

Коммивояжер хочет побывать в каждом из 5 городов так, чтобы при этом
проехать минимальное общее расстояние. Одно из возможных решений:
нужно перебрать все возможные комбинации порядка объезда городов.

120 13'3

миль мили

Все расстояния суммируются, после чего выбирается путь с кратчайшим
расстоянием. Для 5 городов можно создать 120 перестановок, поэтому реше­
ние задачи для 5 городов потребует 120 операций. Для 6 городов количество
операций увеличивается до 720 (существуют 720 возможных перестановок).
А для 7 городов потребуется уже 5040 операций!

ГОРОД~ ОПЕ.РЩИИ

15

Количество операций стремительно растет

В общем случае для вычисления резу ль тата при п элементах потребуется
п! (п-факториал) операций. А значит, время выполнения составит О(п!)
(такое время называется факторuальным). При любом сколько-нибудь
серьезном размере списка количество операций будет просто огромным.
Скажем, если вы попытаетесь решить задачу для 100+ городов, сделать это
вовремя не удастся - Солнце погаснет раньше.

www.trk.kg