Задача коммивояжера курсовая скачать

Курсовой проект.

Общее описание. 1.2. Методы решения задачи коммивояжера. 1.2.1. Жадный алгоритм. 1.2.3. Метод ветвей и границ.

1.3. Практическое применение задачи коммивояжера. 2. Блок-схема к алгоритму. 2.1. Пояснения и применяемые обозначения в алгоритме. 3.2.

Работа с приложением. Задача коммивояжера (в дальнейшем сокращённо - ЗК) является одной из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году, и об неё, как об Великую теорему Ферма обламывали зубы лучшие математики. В своей области (оптимизации дискретных задач) ЗК служит своеобразным полигоном, на котором испытываются всё новые методы. ЗК является NP-полной, и по тому имеет только один абсолютно точный класс алгоритмов – перебор вариантов.

Этот класс вариантов решения самый долгий (по времени выполнения), и потому является самым невыгодным при решении задачи с большим количеством городов. Постановка задачи следующая. Коммивояжер должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3.. n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Приведем задачу к математическому виду. Города перенумерованы числами j?Т=(1,2,3..n). Тур коммивояжера может быть описан циклической перестановкойt=(j 1 ,j 2 . j n ,j 1 ), причём всеj 1 ..j n – разные номера; повторяющийся в начале и в концеj 1 , показывает, что перестановка зациклена. Расстояния между парами вершин С ij образуют матрицу С. Задача состоит в том, что необходимо найти такой турt, чтобы минимизировать функционал. Относительно данной формулировки ЗК уместно сделать два замечания. Во-первых, в постановке С ij означали расстояния, поэтому они должны быть неотрицательными, т.е. для всехj?Т: (последнее равенство означает запрет на петли в туре), симметричными, т.е. для всех i,j: и удовлетворять неравенству треугольника, т.е. для всех: В математической постановке говорится о произвольной матрице. Сделано это потому, что имеется много прикладных задач, которые описываются основной моделью, но всем условиям (2)-(4) не удовлетворяют.

Особенно часто нарушается условие (3) (например, если С ij – не расстояние, а плата за проезд: часто туда билет стоит одну цену, а обратно – другую). Поэтому можно выделить два варианта ЗК: симметричную задачу, когда условие (3) выполнено, и несимметричную - в противном случае. Условия (2)-(4) по умолчанию мы будем считать выполненными. Второе замечание касается числа всех возможных туров. В несимметричной ЗК все туры t=(j 1 ,j 2 . j n ,j 1 ) иt’=(j 1 ,j n . j 2 ,j 1 ) имеют разную длину и должны учитываться оба. Разных туров очевидно (n-1)!. Зафиксируем на первом и последнем месте в циклической перестановке номер j 1 , а оставшиесяnномеров переставим всеми (n-1)! возможными способами.

В результате получим все несимметричные туры. Симметричных туров имеется в два раз меньше, т.к. каждый засчитан два раза: какtи какt’. Можно представить, что С состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро (i,j) проведено, если С ij =1 и не проведено, если С ij =0. Тогда, если существует тур длиныn+1, то он пройдёт по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом. Незамкнутый гамильтонов цикл называется гамильтоновой цепью (гамильтоновым путём). В терминах теории графов симметричную ЗК можно сформулировать так:

Дана полная сеть с n вершинами, длина ребра ( i , j )= С ij . Найти гамильтонов цикл минимальной длины. В несимметричной ЗК вместо «цикл» надо говорить «контур», а вместо «ребра» - «дуги». Некоторые прикладные задачи формулируются как ЗК, но в них нужно минимизировать длину не гамильтонова цикла, а гамильтоновой цепи. Такие задачи называются незамкнутыми. Некоторые модели сводятся к задаче о нескольких коммивояжерах, но мы в данной работе их рассматривать не будем.