Федеральное агентство по образованиюГОУ ВПО “Уральский государственный технический университет – УПИ”Кафедра “Информационные системы и технологии”“Задача коммивояжера” Курсовая работа на тему: “Теория графов в решении задач теории систем” Дисциплина: ”Теория информационных систем” Семестр VII Вариант № 17 Студент: Номер зачетной книжки: Группа: Преподаватель: Ступин Ю.В. 17458724 ИТ – 44019д Александров О.Е. Екатеринбург 2007 Содержание. Введение. 3Теория о теории графов. 3Задача коммивояжера. 4Генетический алгоритм. 4Метод ветвей и границ. 5Метод простого перебора. 7Заключение. 8Литература. 9 Введение. Тема курсового проекта звучит так: ”Теория графов в решении задач теории систем”. А задача взятая для рассмотрения: ”Задача коммивояжера”. По этому в начале поговорим о теории графов, приведем немного теории. Затем будут рассмотрены основные методы решения задач такого типа. Одним таким методом, который для нас покажется наиболее удобным, мы решим какую-нибудь конкретную задачу. И в итоге все проделанной работы, необходимо получить дееспособный и реализуемый (на любом языке программирования) алгоритм решения задач такого типа. ^ Теория о теории графов. Теория графов - раздел дискретной математики, изучающий свойства графов. Графом называется совокупность конечного числа точек, называемых вершинами графа, и попарно соединяющих некоторые из этих вершин линий, называемых ребрами или дугами графа. Или по другому: графом называется непустое множество точек (вершин) и отрезков (ребер), оба конца которых принадлежат заданному множеству точек.Несколько сухих определений, которые помогут при решении поставленной задачи: Вершины графа, которые не принадлежат ни одному ребру, называются изолированными. Граф, состоящий только из изолированных вершин, называется нуль - графом. Граф, в котором каждая пара вершин соединена ребром, называется полным. Степенью вершины называется число ребер, которым принадлежит вершина. Граф, степени всех k вершин которого одинаковы, называется однородным графом степени k. Граф, который можно представить на плоскости в таком виде, когда его ребра пересекаются только в вершинах, называется плоским. Циклом называется путь, в котором совпадают начальная и конечная точка. Простым циклом называется цикл, не проходящий ни через одну из вершин графа более одного раза. Гамильтонов цикл - простой цикл, содержащий все вершины графа ровно по одному разу. Длиной пути, проложенного на цикле, называется число ребер этого пути. Две вершины A и B в графе называются связными (несвязными), если в нем существует (не существует) путь, ведущий из A в B. Деревом называется связный граф, не содержащий циклов.^ Задача коммивояжера. Задача коммивояжёра (коммивояжёр - бродячий торговец) заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т.п.) и соответствующие матрицы расстояний (стоимости и т.п.). Как правило, указывается, что маршрут должен проходить через каждый город только один раз, в таком случае выбор осуществляется среди гамильтоновых циклов. Если считать города вершинами графа, а дороги – его дугами, то требование нахождения минимального пути, проходящего один и только один раз через каждый город, и возвращения обратно, можно рассматривать как нахождение на графе гамильтонова контура минимальной длины. Простейшие методы решения задачи коммивояжёра: полный лексический перебор, жадные алгоритмы. На практике применяются различные модификации более эффективных методов: метод ветвей и границ и метод генетических алгоритмов, а так же алгоритм муравьиной колонии. Все эффективные (сокращающие полный перебор) методы решения задачи коммивояжёра - методы эвристические. В большинстве эвристических методов находится не самый эффективный маршрут, а приближённое решение. Задача коммивояжёра есть NP-полная задача. Часто на ней проводят обкатку новых подходов к эвристическому сокращению полного перебора. Жадные алгоритмы. Жадный алгоритм — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным. Но локально оптимальное решение не гарантирует правильность конечного результата. По этому остановимся на методах полного перебора, генетического алгоритмов и методе ветвей и границ.^ Генетический алгоритм. Генетический алгоритм — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путем последовательного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания» (crossover), который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе. Разработка генетического алгоритма начинается с конструирования двоичной хромосомы, представляющей возможные решения этой задачи. Традиционно генетические алгоритмы используют для этого двоичные строки фиксированной длины. Реализация генетического алгоритма предполагает задание функции приспособленности, или фитнес-функции (fitness function). Эта функция получает на вход двоичную хромосому и возвращает число, показывающее, насколько хороша эта хромосома. Последний этап - мутация (mutation). Даже для больших популяций может оказаться, что не все биты генетического материала в ней представлены. Например, если первый бит у всех хромосом равен 0, то кроссинговер никогда не породит решение с 1 в первом бите. Мутация предназначена для того, чтобы избежать таких ситуаций и увеличить вариабельность популяции. Частота мутации обычно очень низкая. Мутация и кроссинговер могут порождать новые решения, которые никогда не встречались в предыдущих поколениях. Для оценки качества этих решений вычисляется фитнес-функция. На этом построение нового поколения решений заканчивается. В приложении на первой странице показан пример решения задачи коммивояжера с помощью генетического алгоритма. В этом решении сделано два допущения: Рассматриваются только 5 поколений; Мутация происходит в каждом поколении в любом бите любой хромосомы.^ Метод ветвей и границ. Для практической реализации идеи метода ветвей и границ применительно к задаче коммивояжера нужно найти метод определения нижних границ подмножества и разбиения множества гамильтоновых контуров на подмножества (ветвление). Определение нижних границ базируется на том утверждении, что если ко всем элементам i-й строки или j-го столбца матрицы C прибавить или отнять число , то задача останется эквивалентной прежней, то есть оптимальность маршрута коммивояжера не изменится, а длина любого гамильтонова контура изменится на данную величину .Алгоритм Литтла для решения задачи коммивояжера можно сформулировать в виде следующих правил: 1. Находим в каждой строке матрицы минимальный элемент и вычитаем его из всех элементов соответствующей строки. Получим матрицу, приведенную по строкам, с элементами. 2. Если в матрице , приведенной по строкам, окажутся столбцы, не содержащие нуля, то приводим ее по столбцам. Для этого в каждом столбце матрицы выбираем минимальный элемент , и вычитаем его из всех элементов соответствующего столбца. Получим матрицу, каждая строка и столбец, которой содержит хотя бы один нуль. Такая матрица называется приведенной по строкам и столбцам. 3. Суммируем элементы и , получим константу приведения, которая будет нижней границей множества всех допустимых гамильтоновых контуров, то есть . 4. Находим степени нулей для приведенной по строкам и столбцам матрицы. Для этого мысленно нули в матице заменяем на знак «- и находим сумму минимальных элементов строки и столбца, соответствующих этому нулю. Записываем ее в правом верхнем углу клетки:. 5. Выбираем дугу , для которой степень нулевого элемента достигает максимального значения. 6. Разбиваем множество всех гамильтоновых контуров на два подмножества и . Подмножество гамильтоновых контуров содержит дугу , - ее не содержит. Для получения матрицы контуров , включающих дугу , вычеркиваем в матрице строку и столбец . Чтобы не допустить образования негамильтонова контура, заменим симметричный элемент на знак «- 7. Приводим матрицу гамильтоновых контуров . Пусть - константа ее приведения. Тогда нижняя граница множества определится так:. 8. Находим множество гамильтоновых контуров , не включающих дугу . Исключение дуги достигается заменой элемента в матрице на ∞. 9. Делаем приведение матрицы гамильтоновых контуров . Пусть - константа ее приведения. Нижняя граница множества определится так:. 10. Сравниваем нижние границы подмножества гамильтоновых контуров и . Если , то дальнейшему ветвлению в первую очередь подлежит множество . Если же , то разбиению подлежит множество . Процесс разбиения множеств на подмножества сопровождается построением дерева ветвлений. 11. Если в результате ветвлений получаем матрицу , то определяем полученный ветвлением гамильтонов контур и его длину. 12. Сравниваем длину гамильтонова контура с нижними границами оборванных ветвей. Если длина контура не превышает их нижних границ, то задача решена. В противном случае развиваем ветви подмножеств с нижней границей, меньшей полученного контура, до тех пор, пока не получим маршрут с меньшей длиной или не убедимся, что такого не существует. На стр.2 приложения приведен пример решения задачи с использованием метода ветвей и границ.^ Метод простого перебора. Он прост по определению, находятся все возможные варианты маршрута, рассчитывается длинна каждого. Затем результаты сравниваются, и находится наилучший. На стр.3 приложения приведен пример решения. Это самый трудоемкий, но в тоже время самый достоверный способ решения поставленной задачи. Поэтому для реализации был выбран именно этот способ. Заключение. В ходе работы были рассмотрены методики решения задачи коммивояжера. Для реализации был выбран метод простого перебора, как самый надежный и достоверный. Единственный его недостаток заключается в том, что с ростом числа городов количество вариантов маршрута увеличивается по закону факториала, то есть при 4 городах количество вариантов маршрута равно 24, а при 8 городах – 40320 вариантов. Но для компьютера (а мы для него и писали программу) это вполне выполнимая задача. Литература. О. Е. Акимов «Дискретная математика. Логика, группы, графы», Москва, 2003, 376 с., ил., изд. дом «Лаборатория базовых знаний».http://www.lalena.com/ai/tsphttp://ru.wikipedia.org Ф. А. Новиков «Дискретная математика для программистов» С.-Петербург, 2002 г. 304 с., ил., изд. дом «Питер».