close

Вход

Забыли?

вход по аккаунту

?

сплошняк

код для вставкиСкачать
 Введение
Гамильтонова задача о путешественнике нередко преобразуется в задачу о коммивояжере. Коммивояжер - не свободно путешествующий турист, а деловой человек, ограниченный временными, денежными или какими-либо другими ресурсами. Гамильтонова задача может стать задачей о коммивояжере, если каждое из ребер снабдить числовой характеристикой. Это может быть километраж, время на дорогу, стоимость билета, расход горючего и т.д. Таким образом, условные характеристики дадут числовой ряд, элементы которого могут быть распределены между ребрами как угодно.
Сейчас решение задачи Коммивояжёре необходимо во многих областях связанных с замкнутыми и при этом жестко связанными по времени системами, такими как: конвейерное производство, многооперационные обрабатывающие комплексы, судовые и железнодорожные погрузочные системы, перевозки грузов по замкнутому маршруту, расчет авиационных линий.
Поэтому данная проблема на современном этапе развития общества имеет не самое последнее по значимости место.
Задача состоит в том, чтобы коммивояжер (торговец) обошел все намеченные города единожды и в таком порядке, чтобы его путь был наименьшим.
Эта задача выбрана нами потому, что её решение интересно с точки зрения программирования и составления алгоритма. Важно нахождение такого алгоритма, который позволит наиболее оптимально решить задачу.
Назначение и область применения разработки.
Задача коммивояжера имеет ряд практических применений. Как следует из самого названия задачи, ее можно использовать для составления маршрута человека, который должен посетить ряд пунктов и, в конце концов, вернуться в исходный пункт. Например, задача коммивояжера
использовалась для составления маршрутов лиц, занимающихся выемкой монет из таксофонов. В этом случае вершинами являются места установки таксофонов и "базовый пункт". Стоимостью каждого ребра (отрезка маршрута) является время в пути между двумя точками (вершинами) на маршруте.
Относительно недавно, года 2-3 назад, интерактивные карты городов были собственностью только специализированных порталов, а теперь, когда на них обратили внимания такие "монстры" как Яндекс и МайлРу, они начали становиться частью нашей повседневной жизни. Помимо базовых, но лежащих на поверхности функций поиска улицы, дома и заведения в картах появился алгоритм поиска кратчайшего пути между двумя заданными точками. И хотя неискушенному пользователю он может показаться достижением высшей математики, мы знаем, что задача поиска кратчайшего пути в графе была решена датчанином Дейкстрой более 50 лет назад. Ставшие популярными карты подтолкнули интерес пользователей Интернет к гео-сервисам.
Вероятно, что следующей ступенью развития будут попытки решения Задачи коммивояжера в реальном времени. Именно в реальном, интернетовском исчислении, поскольку простой пользователь ждать не любит. Исключением будут только сервисы для профессионального пользования. Что представляет собой задача коммивояжера вкратце в условиях современного города? Например: поездка по магазинам бытовой электроники. Покупатель выезжает из дома, объезжает 5 магазинов и возвращается обратно. Что проще? Как правило, человек в этом случае интуитивно использует "жадный" алгоритм, то есть, первая поездка к ближайшему от дома магазину, от него к ближайшему следующему и т.д. Но отметим, что общее количество вариантом, которыми можно переместиться между магазинами составляет факториал 5 равный 120 вариантам, и "жадный" алгоритм может проиграть в расстоянии в среднем 10%-20% оптимальному. Всего 120 вариантов для скромного набора магазинов, тогда как в случае с 10-ю магазинами цифра взлетает до 3.628.800 !
Безусловно, реальная жизнь накладывает различные ограничения на поиск оптимального варианта, но это не означает, что потребность в эффективном решении Задачи коммивояжера за реальное время не будет расти в будущем. Рассмотрим несколько практических приложений задачи.
1. Доставка продуктов в магазины с оптового склада производителя (в этом случае может быть более уместна постановка транспортной задачи - доставка в несколько магазинов с нескольких складов).
2. Доставка бутилированной воды
3. Мониторинг объектов (базовые станции сотовых операторов, нефтяные вышки)
4. Пополнение банкоматов наличными деньгами
5.Сбор сотрудников для доставки вахтовым методом
6.Расклейка афиш
7. И многие другие...
Как правило, мы имеем дело либо с простым перемещением по заданным точкам, либо с развозом груза небольшого формата или веса на транспортном средстве, вмещающем большое количество единиц, что создает предпосылки для применения Задачи коммивояжера. К сугубо специализированным приложениям можно отнести оптимизацию движений сверлильного станка ЧПУ для создания большого количества нерегулярно расположенных отверстий или сварочного робота. В масштабах массового производства это может дать определенный эффект, учитывая трудоемкость подобных операций. Экономический кризис 2008-2009 года безусловно дал творческий импульс для новых эвристических алгоритмов решений Задачи коммивояжера и родственных транспортных оптимизационных задач, но и для новых практических применений этой задачи.
Постановка задачи.
Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения:
* маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение;
* в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом не побывав ни в одном городе дважды.
Для расчета затрат существует матрица условий, содержащая затраты на переход из каждого города в каждый, при этом считается, что можно перейти из любого города в любой, кроме того же самого (в матрице как бы вычеркивается диагональ). Целью решения является нахождения маршрута, удовлетворяющего всем условиям и при этом имеющего минимальную сумму затрат.
Состав выполняемых функций.
Нахождение кратчайшего пути от одного населённого пункта к другому возможен следующий состав выполняемых функций:
* Ввод данных пользователем с клавиатуры - вводится число населённого пункта и вес, соединяющие их;
* Вывод результата - пользователь задаёт начальный и конечный населённый пункт, между которыми необходимо продолжить путь, на экран появляется маршрут.
Требование к входным и выходным данным.
Для рассматриваемой задачи " Нахождение кратчайшего пути от одного населенного пункта к другому" необходимо при реализации задачи предусмотреть следующие условия: при вводе необходимо указать, пункт назначение и пункт источник, а так же вес каждого пути указать
неотрицательными числами, названия самих городов недопустимы.
Относительно задачи коммивояжера уместно сделать два замечания.
Во-первых, в постановке Сij означали расстояния, поэтому они должны быть неотрицательными, т.е. для всех jТ: Сij0; Cjj=∞ (1) (последнее равенство означает запрет на петли в туре), симметричными, т.е. для всех i,j: Сij= Сji. (2)и удовлетворять неравенству треугольника, т.е. для всех:
Сij+ СjkCik(3) Второе замечание касается числа всех возможных туров. В несимметричной задаче коммивояжёре все туры t=(j1,j2,..,jn,j1) и t'=(j1,jn,..,j2,j1) имеют разную длину и должны учитываться оба. Разных туров очевидно (n-1)!.
Необходимо разработать программу с использованием модульного программирования осуществляющую нахождение кратчайшего пути между городами, задаваемым пользователем в процессе работы.
Описание метода решения.
Общее описание метода ветвей и границ организации полного перебора возможностей. Решение задачи о коммивояжере методом ветвей и границ: основная схема. Пусть - конечное множество и - вещественно-значная функция на нем; требуется найти минимум этой функции и элемент множества, на котором этот минимум достигается. Когда имеется та или иная дополнительная информация о множестве, решение этой задачи иногда удается осуществить без полного перебора элементов всего множества M. Но чаще всего полный перебор производить приходится. В этом случае обязательно возникает задача, как лучше перебор организовать.
Метод ветвей и границ - это один из методов организации полного перебора. Он применим не всегда, а только тогда, когда выполняются специфические дополнительные условия на множество M и минимизируемую на нем функцию. В этих условиях можно организовать перебор элементов множества M с целью минимизации функции на этом множестве так: разобьем множество M на части (любым способом) и выберем ту из его частей W1, на которой функция j минимальна; затем разобьем на несколько частей множество W1 и выберем ту из его частей W2, на которой минимальна функция j; затем разобьем W2 на несколько частей и выберем ту из них, где минимальна j, и так далее, пока не придем к какому-либо одноэлементному множеству .Это одноэлементное множество называется рекордом.
Функция j, которой мы при этом выборе пользуемся, называется оценочной. Очевидно, что рекорд не обязан доставлять минимум функции f; однако, вот какая возможность возникает сократить перебор при благоприятных обстоятельствах. Описанный выше процесс построения рекорда состоял из последовательных этапов, на каждом из которых фиксировалось несколько множеств и выбиралось затем одно из них. Пусть - подмножества множества M, возникшие на предпоследнем этапе построения рекорда, и пусть множество оказалось выбранным с помощью оценочной функции. Именно при разбиении и возник рекорд, который сейчас для определенности обозначим через. Согласно сказанному выше, кроме того, по определению оценочной функции. Предположим, что ; тогда для любого элемента m множества M, принадлежащего множеству , будут верны неравенства; это значит, что при полном переборе элементов из M элементы из уже вообще не надо рассматривать. Если же неравенство не будет выполнено, то все элементы из надо последовательно сравнить с найденным рекордом и как только отыщется элемент, дающий меньшее значение оптимизируемой функции, надо им заменить рекорд и продолжить перебор. Последнее действие называется улучшением рекорда.
Слова метод ветвей и границ связаны с естественной графической интерпретацией всего изложенного: строится многоуровневое дерево, на нижнем этаже которого располагаются элементы множества M, на котором ветви ведут к рекорду и его улучшениям и на котором часть ветвей остаются "оборванными", потому что их развитие оказалось нецелесообразным.
Мы рассмотрим сейчас первый из двух запланированных в этом курсе примеров применения метода ветвей и границ - решение задачи о коммивояжере. Вот ее формулировка. Имеется несколько городов, соединенных некоторым образом дорогами с известной длиной; требуется установить, имеется ли путь, двигаясь по которому можно побывать в каждом городе только один раз и при этом вернуться в город, откуда путь был начат ("обход коммивояжера"), и, если таковой путь имеется, установить кратчайший из таких путей. Формализуем условие в терминах теории графов. Города будут вершинами графа, а дороги между городами - ориентированными (направленными) ребрами графа, на каждом из которых задана весовая функция: вес ребра - это длина соответствующей дороги. Путь, который требуется найти, это - ориентированный остовный простой цикл минимального веса в орграфе (напомним: цикл называется остовным, если он проходит по всем вершинам графа; цикл называется простым, если он проходит по каждой своей вершине только один раз; цикл называется ориентированным, если начало каждого последующего ребра совпадает с концом предыдущего; вес цикла - это сумма весов его ребер; наконец, орграф называется полным, если в нем имеются все возможные ребра); такие циклы называются также гамильтоновыми. Очевидно, в полном орграфе циклы указанного выше типа есть. Заметим, что вопрос о наличии в орграфе гамильтонова цикла достаточно рассмотреть как частный случай задачи о коммивояжере для полных орграфов.
Действительно, если данный орграф не является полным, то его можно дополнить до полного недостающими ребрами и каждому из добавленных ребер приписать вес ¥, считая, что ¥ - это "компьютерная бесконечность", т.е. максимальное из всех возможных в рассмотрениях чисел. Если во вновь построенном полном орграфе найти теперь легчайший гамильтонов цикл, то при наличии у него ребер с весом ¥ можно будет говорить, что в данном, исходном графе "цикла коммивояжера" нет. Если же в полном орграфе легчайший гамильтонов цикл окажется конечным по весу, то он и будет искомым циклом в исходном графе. Отсюда следует, что задачу о коммивояжере достаточно решить для полных орграфов с весовой функцией. Сформулируем теперь это в окончательном виде: пусть - полный ориентированный граф и -весовая функция; найти простой остовный ориентированный цикл ("цикл коммивояжера") минимального веса. Пусть конкретный состав множества вершин и - весовая матрица данного орграфа, т.е., причем для любого.
Рассмотрение метода ветвей и границ для решения задачи о коммивояжере удобнее всего проводить на фоне конкретного примера. Пользуясь введенными здесь обозначениями, мы проводим это описание в следующей лекции. Введем некоторые термины. Пусть имеется некоторая числовая матрица. Привести строку этой матрицы означает выделить в строке минимальный элемент (его называют константой приведения) и вычесть его из всех элементов этой строки. Очевидно, в результате в этой строке на месте минимального элемента окажется ноль, а все остальные элементы будут неотрицательными. Аналогичный смысл имеют слова привести столбец матрицы. Слова привести матрицу по строкам означают, что все строки матрицы приводятся. Аналогичный смысл имеют слова привести матрицу по столбцам. Наконец, слова привести матрицу означают, что матрица сначала приводится по строкам, а потом приводится по столбцам. Весом элемента матрицы называют сумму констант приведения матрицы, которая получается из данной матрицы заменой обсуждаемого элемента на ¥. Следовательно, слова самый тяжелый нуль в матрице означают, что в матрице подсчитан вес каждого нуля, а затем фиксирован нуль с максимальным весом. Приступим теперь к описанию метода ветвей и границ для решения задачи о коммивояжере.
Первый шаг. Фиксируем множество всех обходов коммивояжера (т.е. всех простых ориентированных остовных циклов). Поскольку граф - полный, это множество заведомо не пусто. Сопоставим ему число, которое будет играть роль значения на этом множестве оценочной функции: это число равно сумме констант приведения данной матрицы весов ребер графа. Если множество всех обходов коммивояжера обозначить через G, то сумму констант приведения матрицы весов обозначим через j(G). Приведенную матрицу весов данного графа следует запомнить; обозначим ее через M1; таким образом, итог первого шага: множеству G всех обходов коммивояжера сопоставлено число j(G) и матрица M1.
Второй шаг. Выберем в матрице M1 самый тяжелый нуль; пусть он стоит в клетке ; фиксируем ребро графа и разделим множество G на две части: на часть , состоящую из обходов, которые проходят через ребро , и на часть , состоящую из обходов, которые не проходят через ребро . Сопоставим множеству следующую матрицу M1,1: в матрице M1 заменим на ¥ число в клетке . Затем в полученной матрице вычеркнем строку номер i и столбец номер j, причем у оставшихся строк и столбцов сохраним их исходные номера. Наконец, приведем эту последнюю матрицу и запомним сумму констант приведения. Полученная приведенная матрица и будет матрицей M1,1; только что запомненную сумму констант приведения прибавим к j(G) и результат, обозначаемый в дальнейшем через j(), сопоставим множеству .
Теперь множеству тоже сопоставим некую матрицу M1,2. Для этого в матрице M1 заменим на ¥ число в клетке и полученную в результате матрицу приведем. Сумму констант приведения запомним, а полученную матрицу обозначим через M1,2. Прибавим запомненную сумму констант приведения к числу j(G) и полученное число, обозначаемое в дальнейшем через j(), сопоставим множеству .Теперь выберем между множествами и то, на котором минимальна функция j (т.е. то из множеств, которому соответствует меньшее из чисел j() и j().
Заметим теперь, что в проведенных рассуждениях использовался в качестве исходного только один фактический объект - приведенная матрица весов данного орграфа. По ней было выделено определенное ребро графа и были построены новые матрицы, к которым, конечно, можно все то же самое применить. При каждом таком повторном применении будет фиксироваться очередное ребро графа. Условимся о следующем действии: перед тем, как в очередной матрице вычеркнуть строку и столбец, в ней надо заменить на ¥ числа во всех тех клетках, которые соответствуют ребрам, заведомо не принадлежащим тем гамильтоновым циклам, которые проходят через уже отобранные ранее ребра. К выбранному множеству с сопоставленными ему матрицей и числом j повторим все то же самое и так далее, пока это возможно. Доказывается, что в результате получится множество, состоящее из единственного обхода коммивояжера, вес которого равен очередному значению функции j; таким образом, оказываются выполненными все условия, обсуждавшийся при описании метода ветвей и границ.
После этого осуществляется улучшение рекорда вплоть до получения окончательного ответа.
Алгоритм решения
В курсовой работе для решения задачи о коммивояжере применяется метод ветвей и границ. В сущности, это полный перебор решений, который оптимизируется за счет того, что при переборе вариантов по определенным признакам отсекаются неоптимальные множества перебора. Так как количество вершин от уровня к уровню возрастает в факториальной прогрессии, то отсечение вершин верхних уровней значительно сокращает общее число перебираемых вариантов.
Рисунок 1. Укрупнённый алгоритм.
Рисунок 2:Подробный алгоритм кнопки СmdComp.
Описание укрупнённого алгоритма:
1.В типовом процессе "ввод данных" мы вводим в программу количество рёбер, назначение веса и указываем, как они соединены.
2. В типовом процессе "выбор пункта назначения" выбираем количество ребер, которые будут участвовать в работе программы, а так же выбираем начальный и конечный пункт назначения. 3.В типовом процессе "вывод данных" выводятся результаты выполнения работы программы.
Обоснование выбора средств разработки.
При решении поставленной задачи оптимально использовать для представления информационных материалов язык Delphi, который является языком высокого уровня и позволяет быстро и эффективно создавать приложения.
Для реализации моей программы была выбрана система программирования Delphi версии 7 фирмы Enterprise (Borland), так как она предоставляет наиболее широкие возможности для программирования приложений ОС Windows.
Delphi - это продукт Borland International для быстрого создания приложений. Высокопроизводительный инструмент визуального построения приложений включает в себя настоящий компилятор кода и предоставляет средства визуального программирования.
Прежде всего Delphi предназначен для профессиональных разработчиков, желающих очень быстро разрабатывать приложения в архитектуре клиент-сервер. Delphi производит небольшие по размерам (до 15-30 Кбайт) высокоэффективные исполняемые модули (.exe и .dll), поэтому в Delphi должны быть прежде всего заинтересованы те, кто разрабатывает продукты на продажу. С другой стороны небольшие по размерам и быстро исполняемые модули означают, что требования к клиентским рабочим местам существенно снижаются - это имеет немаловажное значение и для конечных пользователей.
Преимущества Delphi по сравнению с аналогичными программными продуктами.
- быстрота разработки приложения;
- высокая производительность разработанного приложения;
- низкие требования разработанного приложения к ресурсам компьютера;
- наращиваемость за счет встраивания новых компонент и инструментов в среду Delphi;
- возможность разработки новых компонент и инструментов собственными средствами Delphi (существующие компоненты и инструменты доступны в исходных кодах);
- удачная проработка иерархии объектов.
Система программирования Delphi рассчитана на программирование различных приложений и предоставляет большое количество компонентов для этого.
Технические характеристики компьютера: Pentium 2 и выше; объем оперативной памяти не менее 128 мб, жесткий диск объемом не менее 1 гб. Именно эти параметры создают условия для полноценной работы Borland Delphi 7 программ созданных в этой среде. Дополнительных устройств не требуется.
Описание программных модулей
Краткое описание модулей, используемых в программе.
Процедура cmdAdd:
Назначение: Добавляет ребра графа.
Входные данные: нет.
Выходные данные: нет.
Не вызывает никаких процедур.
Вызывается из основной программы.
Процедура Process:
Назначение: Выполняется поиск минимального веса ребра маршрута и вывод результата.
Входные данные:
_weight(real) вес ребра вводится с клавиатуры.
VertexSrc(Integer) пункт источник, откуда начинается путь.
VertexDest(Integer ) пункт назначения, где кончается путь.
Выходные данные: Res(real) результат минимального маршрута.
Sum(real) сумма минимальной стоимости маршрута
Вызывается процедура process
Вызывается из основной программы.
Процедура cmdDel:
Назначение: Удаление ребра графа.
Входные данные: нет. Выходные данные: нет.
Не вызывает никаких процедур.
Вызывается из основной программы.
Кодирование должно быть простым. Необычное кодирование (например, использование скрытых возможностей машины) часто препятствует отладке программы и затрудняет ее использование другими программистами. Программа должна быть по возможности универсальной. Универсальные программы обеспечивают независимость программы от конкретного набора данных. Например, универсальная программа использует в качестве параметров переменные, а не константы, обрабатывает вырожденные случаи и т. д. Универсальность программы экономит время по дальнейшей работы над ней и обеспечивает широкие возможности по использованию. Входные форматы должны быть разработаны с учетом максимального удобства для пользователя и минимальной возможности ошибок. Идентификаторы переменных и форматы данных привычные для пользователя помогут избежать ошибок и облегчат использование программ.
При написании программ не следует забывать о хорошем стиле программирования. После заголовка процедуры или функции записывается комментарий, содержащий поясняющий текст, а именно назначение подпрограммы; перечень и назначение формальных параметров, их тип. Комментариями должны быть снабжены и основные смысловые блоки программы или подпрограммы. Для облегчения чтения текста программы отдельные операторы программы записываются с отступом.
Тестирование программы.
Разработанное программное средство было протестировано.
Ввод данных:
Дан граф с 6 вершинами, нужно рассчитать длину маршрута от вершины 1 до 5:
1) Из вершины 1 можно попасть в 2, 3 и 6 , выбираем минимальный вес между рёбрами, это 9 (маршрут 1 - 3).
2) Из вершины 3 есть пути в 6 и 4, выбираем минимальный вес, это 2 ( маршрут 3 - 6).
3) Из вершины 6 можно попасть только в 5 вершину, вес ребра равен 9.
4) Складываем минимальные пути между рёбер 9+2+9=20, следовательно минимальный путь между 1 и 5 = 20.
Вывод результата: Ввели в программу данные (Начало , конец , вес , пункт назначения, пункт источник и кол-во вершин) и выводим результат.
Ответ равен 20, ручной тест совпал с результатами программы, следовательно программа составлена правильно.
Заключение
Для курсового проекта было предложено следующее задание "Реализация задачи коммивояжера методом ветвей и границ". Для его реализации были разработаны алгоритмы, на основании которых была разработана программа на языке программирования Delphi 7. Отладка программы производилась на персональном компьютере. Внедрение данного программного продукта облегчит работу многим как частным так государственным предприятиям, где необходимо проводить расчеты, связанные с транспортными перевозками.
Литература.
1. Акимов О.Е Дискретная математика. Логика. Графы. Группы,-М,: 2001г.
2. Акулич И. Л. Математическое программирование в примерах и задачах.-М: Высшая школа,1986г.
3. Архангельский А.Я. Программирование в Delphi 7.-М.:ООО "Бином - Пресс", 2003г.
4. Мамиконов А.Г. "Основы построения АСУ", - М, :"Высшая школа" - 1999г.
5. Липатов Е. П. Теория графов и её применения. - М., Знание, 1999г.
6. О. Оре Графы и их применение. Пер. с англ. под ред. И.М. Яглома. - М., "Мир", 2001г.
7. Хемди А. Таха Введение в исследование операций, 7-е издание. С.-Питербург: Питер, 2002г.
8. Фомин Г.П. Математические методы и модели в коммерческой деятельности: Учебник.- 2-ое издание., перераб. и доп.-М.: Финансы и статистика, 2005г. 9. ГОСТ 24.301-80 - ГОСТ 24.303-80. ГОСТ 24.401-80, ГОСТ 24.402-80 Система технической документации на АСУ. М.: Издательство стандартов, 1980.
10. СТП.001.001. Учебная документация. Правила присвоения обозначений и оформления, Белебей, БМСТ, 1993. 11. http://epsilon.narod.ru - сайт с учебниками по Delphi 7.
12. http://window.edu.ru/ - единое окно доступа к образовательным ресурсам, имеет бесплатные учебники для темы курсовой работы.
2
Документ
Категория
Рефераты
Просмотров
162
Размер файла
275 Кб
Теги
сплошняк
1/--страниц
Пожаловаться на содержимое документа