Решение задачи коммивояжера

  • 02 мая 2012 г.
  • 852 Слова
Введение
В моей курсовой работе рассматривается задача коммивояжера. Цель курсовой работы – изучить задачу коммивояжера, ее виды и способы ее решения.
Коммивояжер (фр. commis voyageur) —разъездной сбытовой посредник, который, перемещаясь по рынку, выполняет роль простого посредника или действует по поручению своего клиента(продавца); разъездной торговый агент какой-либо фирмы, предлагающийпокупателям товары по образцам и каталогам.
Задача коммивояжера (англ. Travelling salesman problem, TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самоговыгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.)и соответствующие матрицы расстояний, стоимости и т. п. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляетсясреди гамильтоновых циклов.
Комбинаторная оптимизация – область теории оптимизации в прикладной математике, связанная с исследованием операций, теорией алгоритмов и теорией вычислительной сложности. В комбинаторнойоптимизации используются как математические подходы, так и методы искусственного интеллекта. Алгоритмы комбинаторной оптимизации, одним из наиболее популярных среди них является метод ветвей и границ, применяются прирешении NP-трудных задач, позволяя уменьшать пространство допустимых решений с помощью эффективной процедуры поиска.
Общая постановка задачи, впрочем как и большинство её частных случаев, относитсяк классу NP-полных задач. Задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантовникакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет.
В теории алгоритмов NP-полная задача —...
tracking img