48 столиц штатов за 8 1/2 дней
Олсон установил ряд предпосылок, которые определят его более поздние расчеты. Во-первых, целью было не посещение городов, а как можно больше столиц штатов . На втором месте, ездил бы только на машине , что исключает Аляску из маршрута из-за ее удаленности и Гавайи из-за необходимости летать на самолете, что ограничивает маршрут 48 смежными штатами. Третий и последний, Маршруты, которые требуют прохождения через другие страны, будут исключены чтобы избежать паспортного и пограничного контроля, которые замедляют любое путешествие, объясняет Рэндал С. Олсон на своем веб-сайте.
Учитывая это, исследователь использовал комбинацию генетических алгоритмов, Google Maps и многоцелевой оптимизации Парето , или, что то же самое, обнаружил, что совершенство в путешествии по Соединенным Штатам предполагает посетить 48 столиц штатов, проехав 21 420 км за 8 с половиной дней . Если нет движения, конечно. Кроме того, было установлено, что поездку можно начать из любой точки маршрута без изменения конечного результата.
Как это было? Имея в руках список столиц, Олсон должен был установить фактическое расстояние по дороге, а не по прямой, между этими зданиями. Для этого он обратился к Google Maps API, который рассчитал расстояния по 2256 возможным маршрутам.
После расчета маршрутов следующим делом было упорядочить их так, чтобы их комбинация приводила к наименьшему возможному количеству пройденных километров. Генетический алгоритм дал ответ. Его интерес заключается в том, что вместо того, чтобы искать все возможные варианты, он предлагает случайные решения, всегда пробуя что-то новое и сохраняя лучшие предложения, пока не сможет найти лучшее.
Все это в сочетании с применение многокритериальной оптимизации по Парето , что позволяет оптимизировать несколько критериев одновременно. В данном случае под рукой это позволит максимально увеличить количество штатов для посещения и свести к минимуму время, необходимое для этого.