Задача коммивояжера
КУРСОВАЯ РАБОТА
по дисциплине:
«Структуры и алгоритмы обработки данных »
на тему:
«Задача коммивояжера»
Аннотация
Данная курсовая работа посвящена решению задачи коммивояжера методами динамического программирования и ближайшего соседа. В работе содержится описание алгоритмов этих методов и программа, реализующая данные алгоритмы. Пояснительная записка к курсовой работе содержит:
3 рисунка;
5 таблиц
21 страниц машинописного текста.
Введение.
В современной науке широкое распространение получили комбинаторные задачи. Для решения такого рода задач, несомненно, необходима ЭВМ, а также высокоэффективные алгоритмы решения этих задач.
Большинство таких задач основано на представлении в виде графа.
Одной из таких задач является “Задача коммивояжера”.
Основой задачи
стала проблема нахождения
При большом количестве городов задача имеет комбинаторную сложность, поэтому необходимо отказаться от идеи просмотра всевозможных путей и искать альтернативный метод.
Создано множество алгоритмов решения данной задачи однако, они имеют большие недостатки и проблема решения задачи для большого количества городов остается актуальной и в наши дни.
1.) Содержательная постановка задачи.
Решение задачи коммивояжера методом динамического программирования, а также приближенным методом ближайшего соседа. Произвести сравнительный анализ полученных решений.
2.)Анализ и пример решения задачи.
Задача коммивояжера относится к NP трудным задачам. Сутью задачи является нахождение оптимального маршрута посещения n городов. Эту задачу можно сформулировать следующим образом:
Коммивояжер хочет проехать по всем городам, побывав в каждом только по одному разу и вернуться к городу, из которого начато путешествие. При этом известно, что поездка из одного города i, в другой город j стоит c(i,j) рублей (будем считать цены целыми числами).
Если выполняется условие что: c(i,j)=c(j,i) для каждого города, то задача коммивояжера называется симметричной. Это условие может сильно упростить сложность решения задачи: так как можно отбросить половину возможных решения исходя из симметричности путей.
В терминах теории графов задача формулируется следующим образом:
Требуется найти в данном графе гамильтонов цикл наименьшей стоимости.
Известно, что при количестве городов равном n существуют (n-1)! возможных решений, из которых одно единственное является оптимальным. Искать оптимальное решение методом перебора всех этих значений тяжелая задача, даже для современных ЭВМ.
Для решения данной задачи существуют 2 группы методов.
Первые принадлежат к группе “точных” методов. Они дают оптимальное, исчерпывающее решение. Другая группа – группа “приближенных” методов, которые дают не точные, а приближенные решения. В наилучшем случае решения задачи этими методами может дать
результат, получаемый при решении данной задачи точными методами, однако, в наихудшем случае результат может быть неприемлемым. Эти методы применяются исходя из требований, предъявляемых к решению задачи.
Рассмотрим симметричную задачу коммивояжера с 4 городами.
Количество решений всевозможных решений будет равно (4-1)!=6
Вот все эти решения и цена каждого маршрута
Путь |
Цена |
ABCDA |
11 |
ABDCA |
21 |
ACBDA |
18 |
ACDBA |
21 |
ADBCA |
18 |
ADCBA |
11 |
B
1 2 3
12
A 1 6 C
D
Как видно из приведенной таблицы оптимальным маршрутом является маршрут ABCDA.
Условие симметричности в данном случае позволяет отбросить симметричные решения и искать оптимальный маршрут всего из 3 возможных решений:
Путь |
Цена |
ABCDA |
11 |
ABDCA |
21 |
ACBDA |
18 |
3.) Формальная постановка задачи.
3.1) Исходные данные.
Исходные данные необходимые для решения задачи коммивояжера следующие:
- Количество городов
- Названия городов
- Матрица стоимостей (путей).
3.2) Ограничения на исходные данные
Количество городов для решения задачи коммивояжера должны быть не менее 2 и не более 100 при применении вышеуказанных алгоритмов.
При количестве городов менее 2 задача коммивояжера теряет смысл, так как не возможно из множества с мощностью менее 2 создать ни одного маршрута. Верхний предел ограничивается памятью, которую требует алгоритм (в частности для метода динамического программирования занимаемая память таблиц может расти экспоненциально и описывается функцией O(n2n)). Поэтому при количестве городов более 100 решение задачи коммивояжера на существующих системах программирования невозможно.
3.3) Результирующие данные
Результатом решение коммивояжера является вывод цепочки городов оптимального маршрута и его стоимости, а также вывод приближенного тура и его стоимости.
3.4) Связь выходных данных с исходными данными
a) Динамическое программирование.
Пусть даны множество и .
Обозначим С(S,R) оптимальную стоимость пути, начинающегося в 1 городе и оканчивающегося в R городе, проходящего по всем городам множества S.
Для вычисления С(S,R) при |S|>1 будем использовать тот факт, что для нахождения наилучшего маршрута из города множества S, достаточно рассмотреть для каждого m вариант, в котором m город, который посещается непосредственно перед городом R, и обратимся к C(S-{R}, m) в предыдущей таблице. Таким образом :
b) Метод ближайшего соседа.
Пусть даны множество и .
Обозначим С(i,j) оптимальную стоимость пути из i-го города в и j городе.
Для каждого i города будем выбирать тот город j, для которого выполняется
где множество L – это множество городов, в которые ход из i города запрещен.
Для каждого i города вычисления прекращаются, когда |L|=|S|
Этот процесс осуществляется для каждого i города, в который можно попасть из первого города.
4.)Спецификация программы.
4.1)Исходные данные.
Исходные данные должны быть представлены в файле с именем “In_ file.pas”
Структура описания данных в файле следующая:
- Количество городов (целое число).
- Название городов (название города представляет собой одиночный символ, который ставится в соответствие этому городу).
- Матрица стоимостей
путей. (целочисленная матрица
Первый символ в строке описания названия городов автоматически становится отправным городом.
4.2) Функции
программы по обработке исключи
Если в файле указано число городов, которое выходит за рамки возможных значений, то программа выводит сообщение о неправильности входных данных и прекращает работу.
Если в файле указано больше названий городов, чем их количество указанное выше программа также выводит сообщение об ошибке во входных данных и прекращает свою работу.
При всех критических
завершениях программы в
“Error in input file”.
4.3)Выходные данные.
Выходные данные находятся в файле с именем “Out_ file.pas”.
Структура выходных данных следующая:
Данные для решения
задачи методом динамического
- Строка из цепочки
городов входящих в
- Стоимость найденного оптимального тура.
Данные для решения задачи методом ближайшего соседа:
- Строка из цепочки
городов входящих в
- Стоимость найденного оптимального тура.
4.4)Сценарий диалога.
Для правильной работы программы необходимо обязательно создать входной файл с необходимыми данными. Данный файл создается в той же директории что и сама программа. Название файла имеет следующее название : “In_ file.pas”.
Далее пользователю необходимо запустить программу на выполнение.
Файл выходными данными
5.)Разработка структур данных и алгоритмов.
Рассмотрим словесно-
а) Метод динамического
Начало
1)Ввод кол-ва городов |S|.
2)Ввод множества городов S.
3)Ввод матрицы стоимости путей.
4)Пусть С(S,r) есть оптимальный тур по всем городам множества S начинающийся в 1 городе и оканчивающийся в городе r. Используя реккурентную формулу:
вычислим предыдущие оптимальные туры для всех m из множества S ,
где m- город, который посещается непосредственно перед узлом r.
Dmr расстояние от города m до города r.
( при этом запомним m, для которых достигается минимальный частичный тур, для восстановления полного оптимального тура при обратном просмотре ).
5)Выведем цепочку городов входящих в найденный оптимальный тур в обратном порядке.
Конец.
b) Метод ближайшего соседа.
Начало
1.)Ввод кол-ва городов n .
2.)Ввод названия городов.
3.)Ввод матрицы стоимости путей.
4.)Создание для каждого города записи содержащей следующие поля:
Поле для хранения названия города.
Поле для хранения индекса города в матрице стоимости путей.
Поле для хранения множества
городов, не подлежащих
Поле для хранения городов вошедших в текущий маршрут.
Поле для хранения общего
5.)Запись стоимости пути от первого города до i города, в поле хранения стоимости путей тура каждого i города . ( i=2..n )
6.)Запись
первого города в число
7.)Запись
первого города в множества
городов, не подлежащих
8.)Поиск наименьшей стоимости пути, из всевозможных путей из i города до любого из городов, не вошедших в множества городов, не подлежащих дальнейшей проверке, данного i города.
9.)Добавление найденного города в число городов, вошедших в текущий маршрут i города.
10.)Добавления стоимости пути от i города к найденному, в поле хранения общей стоимости путей текущего маршрута, для данного i города.
11.)Добавление
найденного города в множество
городов, не подлежащих
12.)Запись названия найденного города в поле хранения названия i города.
13.)Если для всех i городов, мощность множества городов, не подлежащих дальнейшей проверке равна n, то переход к пункту 14, иначе переход к пункту 8;
14.)Добавить к полю для хранения общей стоимости пути текущего тура i города, расстояния до первого города. ( i=2..n )
15.)Вывод
наименьшей из стоимостей
Конец.
Как в первом, так и во втором алгоритме используется такая структура данных, как линейный список на основе вектора. Данный вектор служит для хранения в своих полях свойств городов. Данная структура данных выбрана, потому что она не требует сложных алгоритмов обращения с собой, а также идеально подходит в качестве таблиц для применения последовательного поиска, при нахождении частичных решений.
6) Исходный текст программы на языке Turbo Pascal 7.2
Program R_alg;
uses crt,dos;
var nm,e,sc,mm,nt,ch,i,j,n,sm,m,u,
aa,a,al :array[1..20,1..20] of integer;
bb,b,bl :array[1..20,1..2] of integer;
hh,c :array[1..20] of integer;
stj,st :set of byte;
procedure poisk;
var ss,jj,ii:integer;
begin
e:=0; i:=nt;
repeat
ss:=aa[i,i];
for j:=1 to ch do
if (ss>aa[i,j]) and not(j in st) and not(j in stj) then begin
ss:=aa[i,j];
jj:=j;
end;
include(st,i);
include(stj,jj);
inc(e);
bl[e,1]:=i;
bl[e,2]:=jj;
i:=jj;
until e=ch; end;
procedure choose;
var q,l,z,x,y:integer;
begin
for i:=1 to ch do
for j:=1 to ch do
if a[i,j]=0 then
begin
x:=i; y:=j;
inc(n);
b[n,1]:=x;
b[n,2]:=y;
z:=100; l:=100;
for q:=1 to ch do
if (z>a[x,q]) and (q<>y) then z:=a[x,q];
for q:=1 to ch do
if (l>a[q,y])and (q<>x) then l:=a[q,y];
c[n]:=z+l;
end;
end;
procedure podset;
var e,d:integer;
begin
u:=c[1];
v:=1;
for e:=1 to n do
if u<c[e] then begin
u:=c[e];
v:=e;
end;
bb[mm,1]:=b[v,1];
bb[mm,2]:=b[v,2];
inc(mm);
for e:=1 to ch do
a[e,b[v,2]]:=100;
for e:=1 to ch do
a[b[v,1],e]:=100;
a[b[v,2],b[v,1]]:=100;
end;
procedure privid;
var s:array [1..20] of integer;
w:integer;
begin
w:=100;
for i:=1 to ch do begin
for j:=1 to ch do
if w>a[i,j] then w:=a[i,j];
s[i]:=w;
w:=100;
end;
for i:=1 to ch do
for j:=1 to ch do
if (s[i]<>0)and (s[i]<>100) and (a[i,j]<>100) then a[i,j]:=a[i,j]-s[i];
w:=100;
for j:=1 to ch do begin
for i:=1 to ch do
if w>a[i,j] then w:=a[i,j];
s[j]:=w;
w:=100;
end;
for j:=1 to ch do
for i:=1 to ch do
if (s[j]<>0) and(s[i]<>100)and (a[i,j]<>100) then a[i,j]:=a[i,j]-s[j];
choose;
podset; end;
begin
textbackground(1);
textcolor(10);
mm:=1; m:=1;
sm:=0;
clrscr;
writeln('Введите количество городов');
readln(ch);
writeln(' Введите матрицу стоимости');
for i:=1 to ch do
for j:=1 to ch do
read(a[i,j]);
writeln('Введите начальную точку');
readln(nt);
nm:=nt;
for i:=1 to ch do
for j:=1 to ch do
aa[i,j]:=a[i,j];
repeat
n:=0;
privid;
inc(m);
until m>ch;
i:=1;
writeln (' Минимальный путь по методу ветвей и границ');
repeat
if (bb[i,1]=nt) and (sc<=ch) then begin
inc(sc);
write(' ',bb[i,1]);
nt:=bb[i,2];
if sc<=ch then i:=0;
end;
inc(i);
until i>ch;
writeln;
for i:=1 to ch do
sm:=sm+aa[bb[i,1],bb[i,2]];
writeln(' Сумма весов:',sm);
sm:=0; sc:=0;
st:=[]; nt:=nm;
poisk;
i:=1;
writeln (' Минимальный путь по методу ближайшего соседа');
repeat
if bl[i,1]=nt then begin
inc(sc);
write(' ',bl[i,1]);
nt:=bl[i,2];
if sc<ch then i:=0;
end;
inc(i);
until i>ch;
writeln(' ',nm);
for i:=1 to ch-1 do
sm:=sm+aa[bl[i,1],bl[i,2]];
sm:=sm+aa[bl[e,2],bl[1,1]];
writeln(' Сумма весов:',sm);
readkey;
end.
7) Результаты тестирования программы.
7.1) Тестовые
примеры для проверки
Тестовый пример №1
Пусть дана следующая таблица стоимостей путей:
A |
B |
C |
D | |
A |
-- |
1 |
12 |
1 |
B |
1 |
-- |
3 |
2 |
C |
12 |
3 |
-- |
6 |
D |
1 |
2 |
6 |
-- |
Решение, полученное для задачи ЗК заданной данной таблицей вручную:
Оптимальный маршрут: A-B-C-D-A
Стоимость маршрута: 11
Тестовый пример №2
Пусть дана следующая таблица стоимостей путей:
A |
B |
C |
D |
E |
F |
G | |
A |
-- |
1 |
2 |
6 |
7 |
9 |
12 |
B |
3 |
-- |
16 |
42 |
1 |
5 |
9 |
C |
4 |
5 |
-- |
6 |
8 |
3 |
4 |
D |
5 |
4 |
3 |
-- |
2 |
2 |
1 |
E |
7 |
6 |
1 |
21 |
-- |
7 |
2 |
F |
10 |
9 |
8 |
7 |
11 |
-- |
11 |
G |
1 |
7 |
6 |
2 |
3 |
9 |
-- |
Решение, полученное для задачи ЗК заданной данной таблицей вручную:
Оптимальный маршрут: A-B-E-C-F-D-G-A
Стоимость маршрута: 15
Тестовый пример №3
Пусть дана следующая таблица стоимостей путей:
A |
B |
C |
D |
E |
F |
G |
H |
I | |
A |
-- |
1 |
8 |
9 |
6 |
7 |
5 |
4 |
3 |
B |
6 |
-- |
4 |
3 |
1 |
4 |
2 |
7 |
4 |
C |
7 |
3 |
-- |
3 |
6 |
3 |
1 |
6 |
5 |
D |
1 |
5 |
6 |
-- |
8 |
7 |
7 |
9 |
6 |
E |
2 |
5 |
6 |
7 |
-- |
1 |
8 |
7 |
8 |
F |
3 |
6 |
1 |
7 |
5 |
-- |
5 |
8 |
9 |
G |
2 |
3 |
3 |
3 |
4 |
7 |
-- |
4 |
1 |
H |
2 |
3 |
4 |
1 |
7 |
8 |
7 |
-- |
4 |
I |
3 |
2 |
3 |
4 |
5 |
6 |
7 |
1 |
-- |
Решение, полученное для задачи ЗК заданной данной таблицей вручную:
Оптимальный маршрут: A-B-E-F-C-G-I-H-D-A
Стоимость маршрута: 9
7.2) Результаты,
полученные в результате
Результат №1
Результат №2
Результат №3
8) Сравнительный анализ результатов.
Как видно из полученных
результатов, решение задачи коммивояжера
методом динамического
Память, требующаяся для решения ЗК методом динамического программирования:
Общее число сложений и сравнений равно:
Память, требующаяся для решения ЗК методом ближайшего соседа:
Общее число сложений и сравнений равно:
Заключение
В данной курсовой работе был изложены алгоритмы решения задачи коммивояжера, составлены схемы алгоритмов решения этой задачи, а также составлены две программы на языке TURBO PASCAL, реализующие данные схемы.
Как видно из анализов курсовой работы ни один из рассмотренных методов нельзя назвать универсальным методом решения задачи коммивояжера. Эти методы имеют недостатки, и для решения задачи с определенными параметрами неприменимы, однако в определенных случаях дают хорошие показатели.
В ходе выполнения
работы были получены
Список литературы
- М. Свами, К. Тхуласираман. Графы, сети и алгоритмы. Москва: Мир, 1984.
- Ю. М. Коршунов. Математические основы кибернетики. Учебное пособие для вузов. - Москва: Энергия, 1980.
Содержание
Раздел
Аннотация
Введение
Содержательная
постановка задачи
Анализ
и пример решения задачи.
Формальная
постановка задачи
Спецификация
программы
Разработка
структур данных и алгоритмов
Исходный текст программы на языке Turbo Pascal 7.2 11
Результаты
тестирования программы
Сравнительный
анализ результатов.
Заключение
Список
литературы
- Задача коммивояжера
- Задача коммивояжера
- Задача коммивояжёра
- Задача коммивояжера и задача о назначениях
- Задача коммивояжера и методы её решения
- Задача коммивояжора
- Задача линейного программирования
- Задача динамического программирования
- Задача Ердеша-Морделла
- Задача и порядок проведения анализа диагностики банкротства и пути его преодоления
- Задача и содержание работы школьных библиотек
- Задача квадратичного программирования и её решение симплекс-методом
- Задача комивояжера
- Задача коммивояжера