Отыскание кратчайшего пути - Курсовая работа

Задача отыскания на графе (как ориентированном, так и неориентированном) кратчайшего пути имеет многочисленные практические приложения. С решением подобной задачи приходится встречаться в технике связи, на транспорте, в микроэлектронике и т.д. Самыми знаменитыми задачами в теории графов являются: задача о Кенигсбергских мостах, задача о трех домах и трех колодцах, задача о четырех красках. Повлияло на этот процесс запросы новых областей: теории игр и программирования, теории передачи сообщений, электрических сетей и контактных цепей, а также проблем психологии и биологии и многое другое. В данной работе я постараюсь раскрыть понятие графа, описать некоторые определения, алгоритмы решения задач, а также уделить особое внимание задачам коммивояжера, решить их как математически, так и программно.Обычно ее относят к топологии (потому что во многих случаях рассматриваются лишь топологические свойства графов), однако она пересекается со многими разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин. Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок. Одним из первых результатов в теории графов явился критерий существования обхода всех ребер графа без повторений, полученный Л. Вот пересказ отрывка из письма Эйлера от 13 марта 1736 году: ”Мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто 7 мостов. Рассмотрев эту задачу, в 1736 году Эйлер доказал, что это невозможно, причем он рассмотрел более общую задачу: какие местности, разделенные рукавами рек и соединенные мостами, возможно обойти, побывав на каждом мосту ровно один раз, а какие невозможно.В частности в монографии Гудман, Хидетниеми, 1981 сказано «В программистском мире нет единого мнения о том, какой из двух терминов "граф" или "сеть". Кружки называются вершинами графа, линии со стрелками - дугами, без стрелок - ребрами. Граф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным; граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным. Подграфом называется часть графа, образованная подмножеством вершин вместе со всеми ребрами (дугами), соединяющими вершины из этого множества. Смежные вершины называются граничными вершинами соответствующего ребра (дуги), а это ребро (дуга) - инцидентным соответствующим вершинам.В этом случае ребра графа могут представлять собой кривые линии, дуги или ломаные линии, состоящие из отрезков прямых. Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скорость выполнения операций над графами. Если в клетке i, j (i - строка, j - столбец) установлено значение пусто (как правило, это очень большая величина или величина, которой заведомо не может равняться вес ребра), то дуги, начинающейся в вершине i и кончающейся в вершине j, нет. Е сопоставимо V2 (где Е - количество дуг), этот способ хранения графа наиболее выгоден, т.к. его очень просто реализовывать и память будет заполнена "нужными" значениями. Но если это условие не выполняется, например, вершин до 10000 и ребер до 1000, то нам понадобиться ?2 * 100000000 / 10242 Мбайт памяти (по 2 байта на ячейку), что примерно равно 190 Мбайт, памяти.Задача коммивояжера (коммивояжер - разъездной сбытовой посредник) - одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешевый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Существует несколько частных случаев общей постановки задачи, в частности геометрическая задача коммивояжера (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости), треугольная задача коммивояжера (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжера.Для практической реализации идеи метода ветвей и границ применительно к задаче коммивояжера нужно найти метод определения нижних границ подмножества и разбиения множества гамильтоновых контуров на подмножества (ветвление). Определение нижних границ базируется на том утверждении, что если ко всем элементам i-й строки или j-го столбца матрицы C прибавить или отнять число , то задача останется эквивалентной прежней, то есть оптимальность маршрута коммивояжера не изменится, а длина любого гамильтонова контура изменится на данную величину .Коммивояжер хочет объехать N городов и затем вернуться в начальный город, расстояния между которыми заданы.Определяем ребро ветвления (таблица 6) и разобьем все множество маршрутов относительно этого

Содержание

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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