Задача коммивояжера

Размещено на http://www.allbest.ru/

Задача коммивояжера



Содержание

Введение

1. Основная часть

1.1 Теоретическая часть (теория графов и обход графов)

1.2 Постановка задачи

1.3 Методы решения

1.4 Выбор алгоритма

2. Тестовая часть

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

2.2 Тестовый расчет

Заключение

Список используемых источников

Приложение А: Текст программы



Введение

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

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

Комбинаторика - раздел математики, посвящённый решению задач выбора и расположения элементов некоторого, обычно конечного множества в соответствии с заданными правилами.

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



1. Основная часть

1.1 Теоретическая часть (теория графов и обход графов)

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

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

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

Существуют две основные стратегии таких обходов: поиск в глубину и поиск в ширину. Эти стратегии можно описать так.

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

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

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

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

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

Рис.1

1.2 Постановка задачи

Постановка задачи следующая.

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

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

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

Дана полная сеть с n вершинами, длина ребра (i,j)= С_ij. Найти гамильтонов цикл минимальной длины.

В несимметричной ЗК вместо "цикл" надо говорить "контур", а вместо "ребра" - "дуги" или "стрелки".

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

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



Рис.2 Симметричная задача коммивояжера

Непременным условием и единственным смыслом задачи коммивояжёра является поиск самого выгодного пути. Для этого необходимо найти и описать все возможные пути при любом из вариантов способов поиска решения. Если мы не просчитали все пути в выбранном варианте решения, то мы не можем утверждать, что найденное решение самое выгодное. Что такое проверка решения? -- это поиск ошибки в процессе решения или сверка полученного результата с заведомо правильным. Второй вариант временно отбрасываем, так как нет практического смысла в решении задачи, если уже есть решение (в свою очередь, использование ранее выполненного верного решения для части имеющейся задачи -- способ уменьшить решение). В рамках данной работы не ставилось целью сравнение различных методов и способов решения, поэтому принимаем, что проверяющий также считает выбранный способ решения оптимальным и проверяет его на правильность. Что нужно сделать проверяющему? -- повторить работу, проделанную при решении, в полном объёме для поиска ошибки на каждом этапе решения. Если будет найдена ошибка, то проверяющему будет необходимо продолжить процесс решения для поиска более выгодного маршрута. Таким образом, мы получаем, что проверка решения задачи коммивояжёра равна или больше самого решения.



1.3 Методы решения

Существует 4 метода решения:

1) Простейшие

a) Полный перебор

b) Жадные алгоритмы

c) Метод минимального остовного дерева

d) Метод имитации отжига

2) Метод нейросети

3) Метод эластичной сети

4) Метод ветвей и границ

Полный перебор.

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

Жадные алгоритмы.

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

Рис.3 Открытый конверт

Рассмотрим для примера сеть на Рис.3, представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм "иди в ближайший город" выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.

Метод минимального остовного дерева.

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

Метод имитации отжига

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

Все эффективные (сокращающие полный перебор) методы решения задачи коммивояжёра -- методы эвристические. В большинстве эвристических методов находится не самый эффективный маршрут, а приближённое решение. Зачастую востребованы так называемые any-time алгоритмы, то есть постепенно улучшающие некоторое текущее приближенное решение.

Существуют также постановки, в которых задача коммивояжера становится NP-полной. Обычно такие постановки выглядят следующим образом: существует ли на заданном графе G такой обход, что его стоимость не превышает x. Часто на ней проводят обкатку новых подходов к эвристическому сокращению полного перебора.

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

Метод нейросети

Используется сеть, состоящая из 100 нейронов.

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

Метод эластичной сети

В 1987 году его использовали Дурбин (Durbin) и Уиллшоу (Willshaw), указавшие аналогию с механизмами установления упорядоченных нейронных связей.

Каждый из маршрутов коммивояжера рассматривался как отображение окружности на плоскость (в каждый город на плоскости отображается некоторая точка этой окружности). Соседние точки на окружности должны отображаться в точки, по возможности ближайшие и на плоскости.

Метод ветвей и границ

Общая идея метода может быть описана на примере поиска минимума функции f(x) на множестве допустимых значений переменнойx. Функция f и переменнаяxмогут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).

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

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

1.4 Выбор алгоритма

В этой курсовой работе выбираем алгоритм решения задачи методом ветвей и границ.

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



2. Тестовая часть

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

К идее метода ветвей и границ приходили многие исследователи, но Литтл с соавторами на основе указанного метода разработали удачный алгоритм решения ЗК и тем самым способствовали популяризации подхода. С тех пор метод ветвей и границ был успешно применен ко многим задачам, для решения ЗК было придумано несколько других модификаций метода, но в большинстве учебников излагается пионерская работа Литтла.

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

Изложим алгоритм Литтла на примере предыдущего раздела. Повторно запишем матрицу:

Нам будет удобнее трактовать С_ij как стоимость проезда из города i в город j. Допустим, что добрый мэр города j издал указ выплачивать каждому въехавшему в город коммивояжеру 5 долларов. Это означает, что любой тур подешевеет на 5 долларов, поскольку в любом туре нужно въехать в город j. Но поскольку все туры равномерно подешевели, то прежний минимальный тур будет и теперь стоить меньше всех. Добрый же поступок мэра можно представить как уменьшение всех чисел j-го столбца матрицы С на 5. Если бы мэр хотел спровадить коммивояжеров из j-го города и установил награду за выезд в размере 10 долларов, это можно было бы выразить вычитанием 10 из всех элементов j-й той строки. Это снова бы изменило стоимость каждого тура, но минимальный тур остался бы минимальным. Итак, доказана следующая лемма.

Вычитая любую константу из всех элементов любой строки или столбца матрицы С, мы оставляем минимальный тур минимальным.

Для алгоритма нам будет удобно получить побольше нулей в матрице С, не получая там, однако, отрицательных чисел. Для этого мы вычтем из каждой строки ее минимальный элемент (это называется приведением по строкам, см. Рис.5), а затем вычтем из каждого столбца матрицы, приведенной по строкам, его минимальный элемент, получив матрицу, приведенную по столбцам, см. Рис.6).

Прочерки по диагонали означают, что из города i в город i ходить нельзя. Заметим, что сумма констант приведения по строкам равна 27, сумма по столбцам 7, сумма сумм равна 34.

Тур можно задать системой из шести подчеркнутых (выделенных другим цветом) элементов матрицы С, например, такой, как показано на Рис.4. Подчеркивание элементаозначает, что в туре из i-го элемента идут именно в j-тый. Для тура из шести городов подчеркнутых элементов должно быть шесть, так как в туре из шести городов есть шесть ребер. Каждый столбец должен содержать ровно один подчеркнутый элемент (в каждый город коммивояжер въехал один раз), в каждой строке должен быть ровно один подчеркнутый элемент (из каждого города коммивояжер выехал один раз); кроме того, подчеркнутые элементы должны описывать один тур, а не несколько меньших циклов. Сумма чисел подчеркнутых элементов есть стоимость тура. На Рис.4 стоимость равна 36, это тот минимальный тур, который получен лексикографическим перебором.

Теперь будем рассуждать от приведенной матрицы на Рис.8. Если в ней удастся построить правильную систему подчеркнутых элементов, т.е. систему, удовлетворяющую трем вышеописанным требованиям, и этими подчеркнутыми элементами будут только нули, то ясно, что для этой матрицы мы получим минимальный тур. Но он же будет минимальным и для исходной матрицы С, только для того, чтобы получить правильную стоимость тура, нужно будет обратно прибавить все константы приведения, и стоимость тура изменится с 0 до 34. Таким образом, минимальный тур не может быть меньше 34. Мы получили оценку снизу для всех туров. Теперь приступим к ветвлению. Для этого проделаем шаг оценки нулей. Рассмотрим нуль в клетке (1,2) приведенной матрицы. Он означает, что цена перехода из города 1 в город 2 равна 0. А если мы не пойдем из города 1 в город 2? Тогда все равно нужно въехать в город 2 за цены, указанные во втором столбце; дешевле всего за 1 (из города 6). Далее, все равно надо будет выехать из города 1 за цену, указанную в первой строке; дешевле всего в город 3 за 0. Суммируя эти два минимума, имеем 1+0=1: если не ехать "по нулю" из города 1 в город 2, то надо заплатить не меньше 1. Это и есть оценка нуля. Оценки всех нулей поставлены на табл. 5 правее и выше нуля (оценки нуля, равные нулю, не ставились).

Выберем максимальную из этих оценок (в примере есть несколько оценок, равных единице, выберем первую из них, в клетке (1,2)).

Итак, выбрано нулевое ребро (1,2). Разобьем все туры на два класса - включающие ребро (1,2) и не включающие ребро (1,2). Про второй класс можно сказать, что придется приплатить еще 1, так что туры этого класса стоят 35 или больше.

Что касается первого класса, то в нем надо рассмотреть матрицу на Рис.8 с вычеркнутой первой строкой и вторым столбцом.

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

Рис.11 Результат получения оценок

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

Продолжим ветвление в положительную сторону: влево - вниз. Для этого оценим нули в уменьшенной матрице C[1,2] на Рис.9. Максимальная оценка в клетке (3,1) равна 3.

Рис.12 Результат

Таким образом, оценка для правой нижней вершины на Рис.9 есть 35+3=38. Для оценки левой нижней вершины на Рис.9 нужно вычеркнуть из матрицы C[1,2] еще строку 3 и столбец 1, получив матрицу C[(1,2),(3,1)] на Рис.10. В эту матрицу нужно поставить запрет в клетку (2,3), так как уже построен фрагмент тура из ребер (1,2) и (3,1), т.е. [3,1,2], и нужно запретить преждевременное замыкание (2,3). Эта матрица приводится по столбцу на 1 (Рис.13), таким образом, каждый тур соответствующего класса (т.е. тур, содержащий ребра (1,2) и (3,1)) стоит 36 и более.

Оцениваем теперь нули в приведенной матрице C[(1,2),(3,1)] нуль с максимальной оценкой 3 находится в клетке (6,5). Отрицательный вариант имеет оценку 38+3=41. Для получения оценки положительного варианта убираем строчку 6 и столбец 5, ставим запрет в клетку (5,6), см. Рис.14. Эта матрица неприводима. Следовательно, оценка положительного варианта не увеличивается (Рис.12).

Оценивая нули в матрице на Рис.14, получаем ветвление по выбору ребра (2,6), отрицательный вариант получает оценку 36+3=39, а для получения оценки положительного варианта вычеркиваем вторую строку и шестой столбец, получая матрицу на Рис.15.

В матрицу надо добавить запрет в клетку (5,3), ибо уже построен фрагмент тура [3,1,2,6,5] и надо запретить преждевременный возврат (5,3). Теперь, когда осталась матрица 2х2 с запретами по диагонали, достраиваем тур ребрами (4,3) и (5,4). Мы не зря ветвились, по положительным вариантам. Сейчас получен тур: 1>2>6>5>4>3>1 стоимостью в 36. При достижении низа по дереву перебора класс туров сузился до одного тура, а оценка снизу превратилась в точную стоимость.

Итак, все классы, имеющие оценку 36 и выше, лучшего тура не содержат. Поэтому соответствующие вершины вычеркиваются. Вычеркиваются также вершины, оба потомка которой вычеркнуты. Мы колоссально сократили полный перебор. Осталось проверить, не содержит ли лучшего тура класс, соответствующий матрице С[Not(1,2)], т.е. приведенной матрице С с запретом в клетке 1,2, приведенной на 1 по столбцу (что дало оценку 34+1=35). Оценка нулей дает 3 для нуля в клетке (1,3), так что оценка отрицательного варианта 35+3 превосходит стоимость уже полученного тура 36 и отрицательный вариант отсекается.

Рис.16 Результат

Для получения оценки положительного варианта исключаем из матрицы первую строку и третий столбец, ставим запрет (3,1) и получаем матрицу. Эта матрица приводится по четвертой строке на 1, оценка класса достигает 36 и кружок зачеркивается. Поскольку у вершины "все" убиты оба потомка, она убивается тоже. Вершин не осталось, перебор окончен. Мы получили тот же минимальный тур, который показан подчеркиванием на Рис.4.

Удовлетворительных теоретических оценок быстродействия алгоритма Литтла и родственных алгоритмов нет, но практика показывает, что на современных ЭВМ они часто позволяют решить ЗК с n = 100. Это огромный прогресс по сравнению с полным перебором. Кроме того, алгоритмы типа ветвей и границ являются, если нет возможности доводить их до конца, эффективными эвристическими процедурами.

Реализовать данный алгоритм можно, используя следующий псевдокод:

1. Начать с некоторой задачи

2. S={}множество активных подзадач

3. Лучший результат =

4. While S не пусто

5. Do выбрать подзадачу (частичное решение) и удалить её из S

6. Разбить P на меньшие подзадачи

7. For каждой

8. Do if является полным решением

9. Then обновить лучший результат

10. Else if нижняя граница <лучший результат

11. Then добавить в S

12. Return Лучший результат

Блок-схема алгоритма представлена на рис. 17



Рис.17 Блок-схема

2.2 Тестовый расчет

Задача коммивояжера может быть сформулирована как целочисленная введением булевых переменных, если маршрут включает переезд из города i непосредственно в город j и в противном случае. Тогда можно задать математическую модель задачи, то есть записать целевую функцию и систему ограничений:

(1)

Условия (2) - (4) в совокупности обеспечивают, что каждая переменная равна или нулю, или единице. При этом ограничения (2), (3) выражают условия, что коммивояжер побывает в каждом городе один раз, в него прибыв (ограничение (2)), и один раз, из него выехав (ограничение (3)).

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

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

Необходимо найти все кратчайшие пути от вершины №1 для графа, представленного на Рис.18.

Рис.18 (Данный пример)

Составим матрицу длин кратчайших дуг для данного графа.



?	10	18	8	?	?
10	?	16	9	21	?
?	16	?	?	15	?
7	9	?	?	?	12
?	?	?	?	?	23
?	?	15	?	23	?

Рис.19 (Матрица длин кратчайших дуг)

Стартовая вершина, от которой строится дерево кратчайших путей - вершина 1. Задаем стартовые условия: d(1)=0, d(x)=?. Окрашиваем вершину 1, y=1. Находим вершину, находящуюся рядом с окрашенной нами, используя формулу:

d(x)=min{d(x); d(y)+ a_y,x}

d(2)=min{d(2);d(1)+a(1,2)}=min{?;0+10}=10

d(3)=min{d(3);d(1)+a(1,3)}=min{?;0+18}=18

d(4)=min{d(4);d(1)+a(1,4)}=min{?;0+8}=8

d(5)=min{d(5);d(1)+a(1,5)}=min{?;0+?}=?

d(6)=min{d(6);d(1)+a(1,6)}=min{?;0+?}=?

Минимальную длину имеет путь от вершины 1 до вершины 4 d(4)=8. Включаем вершину №4 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину.

Согласно выражению это дуга (1,4)

d(2)=min{d(2) ; d(4)+a(4,2)}=min{10; 8+9}=10

d(3)=min{d(3) ; d(4)+a(4,3)}=min{18; 8+?}=18

d(5)=min{d(5) ; d(4)+a(4,5)}=min{?; 8+?}=?

d(6)=min{d(6) ; d(4)+a(4,6)}=min{?; 8+12}=20

Минимальную длину имеет путь от вершины 1 до вершины 2 d(2)=10. Включаем вершину №2 в текущее ориентированноe дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (1,2)

d(3)=min{d(3) ; d(2)+a(2,3)}=min{18; 10+16}=18

d(5)=min{d(5) ; d(2)+a(2,5)}=min{?; 10+21}=31

d(6)=min{d(6) ; d(2)+a(2,6)}=min{20; 10+?}=20

Минимальную длину имеет путь от вершины 1 до вершины 3 d(3)=18. Включаем вершину №3 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (1,3)

d(5)=min{d(5) ; d(3)+a(3,5)}=min{31; 18+15}=31

d(6)=min{d(6) ; d(3)+a(3,6)}=min{20; 18+?}=20

Минимальную длину имеет путь от вершины 1 до вершины 6 d(6)=20. Включаем вершину №6 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (4,6)

d(5)=min{d(5) ; d(6)+a(6,5)}=min{31; 20+23}=31

Минимальную длину имеет путь от вершины 1 до вершины 5 d(5)=31. Включаем вершину №5 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (2,5)

Мы получили ориентированное дерево кратчайших путей начинающихся в вершине №1 для исходного графа.

d(1)=1 Длина маршрута L=0

d(2)=1-2 Длина маршрута L=10

d(3)=1-3 Длина маршрута L=18

d(4)=1-4 Длина маршрута L=8

d(5)=1-2-5 Длина маршрута L=31

d(6)=1-4-6 Длина маршрута L=20

Рис.20 (Ориентированное дерево с корнем в вершине №1)



Заключение

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

Для составления программы использовался язык Object Pascal. Работа велась в среде Delphi 7.0. Для проверки правильности программы было подготовлено 3 тестовых примеров, один из которых приведен в разделе 2.2 работы. Все задачи были выполнены и цели работы достигнуты.

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



Список используемых источников

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

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

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

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

5. Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач. -- М.: Вузовский учебник, 2004. -- 144 с.

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

7. Акулич И.Л. Математическое программирование в примерах и задачах. -- М.: Высшая школа, 1986. -- 319 с.

8. Википедия [Электронный ресурс] : свободная энциклопедия / текст доступен по лицензии Creative Commons Attribution-ShareAlike ; Wikimedia Foundation, Inc, некоммерческой организации. электрон. дан. (712413 статей, 2479181 страниц, 1177104 загруженных файлов). Wikipedia®, 2001- . URL: https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ(дата обращения: 15.03.2015).

9. Википедия [Электронный ресурс] : свободная энциклопедия / текст доступен по лицензии Creative Commons Attribution-ShareAlike ; Wikimedia Foundation, Inc, некоммерческой организации. электрон. дан. (712413 статей, 2479181 страниц, 1177104 загруженных файлов). Wikipedia®, 2001- https://ru.wikipedia.org/wiki/Задача_коммивояжера (дата обращения: 18.03.2015).



Приложение А: Текст программы

unit Unit1;

interface

uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, Grids, ImgList, StdCtrls, ComCtrls, Menus, ToolWin;

type

TForm1 = class(TForm)

ToolBar1: TToolBar;

StatusBar1: TStatusBar;

MainMenu1: TMainMenu;

N1: TMenuItem;

N2: TMenuItem;

N3: TMenuItem;

N4: TMenuItem;

N5: TMenuItem;

N6: TMenuItem;

N7: TMenuItem;

N8: TMenuItem;

N9: TMenuItem;

N10: TMenuItem;

N11: TMenuItem;

N12: TMenuItem;

ToolButton1: TToolButton;

ToolButton2: TToolButton;

ToolButton3: TToolButton;

ToolButton4: TToolButton;

ToolButton5: TToolButton;

ToolButton6: TToolButton;

ToolButton7: TToolButton;

ToolButton8: TToolButton;

ToolButton9: TToolButton;

ComboBox1: TComboBox;

StaticText1: TStaticText;

ImageList1: TImageList;

OpenDialog1: TOpenDialog;

SaveDialog1: TSaveDialog;

StringGrid1: TStringGrid;

ToolButton10: TToolButton;

N13: TMenuItem;

procedure N6Click(Sender: TObject);

procedure FormCreate(Sender: TObject);

procedure ComboBox1Change(Sender: TObject);

procedure StringGrid1KeyPress(Sender: TObject; var Key: Char);

procedure N9Click(Sender: TObject);

procedure N8Click(Sender: TObject);

procedure N2Click(Sender: TObject);

procedure N3Click(Sender: TObject);

procedure N13Click(Sender: TObject);

procedure N11Click(Sender: TObject);

procedure N12Click(Sender: TObject);

procedure N4Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

Const Max=15;

Max_Stoimost=20;

Var Form1: TForm1;

n: Integer;

p: Boolean;

A:Array[1..Max,1..Max] Of Integer;

B:Array[1..Max,1..Max] Of Byte;

Way,BestWay:Array[1..Max] Of Byte;

Nnew:Array[1..Max] Of Boolean;

BestConst:Integer;

implementation

uses Unit2, Unit3;

{$R *.dfm}

Procedure Poisk (N1,Nconst:Byte;Stoim:Integer);

Var i:Integer;

Begin

If Stoim>BestConst Then Exit;

If Nconst=n Then Begin

Stoim:=Stoim+A[N1,1];

Way[n]:=N1;

If Stoim<BestConst Then

Begin

BestConst:=Stoim;

BestWay:=Way;

End;

Exit;

End;

Nnew[N1]:=False;

Way[Nconst]:=N1;

For i:=1 to n Do

If Nnew[B[N1,i]] Then Poisk(B[N1,i],Nconst+1,Stoim+A[N1,B[N1,i]]);

nnew[N1]:=true;

End;

procedure TForm1.N6Click(Sender: TObject);

begin

Form1.Close;

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

p:=false;

Form1.StringGrid1.Visible:=false;

end;

procedure TForm1.ComboBox1Change(Sender: TObject);

Var i,j:Integer;

begin

n:=Form1.ComboBox1.ItemIndex+2;

Form1.StringGrid1.rowcount:=n+1;

Form1.StringGrid1.colcount:=n+1;

for i:=1 to n do

begin

Form1.StringGrid1.Cells[0,i]:=' '+inttostr(i);

Form1.StringGrid1.Cells[i,0]:=' '+inttostr(i);

end;

for i:=1 to n do

for j:=1 to n do Form1.StringGrid1.Cells[j,i]:='0';

for i:=1 to n do Form1.StringGrid1.Cells[i,i]:= '#';

Form1.StringGrid1.Height:= (n+1)*Form1.StringGrid1.DefaultRowHeight+n+5;

Form1.StringGrid1.width:= (n+1)*Form1.StringGrid1.DefaultColwidth+n+5;

Form1.StringGrid1.Visible:=true;

end;

procedure TForm1.StringGrid1KeyPress(Sender: TObject; var Key: Char);

begin

p:=false;

if not (key in ['0'..'9',#8]) then key:=#0;

end;

procedure TForm1.N9Click(Sender: TObject);

Var i,j:Integer;

Min,h,r:Integer;

k:byte;

M:Set Of Byte;

path:string;

begin

if not(p) then showmessage('Необходимо проверить исходные данные!')

else

begin

randomize;

BestConst:=Maxint;

For i:=1 to n Do Nnew[i]:=True;

For i:=1 to n Do Begin

For j:=1 to n Do Begin

A[i,j]:=random(Max_Stoimost)+1;

If i=j Then A[i,j]:=Max_Stoimost+20;

Form1.StringGrid1.Cells[j,i]:=inttostr(A[i,j]);

End;

End;

For i:=1 to n Do

Begin

h:=0;

M:=[];

For r:=1 to n Do

Begin

Min:=Maxint;

For j:=1 to n Do

Begin

If not(j in M) Then

If Min>A[i,j] Then Begin

Min:=A[i,j];

k:=j;

End;

End;

Include(M,k);

h:=h+1;

B[i,h]:=k;

End;

End;

{

For i:=1 to Max Do Begin Writeln;

For j:=1 to Max Do Begin

Write(B[i,j]:4);

End;

End;

}

Poisk(1,1,0);

showmessage(inttostr(BestConst));

path:='';

For i:=1 to N Do path:=path+' '+inttostr(BestWay[i]);

showmessage (path);

end;

end;

procedure TForm1.N8Click(Sender: TObject);

Var i,j,k:Integer;

t:Boolean;

s:string;

begin

t:=true;

for i:=1 to Form1.StringGrid1.ColCount-1 do

for j:=1 to Form1.StringGrid1.RowCount-1 do

if i<>j then

begin

s:=form1.StringGrid1.Cells[i,j];

for k:=1 to length(s) do

if not (s[k] in ['0'..'9']) then t:=false;

end;

if t then p:=true else showmessage('Исправьте исходные данные!');

end;

procedure TForm1.N2Click(Sender: TObject);

Var

I,j : Byte;

F : TextFile;

S : String;

x,y:Integer;

begin

if OpenDialog1.Execute then begin

AssignFile(F, OpenDialog1.FileName);

Reset(F);

read(f,y);

ComboBox1.ItemIndex:=y-2;

n:=y;

Form1.StringGrid1.rowcount:=n+1;

Form1.StringGrid1.colcount:=n+1;

for i:=1 to n do

begin

Form1.StringGrid1.Cells[0,i]:=' '+inttostr(i);

Form1.StringGrid1.Cells[i,0]:=' '+inttostr(i);

end;

Form1.StringGrid1.Height:= (n+1)*Form1.StringGrid1.DefaultRowHeight+n+5;

Form1.StringGrid1.width:= (n+1)*Form1.StringGrid1.DefaultColwidth+n+5;

For I := 1 to StringGrid1.RowCount - 1 do

for j:=1 to form1.StringGrid1.ColCount - 1 do

Begin

read(f,x);

if x=-1 then StringGrid1.Cells[j,I]:='#' else StringGrid1.Cells[j,I]:=IntToStr(x);

end;

Form1.StringGrid1.Visible:=true;

CloseFile(F)

end;

end;

procedure TForm1.N3Click(Sender: TObject);

Var

I,j : Byte;

F : TextFile;

S : String;

begin

if OpenDialog1.Execute then begin

AssignFile(F, OpenDialog1.FileName);

Rewrite(F);

write(f,stringgrid1.colcount - 1);

For I := 1 to StringGrid1.RowCount - 1 do begin writeln(f);

for j:=1 to form1.StringGrid1.ColCount - 1 do

Begin

if StringGrid1.Cells[j,I]='#' then write(f,-1,' ') else

Write(F,StringGrid1.Cells[j,I],' ')

end;

end;

CloseFile(F)

end;

end;

procedure TForm1.N13Click(Sender: TObject);

var i,j,x:Integer;

begin

Randomize;

For I := 1 to StringGrid1.RowCount - 1 do begin

for j:=1 to form1.StringGrid1.ColCount - 1 do

Begin

x:=Random(100)+1;

StringGrid1.Cells[j,I]:=IntToStr(x);

end;

StringGrid1.Cells[i,I]:='#';

end;

end;

procedure TForm1.N11Click(Sender: TObject);

begin

form2.showmodal

end;

procedure TForm1.N12Click(Sender: TObject);

begin

form3.showmodal

end;

procedure TForm1.N4Click(Sender: TObject);

Var

I,j : Byte;

F : TextFile;

S : String;

begin

if OpenDialog1.Execute then begin

AssignFile(F, OpenDialog1.FileName);

Rewrite(F);

write(f,'Лучшая стоимость пути: ');

write(f,BestConst);

write(f,' Лучший путь: ');

For i:=1 to N Do write(f,BestWay[i]:2);

end;

CloseFile(F)

end;

end.

Размещено на Allbest.ru