WWW.DISSERS.RU

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

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


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

Несмотря на эвристическую основу эстафетного метода, анализируя его вычислительную схему, можно убедиться, что на каждом шаге процесса она приводит, по крайней мере, к одному кратчайшему маршруту. Действительно, из табл. 1 видно, что от УИ A1 никакой другой маршрут не может быть короче, чем 1,4 = 1;4 = 3. На шаге t = 2 оставшиеся гонцы достигнут пунктов A5, Aсоответственно в моменты времени 6 и 8, а гонцы, стартовавшие из A4 с задержкой в L1,4 = 3 ед., придут соответственно к тем же пунктам в моменты 3 + 3 = 6 и 3 + 2 = 5, при этом первым прибудет лидер Л4,6 из группы i = 4 в пункт A6, т.к. из всех указанных времен его время минимально (численно оно равно длине очередного кратчайшего 0 маршрута L1,6 = 5, 1,6 = 1,4,6 ). Вводя понятие «лидер», мы получаем возможность сократить количество элементарных операций и число записей (табл. 7; t = 2 ). Удаляя из табл. 1 столбец, соответствующий концевому пункту Al найденного кратчайшего маршрута, сокращаем объём вычислений в дальнейшем.

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

Предполагается, что матрица с не содержит отрицательных элементов.

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

Получим оценку числа элементарных операций сверху, полагая, что матрица c заполнена полностью, кроме элементов главной диагонали ( =1). Будем также считать, что строится всё множество кратчайших маршрутов и что на каждой из n -1 итераций определяется только один кратчайший маршрут.

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

Общее число операций 1 тогда будет равно:

n-c ( n > 4 ), (2.6) N = [(n - t - 1)t + t - 1]= n(n - 1)(n - 2) / 6 0,1n3, t =n-+ N = -1) = (n -1)(n - 2) / 2 < 0,25n2, (n > 3). (2.7) (t t=Таблица t Ntc Nt+ I t 1 n - 2 0 2(n - 3) +2 1 3(n - 4) + 3 2 … … … … (n - t -1)t + t -t t -1 t … … … … n -1 0 + n - 2 n - 2 n -c c Чтобы приблизить оценку сверху N к реальному значению N, c предположим, что величина N пропорциональна коэффициенту полноты 1, тогда окончательно получим c c N = N = n(n -1)(n - 2) / 6. (2.8) Например, при = 0,5 и равномерном расположении элементов в матрице c сij (шахматная доска!) ясно, что число сравнений уменьшится вдвое.

+ Оценка N от коэффициента практически не зависит. Согласно (2.8) и (2.7) для решенного примера ( n = 6 и = 0,4 ) оценки соответственно + c равны N = 8 и N = 8, что несколько отличается от реальных значений c + (табл. 5; N =11, N = 7 ). По мере увеличения размера n матрицы c следует ожидать, что вследствие действия закона больших чисел [10; с. 52], [11] расхождение в оценках будет уменьшаться.

Требуемый объем вычислений при построении конкретного маршрута k,l также оценится по (2.6) и (2.7), при этом степень полинома уменьшится на 1 единицу, если появление пункта Al равновозможно на каждой итерации (рис. 2; 80 ).

Степень полинома в (2.6), (2.7) увеличится на 1 единицу при поиске множества кратчайших маршрутов для всех сочетаний (k,l), k,l =1,n.

Требуемый объём памяти ОЗУ в основном будет определяться числом значащих элементов матрицы c (для каждого элемента должны отводиться ячейки для хранения трёх чисел (cij,i, j )). Часть памяти выделяется для алгоритма и хранения получаемых результатов (табл. 3).

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

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

L( 6,3,4,5 5;2 = L 6,3,4,5,2 =12, однако L 6;2 = 4 – кратчайший маршрут (табл. 9).

3. В кратчайший маршрут ни одна вершина не может быть включена более одного раза, т.е. кратчайший маршрут – элементарный путь (иначе длину кратчайшего маршрута можно было бы уменьшить, что противоречит определению кратчайшего маршрута).

4. В кратчайший маршрут ни одна дуга не включается более одного раза, т.е. кратчайший маршрут – простой путь [1; с. 13].

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

6. Если совместно с матрицей расстояний c = cij задана и матрица средних скоростей vij передвижения по каждому участку cij, то, вычислив матрицу времен = ij (ij = cij / vij ) и применив рассмотренный метод (рис. 2) для каждой пары (k, j), получим маршрут k,l, кратчайший по времени.

7. Эстафетный метод не потребует существенных изменений, если вместо кратчайшего строить наиболее длинный маршрут (критический путь), что необходимо при сетевых методах планирования. В алгоритме (рис. 2) в пунктах 40, 60 потребуется min заменить на max, при этом согласно 90 появление циклов исключается.

8. При машинной реализации алгоритма эстафетного метода (рис. 2) время задержки (расстояние отставания) Tic (табл. 2) целесообразно добавлять ко всем элементам cij i -й строки, сохранившимся к t -му шагу процесса (i Git ).

Примечание. Статистическая обработка всего семейства кратчайших маршрутов (табл. 9) позволяет решать ряд практических вопросов, связанных с проектированием и функционированием сетей передачи данных (СПД): оптимизация топологической структуры СПД, задачи маршрутизации информационных потоков, обоснование пропускных способностей линий связи и узлов коммутации [3, 8, 6] и др.

Перейдем к рассмотрению другого класса задач построения кратчайшего пути на графе при некотором дополнительном условии:

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

3. КЛАССИЧЕСКАЯ ЗАДАЧА КОММИВОЯЖЕРА И ЕЕ РЕШЕНИЕ МЕТОДОМ РАСШИРЕНИЯ ЦИКЛА 3.1. Постановка классической задачи коммивояжёра ( = 1) Классическая задача коммивояжера хорошо известна по многим источникам [1, 2, 12, 5] и проста по своей содержательной постановке.

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

Классическая задача коммивояжера относится по степени сложности к классу NP-полных задач [13, 14], и ее постановка в форме задачи математического программирования со скалярными переменными [5, 12] не позволяет создать достаточно эффективные алгоритмы, особенно для решения задач больших размеров. Поэтому нужны специальные методы, не связанные с классическим подходом, основанным на аппарате анализа бесконечно малых. В [12] приведен анализ существующих наиболее эффективных методов решения, при этом все они при решении задач больших размеров носят неформальный характер. Наиболее успешные реализации приближенных алгоритмов связаны с двумя схемами решения:

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

Комбинаторная постановка задачи коммивояжера состоит в поиске такого замкнутого маршрута с началом и концом в одной вершине, который включает в себя все остальные вершины и длина его при этом минимальна. Формальную постановку задачи можно записать в виде n-L(k )= c min, ij k (i, j)k n-1 n-1 k = k,..., j,...,k {k }, n-1 n-где L(k ) – длина цикла как сумма длин дуг (i, j), входящих в цикл k ;

n-k – контур (цикл), содержащий в качестве промежуточных все n – остальных вершин графа (гамильтонов цикл).

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

1 n- Множество {k } содержит по крайней мере (n – 1)! элементов.

3.2. Метод расширения цикла, алгоритм, пример вычисления и эффективность алгоритма Суть метода расширения цикла состоит в следующем. Вначале по определенным правилам формируется начальный цикл k, и далее в ходе решения последовательно в промежутки между вершинами текущего t цикла k по определенным правилам включаются другие вершины графа, t еще не вошедшие в текущий цикл k. Процесс заканчивается после включения всех вершин в цикл (t = n -1).

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

Между начальным и конечным номерами вершин (k = l) включается t номер j – любой из множества Gt = {j} оставшихся вершин (j Gt ).

n-Сформированный таким образом начальный цикл 1 = k, j,k не k исключает возможность получения оптимальной последовательности номеров в конечном цикле 1. Правило включения очередной вершины (ее номера) в некоторый из промежутков текущего цикла состоит в том, что увеличение длины цикла t, получаемое на t-м шаге принудительного включения номера вершины Аj, должно быть минимальным.

Приращение tk,j,i, получаемое при пробном включении j между номерами вершин Аk и Аi, вычисляется по формуле t k, j,i = ckj + c - cki, j Gt. (3.1) ji Первые два числа – это длина полученного ломаного маршрута между вершинами Ak и Ai, а сki – длина прежнего пути между этими же t вершинами дуги. Если k, j,i < 0, то обходной путь короче, чем прямой – сki – длина цикла уменьшится.

На t-м шаге процесса текущий цикл будет содержать t + промежутков (интервалов) для пробного включения очередного номера j Gt. Для каждого интервала по формуле (3.1) потребуется вычислить n – 1 – t членов. Следовательно, для получения решения всего потребуется вычислить N членов (3.1):

n-N = -1 - t)(t + 1)= (n -1)(n - 2)(n + 3) < 0,2 n3.

(n t= Если в начальный цикл включить номера сразу двух вершин, то их очередность может оказаться не такой, как в оптимальном цикле, а следовательно, решение уже не может быть точным.

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

Примечание. Наиболее простой алгоритм (на каждом шаге идти к ближайшей вершине [12]) требует всего 0,5n2 операций сравнения, однако возможная погрешность при этом не поддается оценке.

Сравнение с оценками, приводимыми в [12] для наилучших из приближенных алгоритмов (алгоритм Линна ~3,5n3(n–4)!), позволяет рассчитывать на более высокую вычислительную эффективность метода расширения цикла.

Блок-схема алгоритма метода расширения цикла приведена на рис. 3.

Работу алгоритма проиллюстрируем на числовом примере, матрица расстояний для которого представлена в табл. 11.

Ниже приведены вычисления для случая отправления коммивояжера из пункта A1 ( k =1).

Согласно пункту 2 (рис. 3) начальный цикл и необходимые данные записаны для шага t = 1 в (3.2).

Таблица 11.

с = cij j 1 2 3 4 5 i 1 6 13 27 18 2 10 20 1 9 3 22 28 15 8 4 19 2 30 12 5 14 11 26 29 6 24 7 16 4 Начало 1° Ввод: c = cij,n,k 2° t Начальные значения: k = k, k +1, k, Ltk = ck,k+1 + ck+1,k, t, k = 1, t = Gk ={1;n}\ {k,k +1} 3° t Нумерация интервалов Jtr в текущем цикле k : r = 1;t +Границы: Jtr(t) = (jr-1, jr ), j0 = jt+r = k 4° r(t) Вычисление приращений: :

jr-1, j, jr r(t) t = c + c - c, r = 1;t +1, j Gk jr-1, j, jr jr-1, j j, jr jr-1, jr 5° min r( j) rt Определение rt, jt из условия min = jt, rt t r=1;t+ jGk jr-1, j, jr jr-1, jt, jr 6° rt t t t t Пересчет: Gk+1 = Gk \ {jt}, k+1 = k U{jt}rt, Ltk+1 = Ltk +, r = rt jr-1, jt, jr 7° t = t +9° 8° - + - Ln-1 > Ln-t > n -1 k k -+ 10° k = k +11° + Ln-1 = Ln-1 k k -- 12° n-1 n-Замена: Ln-1 = Ln-1, k -1 = k, (L0 = ) k -1 k 13° 0 n-1 Вывод: k = k, L(k )= Lmin = Ln-k Конец Рис. 3. Блок-схема алгоритма метода расширения цикла t = 1: L1 1,2,1 =16, k =1, G1 = {3,4,5,6}. (3.2) = = r 1, r 2, 1 1 3, 2 = + - = = + -10 32, = 13 28 6 35, 20, 2,3, = r 2, 1 1 4, 2 = + = 2,4,1 = + -10 10, = 27 2 - 6 23, 1, = j1 4, 1 1 5, 2 = + = 2,5,1 = + -10 13, 18 11- 9 14 = 6 23,, 2, 4,1 = 10.

1 1 6, 2 = + = 2,6,1 = + -10 37.

25 7 - = 6 26, 23, t = 2 : L2 1,2,4,1 = 26, G2 = {3,5,6}.

=, = = r 1 r 2, r 3, 2 12, 2 = 2, 3, 4 = + -1 34, 30 22 = = 35, 20 15 = 4,3,1 = + -19 33, r 3,, 3 2 12 = 2, 5, 4 = + -1 37, 12 14 j2 5, = 4,5,1 = + -19 7, = = 23, 9, 5, 2 2 1, 6, 2 = 2, 6, 4 = + -1 26, 17 24 7.

= 4,6,1 = + -19 22.

= 4, 5,1 = 26, 23 t = 3 : L3 1,2,4,5,1 = 33, G3 = {3;6}.

r =1, r = 2, r = 3, r = 4, 1 2 3 r3 = 4, 3 3 3 1,3,2 = 35, 2,3,4 = 34, 4,3,5 = 30 + 8 -12 = 26, 5,3,1 = 26 + 22 -14 = 34, j3 = 5, 3 3 3 1,6,2 = 26, 2,6,4 = 26, 4,6,5 =17 + 21-12 = 26, 5,6,1 = 5 + 24 -14 = 15. 5,6,1 = 15.

= = {} t 4 : L4 1,2,4,5,6,1 48, G4 = 3.

= r4 5, = = = = = r 1, r 2, r 3, r 4, r 5, 4 4 4 4 = j4 3, 1,3,2 = 2 3,4 = 4 3,5 = 5,3,6 = + = 6,3,1 = + = 35, 34, 26, 26 3-5 24, 16 22-24,, 6,3,1 = 14.

5 n 1 = (1 - )= =. (3.3) L1 L Ln-1 1,2,4,5,6,3,1 62, G = После нумерации интервалов (3), согласно (3.1) вычисляются приращения длины цикла (4). Например, для вычисления приращения 1,3,2 из табл. 11 извлекаются элементы, выделенные жирным шрифтом.

Примечание. При выполнении очередного t + 1-го шага можно t использовать приращения, вычисленные на предыдущем шаге, т.к. приращения изменятся только в двух интервалах, смежных с rt jt интервалом, в который был включен номер вершины на предыдущем шаге (см. t = 2). Расход памяти ОЗУ при этом t увеличится, т.к. придется сохранять приращения от предыдущего шага.

После пересчета текущих величин (пункт 6) осуществляется переход к очередному шагу цикла (пункт 7) и проверяется, закончено ли формирование цикла. Если цикл еще не закончен (пункт 8 –, т.е. Gt или t n -1), то процесс продолжается (переход к 3). В противном случае (8 +, Gt =, т.е. t > n -1) полученный k-й вариант решения Ln-1 по длине k цикла сравнивается с предыдущим. Если он хуже предыдущего (9 +), то назначается k + 1-й исходный вариант (пункт 10), и весь цикл расчетов повторяется. Пункты алгоритма (9 – 12) позволяют улучшить решение и повысить его достоверность. Действительно, анализируя табл. 12, в которой записана динамика полученного решения (3.3) и решений при всех возможных Cn = 15 начальных циклах 1 (элементы jt, включаемые в цикл на t -м шаге, выделены жирным шрифтом), можно видеть, что оптимальные решения в зависимости от начального цикла появляются с некоторой частотой P1 = 11/15 = 0,73. Следовательно, вычисляя последовательно m вариантов с различными начальными циклами, можно с вероятностью m Pm = 1- (1- P1) (3.4) утверждать, что лучший из них является оптимальным.

При m = 3 для P1 = 0,73 вероятность Pm близка к единице ( P3 0,98 ).

Этот результат подтверждается данными табл. 12: практически любая тройка случайно выбранных вариантов будет содержать хотя бы один оптимальный.

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






















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

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