Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Задача коммивояжера - файл Пояснительная записка.doc


Задача коммивояжера
скачать (92.2 kb.)

Доступные файлы (4):

KOM.CPP
KOM.EXE
Пояснительная записка.doc223kb.17.05.2009 21:55скачать
Титулный лист и содержание.doc33kb.17.05.2009 21:31скачать

Пояснительная записка.doc

ВВЕДЕНИЕ
Дана задача коммивояжера в классической формулировке: для некоторой группы городов с заданными расстояниями между ними требуется найти кратчайший маршрут посещения каждого города один раз с возвращением в исходный пункт. Кратчайший маршрут находится полным перебором, при этом оценка времени вычислений составляет t (n - 1)! без учета повторяющихся путей (например, 1-2-3-1 и 2-3-1-2). При этом в декартовом пространстве на плоскости полученный маршрут является границей неправильного многоугольника. Таким образом, можно предположить, что существует такая точка, что лучи, исходящие из нее, пересекают границы полученного многоугольника только в его вершинах. Будем называть эту точку – «центром массы» полученной фигуры. Предположим, что только вершинам многоугольника можно сопоставить понятие единичной «массы», а внутреннее пространство многоугольника «массой» не наделено. Координаты точки «центра массы» можно определить по формулам:

, где n – число городов, – координаты i [1, n] – города.

Каждому i-му городу сопоставляется луч, проходящий через точки и . После посещения города i [1, n], маршрут проходит в город j [1, n], ji, если при этом отрезок с концами и пересекает не более одного луча.

Предложенный алгоритм дает оценку времени вычислений t n(n - 1)(n - 2) в худшем случае и t * n * 1(n - 2) в лучшем случае при удачном выборе города – получателя для любого города – отправителя, где n – цикл по i городам – отправителям коммивояжера, (n-1) – цикл по j городам – получателям и (n-2) – цикл по лучам для определения возможных точек пересечения с отрезком (i, j).

Целью данной курсовой работы является рассмотрение задачи коммивояжера и написание программы на языке программирования C++.

Многие задачи, с которыми приходится иметь дело в повседневной практике, являются многовариантными. Среди множества возможных вариантов в условиях рыночных отношений приходится отыскивать наилучшие решения при ограничениях, налагаемых на природные, экономические и технологические возможности. В связи с этим возникла необходимость применять для анализа и синтеза экономических ситуаций и систем математические методы и современную вычислительную технику.
^ 1 МАТЕМАТЧЕСКИЕ ОСНОВЫ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА
1.1 Основные понятия теории графов
Пусть G – неориентированный граф. Геометрически граф можно представить как набор вершин (точек), определенные пары которых соединены линиями. Например, сеть дорог, соединяющих города ,,,, можно представить в виде графа следующим образом: города обозначены точками (вершинами), а дороги – неориентированными линиями (рис. 1).



рис. 1

Неориентированные линии означают наличие двустороннего движения между соответствующей парой городов. Пересечения линий не считаются вершинами.

При изображении графа не имеет значение расположение вершин на плоскости, кривизна и длина ребер (рис. 2).



рис. 2

Вершины графов обозначаются буквами или натуральными числами. Ребра графа – пары чисел.

Графические представления – наглядные отображения исследуемой системы процесса или явления на плоскость: рисунки, чертежи, схемы и блок-схемы, диаграммы, графы. На языке теории графов формируются и решаются многие технические задачи, задачи из области экономики, социологии, менеджмента и т.д. Графы используются для наглядного представления объектов и связи между ними.

Маршрутом в G называется такая конечная или бесконечная последовательность ребер, что каждые два соседних ребра имеют концевую точку. Причем, одно и то же ребро Е может встречаться в маршруте несколько раз.

Циклическим маршрутом называется такой маршрут, начальная и конечная точки которого совпадают.

Цепью называют маршрут, в котором каждое его ребро встречается не более одного раза; вершины в цепи могут повторяться не более одного раза. Любой участок цепи является цепью. Нециклическая цепь является простой цепью, если в ней никакая вершина не повторяется.

Граф называется сильно связным, если между каждой парой его вершин , , , существует путь () такой, что является начальной вершиной пути, а – конечной.

Граф называется связным, если между парой его вершин , , существует такая последовательность элементов (дуг или ребер, или же и дуг и ребер), что любая соседних элементов в этой последовательности имеет общую вершину. Очевидно, что любой сильно связный граф является связным. Связный неориентированный граф называется деревом, если он не имеет циклов. В дереве любые две вершины связаны единственной цепью.
^ 1.2 Формулировка и некоторые свойства решений задачи коммивояжера
Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3..n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Чтобы привести задачу к научному виду, введем некоторые термины. Города перенумерованы числами jТ=(1,2,3..n). Тур коммивояжера может быть описан циклической перестановкой t=(j1,j2,..,jn,j1), причём все j1...jn – разные номера; повторяющийся в начале и в конце j1, показывает, что перестановка зациклена. Расстояния между парами вершин Сij образуют матрицу С. Задача состоит в том, чтобы найти такой тур t:

…..(1)

Относительно математизированной формулировки задачи коммивояжера уместно сделать два замечания:

1) В постановке Сij означали расстояния, поэтому они должны быть неотрицательными, т.е. для всех jТ:

Сij0; Cjj=∞ (2)

(последнее равенство означает запрет на петли в туре), симметричными, т.е. для всех i,j:

Сij= Сji (3)

и удовлетворять неравенству треугольника, т.е. для всех:

Сij+ СjkCik (4)

В математической постановке говорится о произвольной матрице. Сделано это потому, что имеется много прикладных задач, которые описываются основной моделью, но всем условиям (2) – (4) не удовлетворяют. Особенно часто нарушается условие (3) (например, если Сij – не расстояние, а плата за проезд: часто туда билет стоит одну цену, а обратно – другую). Поэтому мы будем различать два варианта задачи коммивояжера: симметричную задачу, когда условие (3) выполнено, и несимметричную – в противном случае. Условия (2) – (4) по умолчанию мы будем считать выполненными.

2) В несимметричной задаче коммивояжера все туры t=(j1,j2,..,jn,j1) и t’=(j1,jn,..,j2,j1) имеют разную длину и должны учитываться оба. Разных туров очевидно (n-1)!.

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

В терминах теории графов симметричную задачу коммивояжера можно сформулировать так:

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

Некоторые прикладные задачи формулируются как задачи коммивояжера, но в них нужно минимизировать длину не гамильтонова цикла, а гамильтоновой цепи. Такие задачи называются незамкнутыми. Некоторые модели сводятся к задаче о нескольких коммивояжерах, но мы здесь их рассматривать не будем.
^ 1.3 Постановка задачи коммивояжера как задачи на графе


Формулировка: Множество городов: . Расстояние между городами i и j: . П – множество перестановок элементов А, перестановка





Если городам поставить в соответствии вершины графа, а соединяющих их дорогам дуги, то в терминах теории графов задача заключается в определении гамильтонова контура минимальной длины. Гамильтоновым контуром называется путь, проходящий через все вершины графа, у которого начальная вершина совпадает с конечной. Здесь под длиной контура понимают не количество дуг, входящих в контур, а сумму их длин. Длина соответствующей дороги – вес ребра. Граф должен быть полным, т.е. в нем имеются все возможные ребра. Если же граф не является полным, то его можно дополнить недостающими ребрами с весом равным .
^ 1.4 Условия существования Гамильтонова контура
Последовательность (путь), который требуется найти – ориентированный остовный простой цикл минимального веса в орграфе, такие циклы также называют гамильтоновыми. Очевидно, что в полном орграфе циклы указанного выше типа есть. Заметим, что вопрос о наличии в орграфе гамильтонова цикла достаточно рассмотреть как частный случай задачи о коммивояжере для полных орграфов. Действительно, если данный орграф не является полным, то его можно дополнить до полного недостающими ребрами и каждому из добавленных ребер приписать вес – это «компьютерная бесконечность», т.е. максимальное из всех возможных в рассмотрениях чисел. Если во вновь построенном полном орграфе найти теперь легчайший гамильтонов цикл, то при наличии у него ребер с весом можно будет говорить, что в данном, исходном графе «цикла коммивояжера» нет. Если же в полном орграфе легчайший гамильтонов цикл окажется конечным по весу, то он и будет искомым циклом в исходном графе.

Гамильтоновым контуром называется путь, проходящий через все вершины графа, у которого начальная вершина совпадает с конечной. Здесь под длиной контура понимают не количество дуг, входящих в контур, а сумму их длин.

^ 2 ПОСТАНОВКА И ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ
2.1 Алгоритм решения задачи
В курсовой работе для решения задачи о коммивояжере применяется метод ветвей и границ, относящийся к методам дискретной оптимизации. В сущности, это полный перебор решений, который оптимизируется за счет того, что при переборе вариантов по определенным признакам отсекаются неоптимальные множества перебора. Так как количество вершин от уровня к уровню возрастает в факториальной прогрессии, то отсечение вершин верхних уровней значительно сокращает общее число перебираемых вариантов.

Общая схема метода такова (данная программная реализация):

1. Все множество разбивается на N-1 подмножеств, каждое из которых оценивается верхней и нижней оценками.

2 Производится отсев неоптимальных множеств по следующему критерию: если нижняя оценка (решение релаксированной задачи) больше минимальной из верхних оценок (решений нерелаксированной задачи), то множество считается очевидно неоптимальным и отсекается, иначе остается до следующей итерации.

3. Находится множество с лучшей нижней оценкой (прогнозом) и дробится на количество, равное размерности исходной матрицы минус количество уже пройденных (фиксированных для данного множества) городов.

4. Находятся минимальные верхняя и нижняя оценки. Если они равны и достигнуты на одном и том же множестве, то это значит, что получено оптимальное решение и алгоритм заканчивает работу, иначе возврат к шагу 2.
^ 2.2 Построение математической модели
N – число городов.

Ci j , i, j=1…N – матрица затрат, где Ci j – затраты на переход из i-го города в j-й.

Xi j – матрица переходов с компонентами:

Xi j = 1, если коммивояжер совершает переход из i-го города в j-й,

Xi j = 0, если не совершает перехода,

где i, j = 1…N и ij.

Критерий:

(1)

Ограничения:

, i = 1…N (2)

, j = 1…N (3)

Ui – Uj + N  Xi j  N–1, i, j = 1…N, i  j (4)

Доказательство, что модель (1 – 4) описывает задачу о коммивояжере:

Условие (2) означает, что коммивояжер из каждого города выезжает только один раз; условие (3) – въезжает в каждый город только один раз; условие (4) – обеспечивает замкнутость маршрута, содержащего N городов, и не содержащего замкнутых внутренних петель.

Рассмотрим условие (4). Применим метод доказательства от противного, то есть предположим, что условие (4) выполняется для некоторого подцикла T из R городов, где R<N. Сложив все неравенства (4) вдоль этого подцикла получим



Так как



то N  R  (N – 1), где R<N, R  0

Следовательно, не существует замкнутого подцикла с числом городов меньшим, чем N.

Покажем, что существует Ui, которое для замкнутого цикла, начинающегося в некотором начальном пункте, удовлетворяет условию (4). При всех Xi j (j-й город не посещается после i-го) в (4) имеем Ui – Uj  N – 1, что допустимо в силу произвольных Ui и Uj.

Пусть на некотором R-ом шаге i-й город посещается перед j-м, то есть Xi j = 1. В силу произвольности значений Ui и Uj положим Ui = R, а Uj = R + 1, тогда из (4) имеем:

Ui – Uj + N  Xi j  R – (R – 1) + N = N – 1

Итак, существуют такие конечные значения для Ui и Uj, что для маршрута, содержащего N городов, условие (4) удовлетворяется как неравенство или строгое равенство, а следовательно, модель (1 – 4) описывает задачу о коммивояжере.
^ 2.3 Описание работы программы
Вначале для множества R всех гамильтоновых контуров определяется некоторая оценка снизу (нижняя граница) φ(R) их длины. Затем множество всех гамильтоновых контуров разбивается на два подмножества. Первое подмножество состоит из гамильтоновых контуров, которые включают некоторую дугу (i,j), а второе состоит из гамильтоновых контуров, которые не включают эту дугу, обозначим его {()}. Для каждого из подмножеств {(i,j)} и {()} определяется нижняя граница длины гамильтоновых контуров φ(i,j) и . Каждая новая нижняя граница оказывается не меньше нижней границы всего множества гамильтоновых контуров φ(R). Среди двух подмножеств маршрутов {(i,j)} и {()} выбирается подмножество с меньшей нижней границей. Это подмножество снова разбивается на два и для вновь образованных подмножеств находятся нижние границы.

Процесс разбиения подмножества аналогичным образом продолжается до тех пор, пока не будет выделено подмножество, содержащее единственный гамильтонов контур.

Взаимосвязь подмножеств получается в результате разбиения, изображается в виде дерева (графа), вершинами которого приписывают нижние границы.

Получив гамильтонов контур, просматривают оборванные ветви дерева и сравнивают нижние границы подмножеств, соответствующих оборванным ветвям, с длиной полученного гамильтонова контура. Если же нижние границы подмножеств, соответствующих оборванным ветвям, окажутся меньше длинны гамильтонова контура, то эти ветви разбивают по тому же правилу.

Процесс продолжается до тех пор, пока нижние границы вновь полученных подмножеств меньше длины гамильтонова контура. В этом случае сравниваются длины всех гамильтоновых контуров и среди них выбирается контур с наименьшей длиной.

Решение задачи решается законченным, если нижние границы оборванных ветвей не меньше длины гамильтонова контура. В качестве оптимального выбирается гамильтонов контур с наименьшей длинной.

В нашей программе ввод значений (входных данных) происходит через клавиатуру в самой программе. Стоимость проезда из одного города в другой мы вводим как матрицу.
^ 2.4 Текст программы
#include<stdio.h>

#include<conio.h>

#define ALL -1

#define MAXCITIES 10
enum BOOL{FALSE,TRUE};

long*visited;

long*min_circuit;

long*ham_circuit;

long min_circuit_length;
int n;

long matrix[MAXCITIES][MAXCITIES];

long INFI;


void reset_min_circuit(int s_v_id)

{

min_circuit[0]=s_v_id;

for(int i=1;i<n;i++) min_circuit[i]=-1;

}


void set_visited(int v_id,BOOL flag)

{

if(v_id==ALL) for(int i=0;i<n;i++) visited[i]=flag;

else visited[v_id]=flag;

}


void SET_HAM_CKT(long pl)

{

ham_circuit[0]=pl;

for(int i=0;i<n;i++) ham_circuit[i+1]=min_circuit[i];

ham_circuit[n+1]=min_circuit[0];

}

long get_valid_circuit(int s_v,int s_n_v)

{

int next_v,min,v_count=1;

long path_length=0;

min_circuit[0]=s_v;

min_circuit[1]=s_n_v;

set_visited(s_n_v,TRUE);

path_length+=matrix[s_v][s_n_v];

for(int V=s_n_v;v_count<n-1;v_count++)

{ min=INFI;

for(int i=0;i<n;i++)

if( matrix[V][i]<INFI && !visited[i]

&& matrix[V][i]<=min

)

min=matrix[V][next_v=i];

set_visited(next_v,TRUE);

V=min_circuit[v_count+1]=next_v;

path_length+=min;

}

path_length+=matrix[min_circuit[n-1]][s_v];

return(path_length);

}
void main()

{

clrscr();

INFI=999;

int pathcount,i,j,source,dest;

long dist=0;

long new_circuit_length=INFI;

printf("Vvedite kolichestvo gorodov: ",MAXCITIES);

scanf("%d",&n);

printf("Vvedite kolichestvo pytei: ");

scanf("%d",&pathcount);
printf("Vvedite matricy rasstoianii (nachlnii pynkt, konechnii pynkt, rasstoianie):\n");
for(i=0;i<n;i++)

for(j=0;j<n;j++)

matrix[i][j]=INFI;

for(i=0;i<pathcount;i++)

{

printf("[Pyt %d]:",i+1);

printf("\n");

scanf("%d %d %ld",&source,&dest,&dist);

if(source!=dest)

matrix[source][dest]=matrix[dest][source]=dist;

}
visited=new long[n];

min_circuit=new long[n];

ham_circuit=new long[n+2];

min_circuit_length=INFI;
for(int S_V_id=0;S_V_id<n;S_V_id++)

{

for(i=0;i<n;i++)

{

set_visited(ALL,FALSE);
set_visited(S_V_id,TRUE);
reset_min_circuit(S_V_id);
new_circuit_length=get_valid_circuit(S_V_id,i);
if(new_circuit_length<=min_circuit_length)

SET_HAM_CKT(min_circuit_length=new_circuit_length);

}

}
if(min_circuit_length<INFI)

{

printf("\n\nMinimalnii cikl dlinoi: %ld\nCikl:\n",min_circuit_length);

for(i=1;i<n+2;i++) printf("<%ld> ",ham_circuit[i]);

}

else printf("\n\nNe Gamiltonov cikl!");

getch();

delete []visited;

delete []min_circuit;

delete []ham_circuit;

}

^ БЛОК-СХЕМА ПРОГРАММЫ





INFI=999; long dist=0




long new_circuit_length=INFI











i=0






Нет





Да

j=0



Нет




Да







matrix[i][j]=INFI; j++


i++


i=0






Да

Нет



















Да

Нет


matrix[source][dest]=matrix[dest][source]=dist



i++










visited=new long[n]; min_circuit=new long[n]




ham_circuit=new long[n+2]; min_circuit_length=INFI




int S_V_id=0












Нет






Да

i=0



Нет






Да


set_visited(ALL,FALSE); set_visited(S_V_id,TRUE)


Да


i++





reset_min_circuit(S_V_id)


S_V_id++




new_circuit_length=get_valid_circuit(S_V_id,i)



Нет

SET_HAM_CKT(min_circuit_length=new_circuit_length)













Да

Нет








Да

Нет


i=1












i++








delete []visited; delete []min_circuit



delete []ham_circuit








Да

Нет

min_circuit[i]=-1; i++

ham_circuit[0]=pl; i=0

Да

Нет

ham_circuit[i+1]=min_circuit[i]


min_circuit[0]=s_v_id; i=1







ham_circuit[n+1]=min_circuit[0]; i++









Да

Нет



i=0

visited[v_id]=flag



Да

Нет

visited[i]=

flag; i++









ЗАКЛЮЧЕНИЕ
В предыдущих разделах были описаны теоретические основы решения задачи коммивояжера, рассмотрены основные понятия теории графов. Представлена программа, написанная на языке программирования С++, реализующая решение задачи коммивояжера методом ветвей и границ. Данный метод является универсальным для решения различных задач оптимизации в области экономики, производства и управления.


^ ТЕСТИРОВАНИЕ ПРОГРАММЫ
Входные данные:

Количество городов: 4

Количество путей: 6

Путь 1: 0 1 70

Путь 2: 0 2 200

Путь 3: 0 3 210

Путь 4: 1 2 130

Путь 5: 1 3 160

Путь 6: 2 3 250
Выходные данные:

Минимальный цикл длиной: 660

Цикл: <3> <2> <1> <0> <3>

ЛИТЕРАТУРА


  1. Вентцель Е.С. Исследование операций: задачи, принципы, методология. - М.: Высшая школа, 2004.-208с.

  2. Исследование операций в экономики / Под ред. Кремера Н.Ш. – М.:ЮНИТИ, 2004.-407с.

  3. Конюховский П.В. Математические методы исследования операций в экономике. Краткий курс. – СПб.: Питер, 2002.-208с.

  4. Просветов Г.И. Математические методы в экономике: Учебно – методическое пособие. – М.: Издательство РДЛ, 204.-160с.

  5. Костевич Л.С. Математическое программирование: Информационные технологии оптимальных решений. – Мн.: Новое издание, 2003.-424с.




Скачать файл (92.2 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации