«О графах и бродячих торговцах»

Проблема коммивояжёра, рассматриваемая в данной работе, является одной из наиболее известных задач оптимизации. Она заключается в отыскании наиболее выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. Повышенное внимание к этой проблеме во многом определено её практической значимостью: к задаче коммивояжёра обыкновенно сводится всякая задача построения оптимального порядка выполнения работ[5]. Наиболее выгодный маршрут для странствующего торговца пытались найти Уильям Гамильтон, Гаслер Уитни, Джордж Данциг и многие другие учёные.

Цель работы:

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

Задачи:

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

В процессе работы были использованы различные методы исследования: математическое моделирование, анализ литературных источников, использование средств ЭВМ для расчётов. Представленная работа состоит из введения, основной части, заключения. Таблицы не вынесены в приложения, так как они являются составной частью приводимых задач.

Глава 1. Задача коммивояжера

В общем виде задачу коммивояжера формулируют так:

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

Задача была известна уже в 1832 году, когда в Германии вышла в свет книга «Коммивояжер — как он должен вести себя и что должен делать для того, чтобы доставлять товар и иметь успех в своих делах — советы старого курьера». Автор этого произведения не применял математическое моделирование для решения проблемы, но предлагал конкретные маршруты, полученные опытным путём. В качестве математической задачи оптимизации проблема коммивояжера была сформулирована в 1930 году Карлом Менгером [3]. С этого времени многие математики искали алгоритмы решения данной проблемы. В процессе исследований были выделены различные виды задачи коммивояжера, основными из которых являются:

Симметричная задача коммивояжера (задача, в которой путь из города А в город В равен пути из города В в город А)
Ассиметричная задача коммивояжера (задача, в которой это условие не выполняется)
Задача коммивояжера, в которой выполняется неравенство треугольника.
Евклидова задача коммивояжера (задача, в которой издержки равны расстояниям между городами)[4].

1.1 Описание используемой математической модели

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

Граф (сеть) - конечное множество вершин и набор упорядоченных и неупорядоченных пар вершин (связей). Неупорядоченная пара вершин называется ребром, упорядоченная – дугой. [7]. Путем в графе от вершины A к B называется такая последовательность ребер (дуг), ведущая от A к B, в которой каждые два соседних ребра имеют общую вершину, и никакое ребро не встречается более одного раза. В данном случае вершина A будет началом пути, B – концом.

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

Полный граф – граф, в котором нет несмежных вершин. Ориентированный графом (орграфом) называется граф, содержащий дуги и не содержащий рёбра. Вершину, от которой идёт дуга, зовут источником, а вершину, к которой дуга направлена – стоком. Ориентированный граф, имеющий неотрицательную пропускную способность (то есть вес каждого ребра неотрицателен), называется транспортной сетью. В неориентированном графе путь, начало и конец пути которого совпадают, называется циклом, в ориентированном - контуром. Цикл от А до В является простым, если он не проходит ни через одну из вершин графа более одного раза (за исключением начальной, которая встречается в цикле дважды).Транспортная сеть – ориентированный граф, в котором каждое ребро имеет неотрицательный вес. В нём выделяют две вершины: источник и сток – такие, что любая другая вершина сети лежит на пути из источника в ток.

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

Матрица – система элементов, расположенных в виде прямоугольной системы [7]. Для невзвешенных ориентированных графов используются матрицы инцидентности, представляющие собой таблицу, строки и столбцы которой соответствуют вершинам. Сама таблица заполняется числами 1, 0 и -1: 1 - если вершина строки – начало дуги, 0 – если дуги нет, -1 – если вершина строки – конец дуги.

Список смежности – список, в котором каждой вершине соответствует строка, в которой хранится список смежных вершин.

1.2 Применение математической модели

Вернёмся к исследуемой проблеме. Для решения задачи коммивояжера составим граф, вершины которого будут соответствовать городам, а дуги и рёбра – соединяющим их дорогам. Вес каждой дуги будет равен расстоянию, стоимости или времени. Помимо уже перечисленных понятий, будем использовать следующие:

маршрут коммивояжера - цикл, включающий каждую вершину графа хотя бы один раз;

гамильтонов цикл - простой цикл, включающий каждую вершину графа.

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

Решение задачи коммивояжера для такого графа очевидно: 1 вершина - дуга, соединяющая 1 и 2 вершины - 2 вершина – ребро, соединяющее 2 и 1 вершины - 1 вершина. Это наименьший, но не единственный путь, существующий в этом графе. Он является частью более сложных путей типа: 1 вершина - ребро, соединяющее 1 и 2 вершины - 2 вершина – ребро, соединяющее2 и 1 вершины - 1 вершина - ребро, соединяющее1 и 2 вершины - 2 вершина - ребро, соединяющее 2 и 1 вершины - 1 вершина. В будущем на более сложных неориентированных графах мы не будем рассматривать подобные пути.

Теперь изучим полный неориентированный граф с тремя вершинами. Произвольно пронумеруем их числами от 1 до 3. Исходя из определения маршрута коммивояжера мы можем начинать путь из любой вершины. Из №1 мы можем попасть в №2 или в №3. Если из вершины №1 мы пойдём в вершину №2, то затем мы можем попасть в вершину №3 или вновь в №1. Как лучше поступить в данном случае? В произвольной задаче коммивояжера без конкретных числовых значений весов рёбер мы не можем ответить на данный вопрос. Рассмотрим один из видов задачи коммивояжера – введём условие неравенства треугольника.

Итак, в нашем графе для всех z ≠ х, z ≠ у выполняется условие {х, у}≤{х, z} + {z, у}. Тогда возвращение в вершину №1 нерационально: вес ребра {2,3} ≤{1,2}+{1,3}. Из вершины №2 нам стоит перейти в №3, затем в №1. Полученный маршрут будет следующим: 1 - {1-2} - 2 - {2-3} - 3 - {3-1} - 1. Если бы в самом начале мы перешли из вершины №1 в вершину №3, мы бы получили цикл с теми же рёбрами и вершинами, проходимыми в обратном направлении.

Рассмотренный пример подводит нам к следующему утверждению: если для каждого ребра {x,y} графа выполняется условие {x,y}≤{x,z}+{z,y}, z≠x, z≠y, то гамильтонов цикл является решением задачи коммивояжера на этом графе. Докажем его в общем виде.

Обозначим оптимальный маршрут коммивояжера буквой С. Если С не является гамильтоновым циклом, то некоторая вершина, например z, повторяется в маршруте С по крайней мере дважды. Предположим, что первый раз коммивояжер в вершину z пришел из вершины х и вышел из нее в направлении вершины у. Изменим маршрут С таким образом, чтобы коммивояжер из вершины х, минуя z, направился прямо к вершине у. Полученный в результате маршрут С' также является маршрутом коммивояжера, поскольку в нем каждая вершина посещается по крайней мере один раз. По неравенству треугольника в графе расстояние от одной вершины до другой никогда не превышает расстояние между ними через какую-то третью вершину, поэтому, общая длина С' не превышает длины С. Заменяя С на С' и повторяя эту процедуру, мы получим другой маршрут C'' и т. д. В конце концов этот процесс приведет нас к оптимальному маршруту, являющемуся гамильтоновым циклом, так как каждый последующий маршрут имеет число дуг на единицу меньшее, чем его предшественник. То есть, если граф удовлетворяет неравенству треугольника, то оптимальное решение задачи коммивояжера на графе G является оптимальным решением для общей задачи коммивояжера на этом графе.

Теперь рассмотрим два маршрута коммивояжера в неориентированном полном графе с четырьмя вершинами: 1 - {1-2} - 2 - {2-3} - 3 - {3-4} – 4 – {4-1} - 1 и 1 - {1-3} - 3 - {3-2} - 2 - {2-4} – 4– {4-1} – 1 (вершины пронумерованы по часовой стрелке). Какой из них меньше? Поскольку рёбра {2-3} и {1-4} входят в оба маршрута, нам нужно сравнить лишь сумму весов рёбер {1-2} и {3-4}, {1-3} и {2-4}. Сделать это при данных условиях мы не можем. Но если бы наш граф можно было начертить на плоскости так, чтобы расстояния между точками соответствовали весам рёбер (то есть в нём бы выполнялись аксиомы геометрии), мы могли бы утверждать, что первый путь меньше второго (если бы это было не так, то сумма диагоналей выпуклого четырёхугольника с вершинами 1,2,3,4 была бы больше суммы противоположных сторон этого четырёхугольника). Заметим, что первый из указанных нами путей является замкнутой не самопересекающейся ломаной. Всегда ли при данном условии существует не самопересекающийся маршрут больше данного самопересекающегося? Предположим, что это не так. Тогда оптимальный маршрут будет пересекать себя, и в нём найдётся по крайней мере два пересекающихся ребра, назовём их AC и BD. Они являются диагоналями выпуклого четырёхугольника ABCD. В выпуклом четырёхугольнике сумма противоположных сторон меньше суммы диагоналей, значит, при замене AC и BD на AB и CD периметр ломаной уменьшится, т. е. существует путь, меньший оптимального маршрута коммивояжера, что невозможно. Следовательно, наше предположение неверно, и при данном условии всегда существует не самопересекающийся маршрут больше данного самопересекающегося. Значит, оптимальный маршрут коммивояжера является не самопересекающейся ломаной.

Теперь рассмотрим не условный, а конкретный взвешенный граф, весы рёбер которого нам известны.

Задача. Дана схема маршрутов между постами. Определить оптимальный маршрут патрульно-постовой службы.

	1	2	3	4
1	-	15	22	21
2	15	-	15	34
3	22	15	-	30
4	21	34	30	-

Стоимость проезда из №1 в №2 равна стоимости проезда из №2 в №1, из №3 в №4 равна стоимости проезда из №4 в №3 и т.д. - перед нами ориентированный граф. Несложные расчёты (их легко провести в уме, если образно начертить граф на плоскости) доказывают, данный граф удовлетворяет неравенству треугольника. То есть, оптимальный маршрут, который мы ищем является гамильтоновым контуром. Гамильтоновых контуров в нашем графе три. Рассчитаем для каждого из них длину пути:

1-{1-2}-2-{2-3}-3-{3-4}-4-{4-1}-1: 15+15+30+21=81

1-{1-2}-2-{2-4}-4-{4-3}-3-{3-1}-1: 15+34+30+22=101

1-{1-4}-4-{4-2}-2-{2-3}-3-{3-1}-1: 21+34+15+22=92

Оптимальным является маршрут 1-{1-2}-2-{2-3}-3-{3-4}-4-{4-1}-1.

В процессе расчётов в задаче 2 полученные нами длины маршрутов ненамного отличались друг от друга. В каждом гамильтоновом цикле мы выходили из вершины №1, прибавляя к каждому пути некоторое число большее 15. Если бы вместо настоящего веса ребра мы прибавляли к каждому пути разницу между весом этого ребра и числом 15, длина каждого гамильтонова цикла уменьшилась бы на 15, и ответ бы не изменился. Точно также и с остальными вершинами. В каждом гамильтоновом цикле любая из четырёх вершин встречается лишь раз, значит, при уменьшении веса каждого ребра, принадлежащего какой-либо вершине, на одно и то же число, длина каждого контура уменьшится на одну и ту же величину, и минимальный путь останется минимальным.

Итак, при помощи математической модели «граф» мы несколько сузили область поиска оптимального маршрута коммивояжера. Для нахождения решения конкретной задачи коммивояжера необходимо знание издержек проезда, индивидуальных для каждой задачи.

Глава 2. Практическое применение задачи коммивояжера

Планирование маршрутов курьеров, гастролирующих артистов, путешественников – первоначальное, но далеко не единственное применение задачи коммивояжера. В литературе можно встретить примеры применения задачи коммивояжера в генетике, при оптимальном управлении механическими роботами[5], в экономике, а также при решении задачи о ходе коня[5] (последний пример кажется нам нецелесообразным, так как в задаче о ходе коня нужно найти гамильтонов цикл, в одном из видов задачи коммивояжера – наименьший гамильтонов цикл). Вообще, задачу коммивояжера правильнее было бы называть задачей выявления некоторого «целесообразного» или «экономного» порядка на произвольном множестве с заданной «функцией стоимости» [6]. С данной формулировкой задачи связана возможность её применения в алгоритмах поисковых систем. Список, полученный при помощи алгоритмов задачи коммивояжера не только отразит схожесть с эталоном, но и сгруппирует близкие между собой элементы.

Проведём небольшой эксперимент - попробуем определить оптимальный маршрут коммивояжера для цветов радуги. Используя цветовую модель RGB, определим «расстояния» между цветами в трёхмерном пространстве (по формуле . Это будут весы рёбер нашего графа. Представим его в виде матрицы.

	1	2	3	4	5	6	7
1	-	165	255	361	360	361	280
2	165	-	90	270	317	397	325
3	255	90	-	255	329	441	379
4	361	270	255	-	277	360	386
5	360	317	329	277	-	182	185.
6	361	397	441	361	182	-	139
7	280	325	379	386	185	139	-

В полученном нами графе в качестве весов рёбер используются расстояния между точками, значит, граф неориентированный. Его можно начертить в трёхмерном пространстве, поэтому в нём выполняется неравенство треугольника, и оптимальный маршрут коммивояжера на данном графе является гамильтоновым циклом (через любые три точки, не лежащие на одной прямой, проходит плоскость, на плоскости выполняется неравенство треугольника). Оценим, среди какого количества маршрутов нам нужно искать оптимальный. Различными путями обойти 7 городов, бывая в каждом лишь раз можно 7! способами (число перестановок). Искомый нами путь цикличен, поэтому маршруты, начинающиеся в разных городах, но обходящие города в одном порядке, можно считать одинаковыми. Каждый такой цикл повторяется в перестановках 7 раз. Рассматриваемая нами задача симметричная, значит пути обратные друг другу (типа 1-{1-2}-2-{2-3}-3 и 3-{3-2}-2-{2-1}-1) также можно считать одинаковыми. Значит, в неориентированном графе с семью вершинами гамильтоновых циклов (7)!/(2*7)=6!/2=360(число перестановок минус повторения циклов разделить на 2). Перебор такого большого числа путей требует большого количества времени. Для его экономии мы реализовали полный перебор на языке C++ и использовали ЭВМ для расчётов:

#include

using namespace std;

int main () {

int n=7;

vector> a(n,vector (n));

for (inti=0;i

for (int j=0;j

cin>>a[i][j];

intput,min=100000;

string s;

for (inti=0;i

for (int b=i+1;b

for (int c=b+1;c

for (int d=c+1;d

for (int e=d+1;e

for (int j=e+1;j

for (int z=j+1;z

{put=a[i][b]+a[b][c]+a[c][d]+a[d][e]+a[e][j]+a[j][z]+a[z][i]; if (put

cout<

В результате работы программы был получен следующий список:

Красный
Оранжевый
Жёлтый
Зелёный
Голубой
Синий
Фиолетовый

Он подтверждает слова о схожести соседних элементов.

Тёплые
Красный
Оранжевый
Жёлтый
Холодные
Зелёный
Голубой
Синий
Фиолетовый
R – 255, G,B<255
Красный
Оранжевый
G - 255
Жёлтый
Зелёный
B – 255, R,G<255
Голубой
Синий
Фиолетовый

2.1 Применение методов решения задачи коммивояжера для решения других задач

Решим следующую родственную проблеме коммивояжера задачу:

Задача 2.Четыре работника должны выполнять четыре вида работ. Назначить работников на работы таким образом, чтобы затраты труда были минимальны.

	1	2	3	4
1	7	7	3	6
2	4	9	5	4
3	5	5	4	5
4	6	4	7	2

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

	1	2	3	4
1	4	4	0	3
2	0	5	1	0
3	1	1	0	1
4	4	2	5	0

1 работу может выполнить с минимальными затратами 3 работник, так же он может выполнить с минимальными затратами 3 работу. Если он выполнит 1 работу, то 3 выполнит кто-то другой с затратами 1, если он выполнит 3 работу, то четвёртую придётся выполнять с затратами 3 или 4, поэтому 1 работу должен выполнять 3 работник. Аналогичными рассуждениями приходим к следующему распределению:

1 работник – 3 работа, 2 работник – 1 работа, 3 работник – 2 работа, 4 работник – 4 работа.

Эта задача является одной из задач об оптимальном назначении:

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

Заключение

Хотя проблема коммивояжёра была известна ещё в 19 веке, точка в её исследовании не поставлена до сих пор. В данной работе был применён подход к этой задаче с точки зрения теории графов. Были рассмотрены некоторые свойства оптимального маршрута коммивояжера, их применение на практике.

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

Список литературы

Березина Л.Ю «Графы и их применение» - М.: Просвещение, 1979. - 143 с.
Большая советская энциклопедия/под ред. А. М. Прохорова – М.: Советская энциклопедия, 1974.
Задача коммивояжера [Электронный ресурс] - https://ru.wikipedia.org/wiki/Задача_коммивояжёра
Задача коммивояжёра [Электронный ресурс] - http://www.managment.aaanet.ru/economics/kommivoyajer.php
Задача о коммивояжере и её обобщения: практическое применение [Электронный ресурс] - http://bibliofond.ru/view.aspx?id=528182
Иванко Е. Е. Маршрутно-распределительные задачи: теории и приложения [Электронный ресурс] - http://wwwrus.imm.uran.ru/C16/Diss/Z/IVANKO%20-%20thesis.pdf
Математическая энциклопедия: 1 том/под ред. И. М. Виноградова – М.: Советская

энциклопедия, 1977. – 576 с.

Методы решения труднорешаемых задач [Электронный ресурс] - http://rain.ifmo.ru/cat/view.php/theory/unsorted/approx-2004

Калитка в сад

Тигрёнок на подсолнухе

Сказки пластилинового ослика

Ах эта снежная зима

Земля на ладонях. Фантастический рассказ