На этом шаге мы подведем некоторые итоги.
У задачи коммивояжера нет простого решения. По мере увеличения количества городов наивный подход быстро становится нереальным. Количество генерируемых перестановок равно факториалу от n (n!), где n - количество городов в задаче. Если бы мы добавили еще один город и их стало бы не пять, а шесть, то число оцененных маршрутов увеличилось бы в шесть раз. А при добавлении еще одного города решить задачу стало бы в семь раз сложнее. Этот подход не масштабируется!
В реальном мире наивный подход к задаче коммивояжера используется крайне редко. Большинство алгоритмов для различных вариаций этой задачи с большим количеством городов являются приближенными. Они пытаются получить решение, близкое к оптимальному. Оно может находиться в пределах небольшой заранее известной полосы, к которой принадлежит идеальное решение (например, возможно, такие решения будут менее чем на 5 % менее эффективными, чем идеальное).
Для решения задачи коммивояжера на больших наборах данных были использованы два метода, уже описанные в предыдущих шагах. Первый - динамическое программирование, которое мы применили, рассматривая задачу о рюкзаке. Второй - генетические алгоритмы, описание которых начинается с 63 шага. Было опубликовано множество журнальных статей, в которых генетические алгоритмы называют почти оптимальным решением задачи коммивояжера с большим количеством городов.
На следующем шаге мы рассмотрим мнемонику для телефонных номеров.
