WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 13 |
3 Е.А. Берзин An Элементарные решения Сk1 = Cln неэлементарных задач на Сni графах Al Сil Ai Сi2 Сki A2 С21 Сk2 С1k Ak A1 Тверь 2005 4 Федеральное агентство по образованию Тверской государственный технический университет Е.А. Берзин ЭЛЕМЕНТАРНЫЕ РЕШЕНИЯ НЕЭЛЕМЕНТАРНЫХ ЗАДАЧ НА ГРАФАХ Учебное пособие Тверь 2005 5 УДК 519.8 ББК Берзин Е.А. Элементарные решения неэлементарных задач на графах / Под ред. А.Н. Кудинова. Тверь: ТГТУ, 2005. 136 с.

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

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

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

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

Предназначено для использования в учебном процессе по ряду учебных дисциплин кафедр «Информационные системы», «Автомобильный транспорт» и «Электроснабжение и электротехника».

Рецензенты: заведующий кафедрой математического моделирования, Заслуженный деятель науки РФ, доктор физико-математических наук, профессор А.Н. Кудинов; заведующий кафедрой вычислительной техники и математического моделирования агросистем, доктор технических наук, профессор В.Р. Гриднев.

ISBN 5-7995-0293-© Тверской государственный технический университет, ПРЕДИСЛОВИЕ Разработанные в книге методы и алгоритмы, как правило, не имеют строгих формальных обоснований, а базируются на неформальном подходе, в рамках которого автор, учитывая конкретную физическую интерпретацию задачи, предлагает нестандартные решения задач, успешно конкурирующие с известными методами. К таким методам с полным правом может быть отнесён, например, эстафетный метод решения задачи о кратчайшем пути на графе. Этот метод являет собой довольно редкий пример того, как эвристический подход приводит к точному решению сложной задачи.

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

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

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

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

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

А.Н. Кудинов ПРИНЯТЫЕ ОБОЗНАЧЕНИЯ G = (A, M ) – граф с n = A вершинами и m = M дугами;

A ={Aj} – множество n вершин графа G ;

n M = {(i, j)} – множество дуг графа G ;

m (i, j) -дуга с началом в вершине Ai и концом в вершине Aj ;

cij - длина дуги (в соответствующих единицах);

= m / n(n -1) - коэффициент полноты матрицы c;

k,l = k,K, j,Kl - путь (маршрут), проходящий через вершины с указанными номерами;

k,l - кратчайший путь от вершины Ak до вершины Al ;

Lk,l = L(k,l ) - длина пути от вершины Ak до вершины Al ;

Э(kj) – величина энергозатрат при движении по маршруту kj ;

– знак включения;

- знак принадлежности;

– знак следования;

– квантор существования («существует»);

- квантор всеобщности («каждый», «всякий»);

f – знак предпочтения (доминирования).

Здесь нужно, чтоб душа была тверда, Здесь страх не должен подавать совета, Здесь никогда не может интуиция одна Дать ключ к раскрытию научного секрета… А. Данте ВВЕДЕНИЕ Появление термина «граф» как общепринятого понятия в математике связывают с появлением монографии Д. Кёнига1, где графы рассматриваются в абстрактной форме как некоторые математические объекты. Однако о появлении теории графов стало возможным говорить только с появлением достаточно общих методов, изложенных в фундаментальной работе Пойа2. Одним из важных и общих методов в теории графов является геометрическая теория транспортных сетей, созданная в 1956 – 1957 гг. Фордом, Фалкерсоном и Гейлом. Эта теория позволяет решать не только транспортные, но и множество других задач из области электрических сетей, химии, социологии и других предметных областей.



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

Разработка достаточно эффективных методов построения кратчайшего пути на графе; решение классической и обобщенной задач коммивояжера при большом числе вершин графа ( n 1000 ); поиск маршрута с максимальной пропускной способностью и оценка пропускной способности сети; поиск специальных точек на графе составляют содержание и цель работы.

Во разделе 2 (в разделе 1 содержится необходимый минимум сведений из теории графов) приведен эффективный алгоритм построения кратчайших маршрутов на графе (эстафетный метод). Оценка сверху для Knig D. Theorie der Еndlichen und Unendlichen Graphen. Leipzig, 1936.

Polya G. Kombinatorische Anzahlbestimmungen fr Gruppen // Graphen und chemische Verbindungen. Acta Math. 68 (1937). Р. 145.

требуемого числа операций ограничена полиномом третьей степени, при этом решение – точное.

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

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

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

В разделе 5 рассмотрен иной подход к решению задач коммивояжера.

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

Раздел 6 посвящен новому решению задачи о пропускной способности сети.

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

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

1. НЕКОТОРЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ 1.1. Основные понятия и определения Теория графов, как и любая математическая теория, использует некоторую символику и понятия, которые применяются при проведении исследований. Центральным понятием теории графов является понятие графа, как некоторой схемы, состоящей из множества A ={Aj} вершин n (узлов), соединённых между собой множеством M = {(i, j)} некоторых m линий (дуг (i, j)) [1; 2]. Граф G = (A, M ) – это схематическое изображение некоторого физического объекта (участка дорожной сети, электросхемы и т.п.). С формальных позиций, граф – это отображение множества A «в себя» (т.е. в множество A ), осуществляемое по некоторому закону (с помощью множества дуг M ). Граф дорожной сети или, например, сети передачи данных представлен на рис. 1. В первом случае под вершиной Ai имеется в виду некий населенный пункт (город, деревня под номером i ), во втором – некий узел связи (узел коммутации – УК, узел-источник – УИ Ai, узел-приёмник – УП Aj ).

Две вершины, связанные одной дугой (i, j), называются смежными.

При этом начало дуги связано с источником Ai, а её конец – с приёмником Aj. В зависимости от физической природы графа каждой его дуге приписывается некоторый вес cij : в первом случае это длина дуги (i, j), связывающей вершину Ai с Aj ; во втором – длительность передачи сигнала от узла-источника Ai до узла-приёмника Aj. Направление, по которому возможно движение (передача сигнала) по данной дуге, указывается стрелкой (см. рис. 1).

Граф с направленными дугами называется ориентированным. В неориентированном графе стрелки не указываются (ребро – пара дуг сij = c ).

ji Для проведения формальных исследований удобна матричная форма представления графа с помощью матрицы смежности. Её смысл ясен из матрицы c = cij, представляющей тот же граф в табличном виде (табл. 1).





Каждая вершина графа представляется в виде двух составляющих:

узла-источника Ai и узла-приёмника Aj, при этом узлу-источнику Ai соответствует i -я строка матрицы c, узлу-приёмнику Aj – j -й столбец этой же матрицы (табл. 1).

Согласно [1], путём (маршрутом) на графе G = (A, M ) будем называть такую последовательность соединённых дуг (i, j), что конец каждой предыдущей дуги совпадает с началом следующей.

c1,5 = c3,1 = 5 c2,1 = x c2,3 = Рис. 1. Граф транспортной сети Таблица j = 1 2 3 4 5 k = 1 3 6 2 13 3 5 4 3 5 6 4 Путь от вершины Ak к вершине Al kl – это упорядоченная последовательность (кортеж) дуг (или номеров вершин) с началом пути в узле-источнике Ak и концом пути в узле-приёмнике Al ( k,l – номера концевых (граничных) вершин (пунктов) маршрута kl ):

kl = (k,i),K,( j,l), или kl = k,i,K, j,l, (1.1) где (k,i), ( j,l) – начальная и конечная дуги маршрута kl (граничные, концевые дуги).

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

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

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

Если на месте некоторого элемента cij в матрице с нет никакой записи, то считается, что от узла-источника Ai до узла-приемника Aj нет прямой связи (сij = ). Указанные элементы в расчётах не используются.

Никаких записей не делается также на месте элементов cij при i = j, однако cii = 0.

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

Длина пути равна сумме длин дуг его составляющих и вычисляется по формуле Lk,l = L(kl ) = (1.2) c, ij (i, j)kl где запись (i, j) kl означает, что суммируются длины дуг, образующих данный путь kl. Например, из табл. 1 для 1,3 = 1,4,6,3 имеем 0 L1,3 = L(1,3) = c1,4 + c4,6 + c6,3 = 3 + 2 + 3 = 8, где 1,3 – кратчайший маршрут от пункта A1 к A3.

Если между любыми двумя вершинами существует хотя бы один путь, то граф (A, M ) сильно связан. Минимальное число дуг, требуемое для обеспечения сильной связности графа, равно n [3].

Граф (A, M ) называется полным, если любые две вершины соединены хотя бы в одном направлении [1]:

(i, j) M ( j,i) M, (1.3) т.е. если дуги (i, j) не существует, то имеется дуга ( j,i).

Примечание. Понятие «полный граф», однако, не будем отождествлять с равенством единице коэффициента полноты матрицы c, который вводится в [3] как доля числа дуг графа m от их максимально возможного количества:

= m / n(n -1), =12/ 6 5 = 0,4 (табл. 1).

Согласно (1.3) граф на рис. 1 не является полным, а коэффициент полноты =0,4 (< 1), однако данный граф сильно связан.

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

2. ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ НА ГРАФЕ 2.1. Постановка задачи На графе (A, M ) требуется найти такую последовательность номеров вершин, соединяющую вершины Ak и Al (путь kl (1.1)), при которой длина пути (1.2) будет минимальной ( kl ).

В 1956 г. Л. Форд [4] предложил алгоритм решения задачи поиска кратчайшего маршрута на графе. Поскольку запись исходной информации в форме графа (рис. 1) мало приемлема для использования ЭВМ, то в [4] отмечается возможность решения задач построения кратчайшего маршрута большого размера «вручную». Однако возможности человека также существенно ограничены. В [4] оценка по требуемым вычислительным затратам не приводится.

В [5] рассматривается матричный подход к решению задачи поиска кратчайшего маршрута. При этом в основу решения положено использование двойственного симплексного метода решения задачи линейного программирования (ЛП), поэтому естественным является вопрос, задаваемый автором в [1; c. 81]: «Не будет ли это стрельбой из пушки по воробьям».

Известны и другие подходы к решению задачи поиска кратчайшего маршрута, однако и там остаются нерешёнными некоторые вопросы, особенно в задачах больших размеров [6].

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

Формальную постановку будет удобно записать в комбинаторном виде как задачу минимизации целевой функции (2.1) на множестве нескалярных переменных k,l :

Lk,l = L(k,l ) = (2.1) c min, ij k,l (i, j)k,l k,l rkl,r =1;n = { }, где r - возможное количество номеров промежуточных вершин в кортеже k,l (r = 0,n - 2).

Упрощение записи формальной постановки задачи по сравнению с её записью в форме задачи математического программирования [5] получено за счёт перехода от скалярных переменных к более сложным нескалярным r переменным, что позволяет предложить эффективный метод k,l решения поставленной задачи.

2.2. Эстафетный метод построения кратчайшего пути на графе В основу эстафетного метода [3] положена следующая физическая интерпретация поиска кратчайшего маршрута от вершины Ak к Al.

Pages:     || 2 | 3 | 4 | 5 |   ...   | 13 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.