Книга является наиболее полным руководством по разработке эффективных ал

Часть I. Практическая разработка алгоритмов 
сводящую к минимуму длину маршрута. Псевдокод этого алгоритма показан в листин-
ге 1.4. 
а) б) 
Рис. 1.4. 
Неудачный входной экземпляр для алгоритма ближайших пар 
(а)
и оптимальное решение 
(б)
Листинг 1.4. Оптимальный алгоритм поиска маршрута 
OptimalTSP(P) 
d = ∞ 
For каждой перестановки P
i
из общего числа перестановок n! множества 
точек P 
If (cost(P
i
) ≤ d) then d = cost(P
i
) и P
min
= P
i
Return P
min
Так как рассматриваются все возможные упорядочения, то получение самого коротко-
го маршрута гарантировано. Поскольку мы выбираем самую лучшую комбинацию, 
алгоритм правильный. В то же самое время он чрезвычайно медленный. Например, 
самый быстрый компьютер в мире не сможет в течение дня перечислить все
20! = 2 432 902 008 176 640 000 возможных перестановок 20 точек. А о реальных си-
туациях, когда количество точек печатной платы достигает тысячи, можно и не гово-
рить. Все компьютеры в мире, работая круглосуточно, не смогут даже приблизиться к 
решению этой задачи до конца существования Вселенной, а тогда решение этой зада-
чи, скорее всего, уже не будет актуальным. 
Поиском эффективного алгоритма решения этой задачи, называющейся 
задачей ком-
мивояжера
(traveling salesman problem, TSP), мы будем заниматься на протяжении 
большей части этой книги. Если же вам не терпится узнать решение уже сейчас, то вы 
можете посмотреть его в 
разделе 16.4
. 
П
ОДВЕДЕНИЕ ИТОГОВ
Алгоритмы
, которые всегда выдают правильное решение, коренным образом отличаются 
от 
эвристических алгоритмов
, которые обычно выдают достаточно хорошие, но не га-
рантированные результаты. 
1.2. Задача календарного планирования 
Теперь рассмотрим задачу календарного планирования. Представьте, что вы кинозвез-
да и вам наперебой предлагают роли в разных кинофильмах, общее количество кото-

---