Задача коммивояжёра

Муравьиный алгоритм[править | править код]
Основная статья: Муравьиный алгоритм
Генетический алгоритм[править | править код]
Основная статья: Генетический алгоритм
Алгоритм динамического программирования[править | править код]
Основная идея заключается в вычислении и запоминании пути от исходного города и до каждого из остальных городов, затем суммирования этой величины с путем из каждого из остальных городов до оставшихся городов и т. д. Преимущество данного метода {\displaystyle D}  перед методом полного перебора {\displaystyle F}  заключается в существенном сокращении полного объема вычислений {\displaystyle P_{D}=(6n-1)-n2^{n-1}+4n(n-1)2^{n-2},P_{F}=n!\approx n^{n}e^{-n}{\sqrt {2\pi n}},P_{D}\ll P_{F}}  за счет заметного увеличения объема памяти {\displaystyle Q_{D}\sim 2^{n}{\sqrt {\frac {2n}{\pi }}},Q_{F}=2,Q_{D}\gg Q_{F}} ^[5].
См. также[править | править код]

• 
  Граф (математика)
  
• 
  Оптимизация
  
• 
  Комбинаторика
  
• 
  Исследование операций
  
• 
  Математическое программирование
  
• 
  Дискретная математика
  
• 
  Транспортная логистика
  
• 
  Проблема Штейнера
  

Примечания[править | править код]

1. 
   ↑ Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 275.
   
2. 
   ↑ Euler, Leonhard, Solution d’une question curieuse que ne paroit soumise à aucune analyse, Mémoires de l’académie des sciences de Berlin, 15 (1759) 1766, p. 310—337.
   
3. 
   ↑ Костевич Л. С. Математическое программирование: Информ. технологии оптимальных решений: Учеб. пособие / Л. С. Костевич. — Мн.: Новое знание, 2003. ил., стр. 150, ISBN 985-6516-83-8
   
4. 
   ↑ Richard Durbin, David Willshaw. An analogue approach to the travelling salesman problem using an elastic net method (англ.) // Nature. — 1987-04-22. — Vol. 326, iss. 6114. — P. 689–691. — doi:10.1038/326689a0.
   
5. 
   ↑ Корбут А. А., Финкельштейн Ю. Ю. Дискретное программирование. — М., Наука, 1969. — C. 258—264
   

Литература[править | править код]

• 
  Левитин А. В. Глава 3. Метод грубой силы: Задача коммивояжёра // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 159—160. — 576 с. — ISBN 978-5-8459-0987-9
  
• 
  Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.
  
• 
  В.И. Мудров. Задача о коммивояжёре. — М.: «Знание», 1969. — С. 62.
  
• 
  Ежов А., Шумский С. Нейрокомпьютинг и его применения в экономике и бизнесе . — М.: МИФИ, 1998. — С. 216.
  
• 
  Gross J. L., Yellen J. Graph theory and its applications. Second edition. Boca Raton—London—New York: Chapman & Hall/CRC, 2006.