Задача коммивояжера
Введение
«Задача коммивояжера» заключается в нахождении кратчайшего пути туда и обратно для заданного количества городов. Это выглядит просто, может быть решено только для небольшого количества промежуточных станций, потому что с каждым другим городом количество возможных комбинаций чрезвычайно увеличивается: в десяти городах существует около 181 000 возможных маршрутов, которые необходимо рассчитать и сравнить. Их уже более 1,8 миллиона в одиннадцати городах, а в 20 городах их число исчисляется триллионами.
Задача коммивояжера, задача заказа - это задача исследования операций, которая заключается в определении оптимального порядка городов или машин, в котором общие затраченные километры, время или затраты минимальны. Задача получила свое название от задачи определения оптимального маршрута путешественника, который должен посетить n мест и должен вернуться к месту отправления в конце путешествия.
СОДЕРЖАНИЕ
Введение
ОСОБЕННОСТИ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА
Задача коммивояжера: сущность и применение на практике
Моделирование в графике.
ЗАКЛЮЧЕНИЕ
Список использованной литературы
Список использованной литературы
Дулькейт В.И., Файзуллин Р.Т. Приближенное решение задачи коммивояжера методом рекурсивного построения вспомогательной кривой // вычислительные методы в дискретной математике. Омск. Изд-во Омского гос.тех.ун-та. 2009. № 1 (3). С. 72-78.
Прикладное программное обеспечение для решения экономических задач: лабораторный практикум. Екатеринбург: Изд-во Ур. гос.ун-та им. А.М. Горького, 2008. 30 с.
Описание электронного ресурса
Алгоритм имитации отжига [Электронный ресурс] // URL: http://www.math.nsc.ru/AP/benchmarks/UFLP/uflp_sa.html.
Задачи коммивояжера [Электронный ресурс] // URL: http://window.edu.ru/window_catalog/pdf2txt?p_id=26518&p_page=7.
Задача – коммивояжер [Электронный ресурс] // URL: http://www.ai08.org/index.php/term/,9da4ac975b546c395b9c3ba39a8d61988dac9f39ae6c59a86e3daa98418d6c395b9c3cad9a8d609853aa9f39af6c8fa86e3dab98a7606c395b9c3c349a8d61988da99f39af6c8fac649c3ea49a5960988fb19f33416c8da56e3f3f983b616c335d9c3ea59a8f61988fb09fadaf6c8da46ea93d9a9a8d61988aaf9f39af6c8f386e3daa98418e6647716da7a4af585bac66675b595eaea9546656596052a89b5e9260645d5a9f.xhtml.
Задача о коммивояжере [Электронный ресурс] // URL: http://mirslovarei.com/content_biz/Zadacha-O-Kommivojazhere-4474.html.
Задача о коммивояжере [Электронный ресурс] // URL: http://zs7.ru/text/nauka/kommivoyager.
Метод ветвей и границ [Электронный ресурс] // URL: http://pco.iis.nsk.su/ICP/Practice/dd8-3/node9.html.
Надстройка Microsoft Excel «Поиск решения» [Электронный ресурс] // URL: http://office.microsoft.com/ru-ru/excel-help/HP005198443.aspx.
Практическое применение задачи коммивояжера [Электронный ресурс] // URL: http://lmatrix.ru/news2/news2_4.html.
Сетевые модели/ Коммивояжер [Электронный ресурс] // URL: http://exsolver.narod.ru/NFP/NFP_salesman.html.
Экономико-математическое моделирование в управлении компанией: оптимизация транспортных потоков [Электронный ресурс] // URL: http://www.cig-bc.ru/library/74190/78999/.
Также существует обобщение задачи, так называемая обобщённая задача коммивояжёра.
Общая постановка задачи и большинство её частных случаев, относится к классу NP-сложных задач. Поэтому алгоритмы решения этой задачи делятся на точные и приближенные. Все точные алгоритмы фактически представляют собой оптимизированный полный перебор вариантов. В некоторых случаях эти алгоритмы достаточно быстро находят решения, но в общем случае приходится перебирать все n! циклов.
При постановке задачи коммивояжера для k коммивояжеров на множестве из n+1 городов строится k замкнутых маршрутов по следующим правилам:
один из городов, называемый базой входит во все маршруты;
каждый из городов, исключая базу входит в ровно один из маршрутов;
суммарная длина всех маршрутов минимальна.