Concorde TSP Solver это программа для решения задачи коммивояжера . Он был написан Дэвидом Эпплгейтом , Робертом Э. Биксби , Вашеком Хваталом и Уильямом Дж. Куком на языке ANSI C и находится в свободном доступе для академического использования.
Concorde применялся для решения задач картирования генов , [1] прогнозирования функции белков , [2] маршрутизации транспортных средств , [3] преобразования растровых изображений в непрерывные линейные рисунки, [4] планирования движения судов для сейсмических исследований, [5] и в изучение масштабных свойств задач комбинаторной оптимизации. [6]
Согласно Mulder & Wunsch (2003) , Concorde «широко считается самым быстрым из существующих в настоящее время решателей TSP для крупных проектов». В 2001 году Concorde выиграла приз в размере 5000 гульденов от CMG за решение проблемы с маршрутизацией транспортных средств, которую компания поставила в 1996 году [7].
Заметки [ править ]
- ^ Hitte et al. (2003) .
- ^ Джонсон и Лю (2006) .
- ^ Эпплгейт и др. (2002) .
- Перейти ↑ Bosch & Herman (2004) .
- ^ Гутин и др. (2005)
- ^ Олдос & Percus (2003) .
- ^ Whizzkids '96 маршрутизация транспортных средств , с вебомсайта Concorde, извлеченным 26 августа 2008 года.
Ссылки [ править ]
- Олдос, Дэвид; Перкус, Аллон Г. (2003), "Масштабирование и универсальность в непрерывной комбинаторной оптимизации длины", Proc. Natl. Акад. Sci. США , 100 (20): 11211–11215, arXiv : cond-mat / 0301035 , Bibcode : 2003PNAS..10011211A , doi : 10.1073 / pnas.1635191100 , PMC 208736 , PMID 14504403.
- Эпплгейт, Дэвид; Кук, Уильям; Дэш, Санджиб; Роэ, Андре (2002), "Решение задачи маршрутизации транспортного средства мин-макс", СООБЩАЕТ журнал по вычислениям , 14 (2): 132-143, DOI : 10,1287 / ijoc.14.2.132.118.
- Босх, Роберт; Герман, Эдрианн (2004), "Непрерывные линейные рисунки с помощью задачи коммивояжера" (PDF) , операции Research Letters , 32 (4): 302-303, DOI : 10.1016 / j.orl.2003.10.001.
- Гутин Григорий; Якубович, Гельмут; Ронен, Шуки; Зверович, Алексей (2005), "Сейсмическая проблема судна" (PDF) , Сообщения в DQM , 8 : 13–20.
- Hitte, C .; Лоренцен, Т.Д .; Guyon, R .; Kim, L .; Cadieu, E .; Паркер, HG; Quignon, P .; Лоу, Дж. К.; и другие. (2003), "Сравнение Multimap и TSP / CONCORDE для построения излучения гибридных карт", журнал Наследственность , 94 (1): 9-13, DOI : 10,1093 / jhered / esg012 , PMID 12692156.
- Джонсон, Олин; Лю Цзин (2006), "коммивояжер подход для прогнозирования функции белка", Исходный код для биологии и медицины , 1 : 3, DOI : 10,1186 / 1751-0473-1-3 , PMC 1636333 , PMID 17147783.
- Малдер, Сэмюэл А .; Wunsch, Дональд К., II (2003), "Миллион город коммивояжер решение проблемы путем разделяй и властвуй кластеризация с адаптивным резонансных нейронных сетей", нейронные сети , 16 (5-6): 827-832, DOI : 10.1016 / S0893- 6080 (03) 00130-8 , PMID 12850040.
Внешние ссылки [ править ]
- Сайт Concorde
- Онлайн-доступ к решателю Concorde в Университете штата Аризона
