Отыскание кратчайшего пути

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

Содержание

Введение

1. Теоретическая часть

1.1 История теории графов

1.2 Основные термины теории графов

1.3 Представление графов в ЭВМ

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

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

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

3. Решение задачи аналитическим методом

4. Создание приложения для решения задачи

4.1 Описание алгоритма

4.2 Разработка программы

4.3 Тестирование программы

4.4 Руководство пользователя

Заключение

Список использованных источников

Введение

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

Теория графов многократно переоткрывалась разными авторами при решении различных прикладных задач.

Самыми знаменитыми задачами в теории графов являются: задача о Кенигсбергских мостах, задача о трех домах и трех колодцах, задача о четырех красках.

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

Поэтому данная тема на современном этапе развития общества имеет не самое последнее по значимости место.

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

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

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

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

граф коммивояжер программный математический

1. Теоретическая часть

1.1 История теории графов

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

Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок. Одним из первых результатов в теории графов явился критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах (рисунок 1). Вот пересказ отрывка из письма Эйлера от 13 марта 1736 году: ” Мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто 7 мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не смог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел лёгкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может“.



Рисунок 1 - Иллюстрация к задаче о Кенигсбергских мостах

Рассмотрев эту задачу, в 1736 году Эйлер доказал, что это невозможно, причем он рассмотрел более общую задачу: какие местности, разделенные рукавами рек и соединенные мостами, возможно обойти, побывав на каждом мосту ровно один раз, а какие невозможно.

Проблема четырех красок также выглядит как развлекательная задача, однако попытки ее решения привели к появлению некоторых исследований графов, имеющих теоретическое и прикладное значение. Проблема четырех красок формулируется так: ”Можно ли область любой плоской карты раскрасить четырьмя цветами так, чтобы любые две соседние области были раскрашены в различные цвета?”. Гипотеза о том, что ответ утвердительный, была сформулирована в середине 19 в. В 1976 году анонсировано положительное решение задачи с использованием ЭВМ.

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



Рисунок 2 - Иллюстрация к задаче о трех домах и трех колодцах

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

1.2 Основные термины теории графов

Терминология теории графов поныне не определена строго. В частности в монографии Гудман, Хидетниеми, 1981 сказано «В программистском мире нет единого мнения о том, какой из двух терминов "граф" или "сеть". Мы выбрали термин "сеть", так как он, по-видимому, чаще встречается в прикладных областях».

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

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

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

Две вершины называются смежными, если они соединены ребром (дугой). Смежные вершины называются граничными вершинами соответствующего ребра (дуги), а это ребро (дуга) - инцидентным соответствующим вершинам.

Путем называется последовательность дуг (в ориентированном графе), такая, что конец одной дуги является началом другой дуги. Простой путь - путь, в котором ни одна дуга не встречается дважды. Элементарный путь - путь, в котором ни одна вершина не встречается дважды. Контур - путь, у которого конечная вершина совпадает с начальной вершиной. Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если последние заданы).

Граф, для которого из (i, j) ? V следует (j, i) ? V называется симметрическим. Иначе, антисимметрическим.

Цепью называется множество ребер (в неориентированном графе), которые можно расположить так, что конец (в этом расположении) одного ребра является началом другого. Другое определение: цепь - последовательность смежных вершин. Замкнутая цепь называется циклом. По аналогии с простым и элементарным путем, можно определить соответственно простые и элементарные цепь и цикл. Любой элементарный цикл является простым, обратное утверждение в общем случае неверно. Элементарная цепь (цикл, путь, контур), проходящая через все вершины графа называется гамильтоновой цепью (соответственно - циклом, путем, контуром). Простая цепь (цикл, путь, контур), содержащая все ребра (дуги) графа называется эйлеровой цепью (соответственно - циклом, путем, контуром).

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

Связный граф, в котором существует эйлеров цикл, называется эйлеровым графом.

1.3 Представление графов в ЭВМ

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

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

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

Графы в ЭВМ можно представить следующими способами:

Матрица смежности

Один из самых распространённых способов хранения графа - матрица смежности. Она представляет собой двумерный массив. Если в клетке i, j (i - строка, j - столбец) установлено значение пусто (как правило, это очень большая величина или величина, которой заведомо не может равняться вес ребра), то дуги, начинающейся в вершине i и кончающейся в вершине j, нет. Иначе дуга есть. Если она есть, то в соответствующую ячейку записывают ее вес. Если граф не взвешенный, то вес дуги считается равным единице.

Для представления графа матрицей смежности нужно V2 (где V - количество вершин) ячеек. Если граф почти полный, т.е. Е сопоставимо V2 (где Е - количество дуг), этот способ хранения графа наиболее выгоден, т.к. его очень просто реализовывать и память будет заполнена "нужными" значениями.

Но если это условие не выполняется, например, вершин до 10000 и ребер до 1000, то нам понадобиться ?2 * 100000000 / 10242 Мбайт памяти (по 2 байта на ячейку), что примерно равно 190 Мбайт, памяти. А на олимпиадах, как правило, ограничении на ее использование составляет 64 Мбайт. Значит, этот метод не годиться.

Кроме большого количества требуемой памяти и медленной работы на разреженных графах (графах, у которых E << V2) у матрицы смежности есть ещё один важный недостаток. Иногда в задачах нужно выводить не номера вершин, а номера дуг (рёбер) на вводе. Хранить эти номера матрица смежности «не умеет». Нужно реализовывать восстановление номера дуги (ребра) как-то иначе, а это совсем неудобно.

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

Для матрицы смежности n(p,q) = О(р2), где ), где p - число вершин, q - число ребер.

Замечание:

Матрица смежности неориентированного графа симметрична относительно главной диагонали, поэтому достаточно хранить только верхнюю (или нижнюю) треугольную матрицу.

Матрица инцидентности

Представление графа с помощью матрицы Н, отражающей инцидентность вершин и ребер, называется матрицей инцидентности, где для неориентированного графа

а для орграфа

Для матрицы инцидентности n(p,q) = О(pq), где ), где p - число вершин, q - число ребер.

Списки смежности

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

<номер_начальной_вершины>: <номера_смежных_вершин>

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

В случае представления неориентированных графов списками смежности, объем необходимой памяти n(p,q) = O(p+2q), где p - число вершин, q - число ребер, а в случае ориентированных графов n(p,q) = O(p+q).

Иерархический список

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

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

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

Задача коммивояжёра есть NP-полная задача. Часто на ней проводят обкатку новых подходов к эвристическому сокращению полного перебора.

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

Задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет. Если в списке n городов, то число возможных путей обхода равно n! Поскольку 66! примерно равно 5,443449391Ч1092, а 67! ? 3,647111092Ч1094, задача проверки всех возможных путей становится трансвычислительной для n > 66.

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

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

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

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

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

Он наиболее оптимален и поэтому был выбран для решения задачи как аналитическим, так и программным способом.

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

Коммивояжер хочет объехать N городов и затем вернуться в начальный город, расстояния между которыми заданы. При этом желательно сделать это по наиболее короткому пути (т.к. коммивояжер не располагает лишними средствами на излишние перемещения между городами), где N =7. (таблица 1)

Таблица 1 - Исходные данные

	А1	А2	А3	А4	А5	А6	А7
А1	0	6	11	6	8	8	8
А2	6	0	9	12	6	7	2
А3	11	9	0	3	6	3	7
А4	6	12	3	0	2	3	13
А5	8	6	6	2	0	1	5
А6	8	7	3	3	1	0	3
А7	8	2	7	13	5	3	0



3. Решение задачи аналитическим методом

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

Таблица 2 - Исходные данные

	А1	А2	А3	А4	А5	А6	А7
А1	0	6	11	6	8	8	8
А2	6	0	9	12	6	7	2
А3	11	9	0	3	6	3	7
А4	6	12	3	0	2	3	13
А5	8	6	6	2	0	1	5
А6	8	7	3	3	1	0	3
А7	8	2	7	13	5	3	0

Возьмем в качестве произвольного маршрута:

X0 = (А1,A2);(A2,A3);(A3,A4);(A4,A5);(A5,A6);(A6,A7);(A7,А1)

Тогда F(X0) = 6+9+3+2+1+3+8=32

Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы найти минимальный элемент (таблица 3):di = minj dij

Таблица 3 - Значение минимума по строке

	А1	А2	А3	А4	А5	А6	А7	di
А1	0	6	11	6	8	8	8	6
А2	6	0	9	12	6	7	2	2
А3	11	9	0	3	6	3	7	3
А4	6	12	3	0	2	3	13	2
А5	8	6	6	2	0	1	5	1
А6	8	7	3	3	1	0	3	1
А7	8	2	7	13	5	3	0	2

Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

Такую же операцию редукции проводим по столбцам (таблица 4):dj = mini dij

Таблица 4 - Значение минимума по столбцу

	А1	А2	А3	А4	А5	А6	А7
А1	0	0	5	0	2	2	2
А2	4	0	7	10	4	5	0
А3	8	6	0	0	3	0	4
А4	4	10	1	0	0	1	11
А5	7	5	5	1	0	0	4
А6	7	6	2	2	0	0	2
А7	6	0	5	11	3	1	0
dj	4	0	1	0	0	0	0

После вычитания минимальных элементов получаем полностью редуцированную матрицу (таблица 5), где величины di и dj называются константами приведения.

Таблица 5 - Редуцированная матрица

	А1	А2	А3	А4	А5	А6	А7
А1	0	0	4	0	2	2	2
А2	0	0	6	10	4	5	0
А3	4	6	0	0	3	0	4
А4	0	10	0	0	0	1	11
А5	3	5	4	1	0	0	4
А6	3	6	1	2	0	0	2
А7	2	0	4	11	3	1	0

Шаг №1.

Определяем ребро ветвления (таблица 6) и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).



Таблица 6 - Определение ребра ветвления

	А1	А2	А3	А4	А5	А6	А7	di
А1	0	0(0)	4	0(0)	2	2	2	0
А2	0(0)	0	6	10	4	5	0(2)	0
А3	4	6	0	0(0)	3	0(0)	4	0
А4	0(0)	10	0(1)	0	0(0)	1	11	0
А5	3	5	4	1	0	0(1)	4	1
А6	3	6	1	2	0(1)	0	2	1
А7	2	0(1)	4	11	3	1	0	1
dj	0	0	1	0	0	0	2	0

Наибольшая сумма констант приведения будет (2 + 0) = 2 для ребра (A2,A7), следовательно, множество разбивается на два подмножества (A2,A7) и (A2*,A7*).

Нижняя граница гамильтоновых циклов этого подмножества (таблица 7):

Таблица 7 - Нижняя граница гамильтонового цикла

	А1	А2	А3	А4	А5	А6	А7	di
А1	0	0	4	0	2	2	2	0
А2	0	0	6	10	4	5	0	0
А3	4	6	0	0	3	0	4	0
А4	0	10	0	0	0	1	11	0
А5	3	5	4	1	0	0	4	0
А6	3	6	1	2	0	0	2	0
А7	2	0	4	11	3	1	0	0
dj	0	0	1	0	0	0	2	2

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

После операции приведения сокращенная матрица будет иметь вид (таблица 8):



Таблица 8 - Сокращенная матрица

	А1	A2	A3	A4	A5	A6	di
А1	0	0	4	0	2	2	0
A3	4	6	0	0	3	0	0
A4	0	10	0	0	0	1	0
A5	3	5	4	1	0	0	0
A6	3	6	1	2	0	0	0
A7	2	0	4	11	3	1	1
dj	0	0	0	0	0	0	1

Поскольку нижняя граница этого подмножества (A2,A7) меньше, чем подмножества (A2*,A7*), то ребро (A2,A7) включаем в маршрут.

Шаг №2.

Определяем ребро ветвления (таблица 9) и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

Таблица 9 - Определяем ребро ветвления

	А1	A2	A3	A4	A5	A6	di
А1	0	0(5)	4	0(0)	2	2	0
A3	4	6	0	0(0)	3	0(0)	0
A4	0(1)	10	0(1)	0	0(0)	1	0
A5	3	5	4	1	0	0(1)	1
A6	3	6	1	2	0(1)	0	1
A7	1	0	3	10	2	0(1)	1
dj	1	5	1	0	0	0	0

Наибольшая сумма констант приведения будет (0 + 5) = 5 для ребра (А1,A2), следовательно, множество разбивается на два подмножества (А1,A2) и (А1*,A2*).

Нижняя граница гамильтоновых циклов этого подмножества (таблица 10):



Таблица 10 - Нижняя граница гамильтонового цикла

	А1	A2	A3	A4	A5	A6	di
А1	0	0	4	0	2	2	0
A3	4	6	0	0	3	0	0
A4	0	10	0	0	0	1	0
A5	3	5	4	1	0	0	0
A6	3	6	1	2	0	0	0
A7	1	0	3	10	2	0	0
dj	0	5	0	0	0	0	5

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

После операции приведения сокращенная матрица будет иметь вид (таблица 11):

Таблица 11 - Сокращенная матрица

	А1	A3	A4	A5	A6	di
A3	4	0	0	3	0	0
A4	0	0	0	0	1	0
A5	3	4	1	0	0	0
A6	3	1	2	0	0	0
A7	1	3	10	2	0	0
dj	0	0	0	0	0	0

Чтобы исключить подциклы, запретим следующие переходы: (A7,А1),

Поскольку нижняя граница этого подмножества (А1,A2) меньше, чем подмножества (А1*,A2*), то ребро (А1,A2) включаем в маршрут.

Шаг №3.

Определяем ребро ветвления (таблица 12) и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

Таблица 12 - Определение ребра ветвления

	А1	A3	A4	A5	A6	di
A3	4	0	0(1)	3	0(0)	0
A4	0(3)	0(1)	0	0(0)	1	0
A5	3	4	1	0	0(1)	1
A6	3	1	2	0(1)	0	1
A7	1	3	10	2	0(2)	2
dj	3	1	1	0	0	0

Наибольшая сумма констант приведения будет (0 + 3) = 3 для ребра (A4,А1), следовательно, множество разбивается на два подмножества (A4,А1) и (A4*,А1*).

Нижняя граница гамильтоновых циклов этого подмножества (таблица 13):

Таблица 13 - Нижняя граница гамильтонового цикла

	А1	A3	A4	A5	A6	di
A3	4	0	0	3	0	0
A4	0	0	0	0	1	0
A5	3	4	1	0	0	0
A6	3	1	2	0	0	0
A7	1	3	10	2	0	0
dj	3	0	0	0	0	3

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

После операции приведения сокращенная матрица будет иметь вид (таблица 14):

Таблица 14 - Сокращенная матрица

	A3	A4	A5	A6	di
A3	0	0	3	0	0
A5	4	1	0	0	0
A6	1	2	0	0	0
A7	3	10	2	0	0
dj	1	0	0	0	1



Чтобы исключить подциклы, запретим следующие переходы: (A7,А1), (A7,A4),

Поскольку нижняя граница этого подмножества (A4,А1) меньше, чем подмножества (A4*,А1*), то ребро (A4,А1) включаем в маршрут.

Шаг №4.

Определяем ребро ветвления (таблица 15) и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

Таблица 15 - Определение ребра ветвления

	A3	A4	A5	A6	di
A3	0	0(1)	3	0(0)	0
A5	3	1	0	0(1)	1
A6	0(2)	2	0(2)	0	0
A7	2	10	2	0(2)	2
dj	2	1	2	0	0

Наибольшая сумма констант приведения будет (0 + 2) = 2 для ребра (A6,A3), следовательно, множество разбивается на два подмножества (A6,A3) и (A6*,A3*).

Нижняя граница гамильтоновых циклов этого подмножества (таблица 16):

Таблица 16 - Нижняя граница гамильтонового цикла

	A3	A4	A5	A6	di
A3	0	0	3	0	0
A5	3	1	0	0	0
A6	0	2	0	0	0
A7	2	10	2	0	0
dj	2	0	0	0	2

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

После операции приведения сокращенная матрица будет иметь вид (таблица 17):

Таблица 17 - Сокращенная матрица

	A4	A5	A6	di
A3	0	3	0	0
A5	1	0	0	0
A7	10	2	0	0
dj	0	2	0	2

Чтобы исключить подциклы, запретим следующие переходы: (A7,А1), (A7,A4),

Поскольку нижняя граница этого подмножества (А6,А3) меньше, чем подмножества (A6*,A3*), то ребро (A6,A3) включаем в маршрут.

Шаг №5.

Определяем ребро ветвления (таблица 18) и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

Таблица 18 - Определение ребра ветвления

	A4	A5	A6	di
A3	0(2)	1	0	1
A5	1	0	0(1)	1
A7	10	0(1)	0(0)	0
dj	1	1	0	0

Наибольшая сумма констант приведения будет (1 + 1) = 2 для ребра (A3,A4), следовательно, множество разбивается на два подмножества (A3,A4) и (A3*,A4*).

Нижняя граница гамильтоновых циклов этого подмножества (таблица 19):

Таблица 19 - Нижняя граница гамильтонового цикла

	A4	A5	A6	di
A3	0	1	0	1
A5	1	0	0	0
A7	10	0	0	0
dj	1	0	0	2

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

После операции приведения сокращенная матрица будет иметь вид (таблица 20):

Таблица 20 - Сокращенная матрица

	A5	A6	di
A5	0	0	0
A7	0	0	0
dj	0	0	0

Поскольку нижняя граница этого подмножества (A3,A4) меньше, чем подмножества (A3*,A4*), то ребро (A3,A4) включаем в маршрут.

В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (A5,A6) и (A7,A5).

В результате по дереву ветвлений гамильтонов цикл образуют ребра:

(A2,A7), (A7,A5), (A5,A6), (A6,A3), (A3,A4), (A4,А1), (А1,A2),

Длина маршрута равна F(Mk) = 26.

4. Создание приложения для решения задачи

4.1 Описание алгоритма

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

Рисунок 3 - Алгоритм работы программы

4.2 Разработка программы

Для программной реализации задачи коммивояжера был использован язык программирования Delphi 7. Для оформления формы были использованы такие компоненты как: button (кнопка возврата условия), combobox (отвечает за количество городов), edit (расстояние между городами), label (комментарий), bitbtn (для нахождения пути), memo (вывод условия), opendialog (открытие файлов), savedialog (сохранение файлов), mainmenu (выпадающее меню).

Что же касается программного кода, то было использовано всего две функции для обращения к edit/label через их name в строковом режиме.

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

чтение матрицы из Edit - procedure TForm1.InputMatrix;

нахождение перспективной пары из множества конкурирующих пар - procedure TForm1.Konkurir;

привидение (вычитание минимума элементов) матрицы, нахождение нижней оценки (границы) - procedure TForm1.Etap;

вычеркивание из матрицы строки и столбца, определение новой диагонали - procedure TForm1.DelStrStolb;

нахождение оптимального пути - procedure TForm1.OpredilPuti;

проверка на замкнутость пути - procedure ProverkaIskl;

процедура, описывающая нажатие на кнопку "найти путь" - procedure TForm1.BitBtn1Click;

увеличение/уменьшение количествава edit - procedure TForm1.ComboBox1Change;

процедура открытия файлов - procedure TForm1.N2Click;

процедура сохранения файлов - procedure TForm1.N3Click;

и парочка наипростейших процедур, описывающих выпадающее меню.

В практически всех процедурах используются циклы с параметрами, для перебора всех имеющихся строк и столбцов.

4.3 Тестирование программы

Введем исходные данные в матрицу Edit'ов (рисунок 3):

Рисунок 4 - Ввод исходных данных

Нажимаем кнопку «Найти путь» и наблюдаем результат (рисунок 4):

Рисунок 5 - Результат работы

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

Нужно отметить следующие особенности программы:

ввод производится только целых чисел;

в программе отсутствует защита «от дураков», из - за большого количества компонентов.

4.4 Руководство пользователя

Запустив приложение Kommi.exe, перед Вами откроется окно, предоставляющее возможность решать задачу коммивояжера метод ветвей и границ с максимальным количеством городов, равным 10.

В поле слева, перед вами представлено условие задачи в общем виде, если Вы ни разу не встречались с задачами подобного типа, то есть возможность прочитать теоретический материал, используя меню вкладки «Справка» пункт «Кто такой коммивояжер?». Если Вам необходимо вернуться к условиям задачи, то для этого имеется необходимая кнопка «Вернуться к условиям задачи».

В данной программе есть возможность 2 способами вводить данные:

Ниже, под условием, в сплывающем списке, необходимо выбрать количества городов, справа, вручную вводим соответствующие данные о расстоянии между городами. После ввода и сверки правильности ввода, нажимаем на кнопку «Найти путь». Вследствие чего, мы можем наблюдать, что появилось значение у «Длины пути», соответствующее минимальному значению, а так же «Оптимальный путь», показывающий последовательный обход городов. Введенные данные можно сохранить, что позволит, в дальнейшем не вводить их повторно. Для этого в меню, во вкладке «Файл» выбираем пункт «Сохранить» и выбираем путь. Не забываем вводить имя файла, а так же обратите внимание, что файл должен иметь формат *kom.

Если у Вас уже имеется сохранений файл, то через меню, во вкладке «Файл» выбрать «Открыть». Тем самым, у нас автоматически заполнятся значения ячеек. Дальше нажимаем на кнопку «Найти путь», вследствие чего мы увидим решение данной задачи методом ветвей и границ.

Заключение

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

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

Данная тема, по моему мнению, будет всегда актуальна, так как наш мир все больше и больше становится связанным на отношениях с торговлей, а в этой сфере, задачи, связанные с нахождением кратчайшего пути просто необходимы. Даже мы, того не подозревая, практически каждый день сталкиваемся с данными типами решения задач: к примеру, Вам необходимо добраться до какого то место назначения, Вы непроизвольно будет составлять алгоритм своих действий. На каком автобусе Вам будет быстрее доехать? На какой из улиц, в данное, время есть пробки, и попадете ли Вы в нее? Где выйти и с какой стороны лучше обойти? Эти и многие вопросы начинают тревожить наше сознание. Даже когда Вы пользуетесь GPS, он, по предоставленным ему сведениям (о пробках, о месте нахождения и месте назначения, о погодных условиях и пр.) предоставляет Вам один из самых коротких и удобных, для Вас маршрутов.

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

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

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

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

Список использованных источников

1. Бурков, В.Н., Заложнев, А.Ю., Новиков, Д.А. Теория графов в управлении организационными системами. - Москва: Синтег, 2001.

2. Новиков, Ф.А. Дискретная математика для программистов. - Санкт-Петербург: изд. дом Питер, 2012.

3. Новиков, Ф.А. Дискретная математика: Учебник для вузов. Стандарт третьего поколения. - Санкт-Петербург: изд. дом Питер, 2011.

4. Прилуцкий, М.Х. Математические основы информатики. - Нижний Новгород: Нижег.гос.ун-т, 2000.

5. Партыка, Т.Л., Попов, И.И. Математические методы - Москва: Форум, 2005.

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

...