Page 202 - Bkhargava_-_Grokaem_algoritmy

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

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

КОЛИЧЕ.СЛО
ГОРО.П.О&
1 МАР О1 РУТ -----------...
----- ~ ..!lЛЯ КАUОГО НАЧАЛА" 2 МАРШРУТА
2 __., 2... НАЧАЛЬНЬIУ. ГОРО.П.А * :1. MAPlllPYТ ~
~
~ ~ НАЧАЛЬНЬIУ. ГOPO.ll.A * ';РОIРУП::: __,6 MAPOIPYTO&
3
4 ~ д, НАЧАЛЬНЬIУ. ГOPO.ll.A * ~ 24 МАРШРУТА

5 - 5 НАЧАЛЬНЬ\)1. ГОРО.П..0&* 2."'\- MAPDIPYТA $ 120 MAPDIPYТO&

Сколько возможных маршрутов существует для шести городов? 720, гово­
рите? Да, вы правы. 5040 для 7 городов, 40 320 для 8 городов.
Такая зависимость называется факториалъной (помните, что об этом го­
ворилось в главе З?) Итак, 5! = 120. Допустим, есть 10 городов. Сколько
существует возможных маршрутов? 10! = 3 628 800. Уже для 10 городов
приходится вычислять более 3 мwи~ионов возможных маршрутов. Как ви­
дите, количество возможных маршрутов стремительно растет! Вот почему
невозможно вычислить «правильное~ решение задачи о коммивояжере при
очень большом количестве городов.
У задачи о коммивояжере и задаче покрытия множества есть кое-что общее:
вы вычисляете каждое возможное решение и выбираете кратчайшее/мини­
мальное. Обе эти задачи являются NР-полными.

www.trk.kg