WWW.DISSERS.RU

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

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


Pages:     | 1 || 3 | 4 |   ...   | 13 |

Из узла-источника Ak (рис. 1; табл. 1) по всем возможным направлениям одновременно в момент Tkc = 0 стартуют гонцы, двигающиеся с одинаковой единичной скоростью. Первым к некоторой вершине прибудет тот гонец из данной группы (лидер), у которого расстояние до вершины будет меньше, чем у других. Момент прибытия при этом будет численно равен длине пути, т.к. скорость равна единице.

Применительно к графу (табл. 1), при старте гонцов из УИ A1 первым прибудет (на первой итерации t =1) гонец в пункт Aj = A4, пройдя при t этом путь длиной min(c1 j ) = min(3;6;8) = 3 к моменту Tj1 =T4c =3.

j Если при этом номер достигнутой вершины совпадает с нужным (т.е. l = 4 ), то кратчайший путь найден на первой же итерации. При этом гонец пройдет по маршруту 1,4 = 1;4, а его длина L1,4 будет равна L1,4 =L(1,4)=c1,4 =3. Столбец j = 4 из табл. 1 удаляется.

Однако если найденный кратчайший маршрут не является искомым ( jt = 4 l ), то к остальным гонцам, стартовавшим из Ak, добавляется новая партия гонцов, получившая эстафету в момент T4 = 3 и стартующая из пункта A4 ко всем ещё не «оповещённым» пунктам (рис. 1; A6, A5).

Момент старта T4c = 3 удобно записывать справа от строки i = 4 (табл. 1).

Из новой группы выделяется лидер – он первым из этой партии прибудет к своему пункту ( A6 ). Так как этот лидер стартовал через T4c = 3 ед. времени после старта первой группы, то при единой системе отсчёта времени он прибудет в A6 в момент времени T6 =T4 +c4,6 = 3+ 2 = 5 ед.

Новый лидер в первой стартовавшей группе прибудет в A5 позднее – в момент T5c = c1,5 = 6 ед. (табл. 1). Следовательно, очередной кратчайший маршрут будет иметь длину L1,6 = 5 ед., при этом его концевая дуга (4;6) закончится в вершине A6 (табл. 2; t = 2 ). Чтобы найти новый кратчайший маршрут, необходимо его концевую дугу (4;6) достроить слева кратчайшим маршрутом, который к данной итерации уже был найден ( 1,4 = 1;4 ). Очередной кратчайший маршрут запишется (табл. 3):

0 0 1,6 = 1,4 4,6 = 1;4 4;6 = 1;4;6. (2.2) Если граничная вершина полученного кратчайшего маршрута ( A6 ) совпадает с искомой (т.е. j2 =6=l), то процесс оканчивается. При 6 l столбец j = 6 из табл. 1 удаляется, и цикл повторяется до выполнения условия jt = l, где jt - номер граничной вершины кратчайшего маршрута, который будет найден на текущей итерации t.

Таблица 2 Таблица t Lt Tic k,l k, l 1 1,4 1 2 2 1,4,6 31,4 61,5 61,3 1,5 3 1,4,5 4 1,4,6,3 54,6 64,5 1,4,6,2 6 1,4,6,3,1 86,Ntc 2 3 Nt+ 0 1 Определяемое таким путём множество кратчайших маршрутов получается упорядоченным по их длине, поэтому процесс поиска кратчайших маршрутов к заданной вершине Al не требует построения всего множества кратчайших маршрутов из вершины Ak, но может быть остановлен в момент появления концевой дуги с вершиной Al.

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

Из вершины (пункта) Ak в момент старта Tkc = 0 ( k =1- номер пункта старта) начинает движение группа гонцов с эстафетами, двигающихся с единичной скоростью ко всем смежным с A1 вершинам (табл. 1; A4, A5, A6 ).

Гонца, который первым придёт к своему объекту, будем именовать лидером и обозначать Лi, j (первый индекс – номер пункта старта Ai, второй – финиша). Для k =1 лидер Л1,4 финиширует в пункте A4 в момент времени, численно равный минимальному из элементов строки k =1:

L1,4 = min cij = ckj = min{3,6,8}= 3 = c1,4 j1 = 4, T1ф = 3. (2.3) j ф Момент финиша Т1 лидера Л1,4 в A4 является сигналом для старта очередной группы гонцов из пункта A4 (T4c = T1ф ), при этом вся группа и её лидер стартуют с задержкой относительно первой группы, равной времени финиша Л1,4, поэтому момент её старта T4c численно равен длине пути Л1,4, т.е. длине найденного кратчайшего маршрута L1,4 (табл. 3).

с Время задержки, как и момент старта Т4 = 3 группы, стартующей из пункта A4, удобно записывать рядом с табл. 1 справа на уровне соответствующей строки (i = 4). Столбец j = 4 из дальнейших вычислений выбывает, т.к. кратчайший маршрут к A4 уже найден (табл. 1;

столбцы 4 – 6). Итоговый результат записан в табл. 3.

Далее цикл повторяется: в обеих движущихся группах выделяются лидеры Л1,5 и Л4,6. С помощью табл. 1 и 2 вычисляются моменты финиша лидеров в единой системе отсчёта времени (от T1c = 0 ) по формуле дв t Tiф = Tiс + Tiл, i I, (2.4) c где T - время старта группы из пункта A (т.е. время её задержки i i дв относительно первой стартовавшей группы T1c = 0 ); Tiл -время движения лидера Лi, jt данной группы гонцов на данном шаге (t ) процесса;

t I -множество групп гонцов, находящихся в движении на t-м шаге процесса.

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

i = 0 : 0 + c1,5 = 0 + 6 = 6, (1;5) для Л1,5, i I = {0;4}:

i = 4 : 3 + c4,6 = 3 + 2 = 5, (4;6) для Л4,6 (2.5).

Из (2.5) видно, что лидер Л4,6 определяет очередной кратчайший маршрут.

Необходимые промежуточные вычисления путём элементарных расчётов [см. формулу (2.5)] выполняются по данным табл. 1. с использованием столбца Tic. Эти результаты записываются в табл. 2, t = 2, откуда определяется главный лидер Л и концевая дуга (4;6). По 4,концевой дуге [см. формулу (2.2)] находится очередной кратчайший маршрут 0 1,6 = 1,4,6 и его длина L1,6 = T4ф = 5.

л Итоговые результаты записаны в табл. 3, t = 2.

Так как концевая вершина j =6l =3, то процесс продолжается.

Шаг t = 3:

- столбец j = 6 удаляется из памяти ЭВМ (табл. 1; столбцы 4 –6);

- момент старта из A6 T6c =L1,6 =5 записывается правее строки i = 6;

- согласно (2.4), (2.5) вычисляются элементы для t = 3 (табл. 2).

Из полученного столбца (табл. 2; t = 3) следует, что очередные два кратчайших маршрута имеют длины L1,5 = 6 и L0 = 6; концевые дуги:

4,(1;5) 1,5 = 1;5 ; (4;5) 1,5 = 1,4,5 (табл. 3). Так как пункт A3 не является концевым у найденного кратчайшего маршрута (l = 3 5), то процесс продолжается (столбец j = 5 из табл. 1 удаляется).

Шаг t = 4.

Далее, для большей наглядности, процесс продолжен в табл. 4 и 5, из которых убраны ненужные предыдущие записи:

- момент старта T5c = L1,5 =6 записывается правее строки i = 5 на одном уровне с нею;

- согласно (2.3), (2.4) вычисляются моменты финиша лидеров всех t групп i I (табл. 5, t = 4 ; в группах {i}= {1;4} I гонцов уже не осталось, а в группах {2;3} они ещё не стартовали);

- из полученного столбца следует, что лидер Л6,3, определяющий очередной кратчайший маршрут, финиширует в заданной вершине A(t4 =3=l =3).

Концевая дуга (6;3) позволяет построить кратчайший маршрут 0 1,3 = 1,4,6 (6;3) = 1,4,6,3 при этом L1,3 = 8, что записано в табл. 3. Процесс прекращается.

Примечания:

1. В табл. 5 выполнен шаг t = 5, завершающий построение всего множества кратчайших маршрутов из УИ A1. Это множество представлено первой строкой табл. 9. Другие строки табл. содержат аналогичные результаты, полученные при других УИ Ai (промежуточные вычисления опущены).

В диагональных клетках табл. 9 можно было записать 0 L0 = L0 =0, k,k = k = k, k. Однако вместо этого тривиального k,k k результата в них записаны запасные (кратчайшие из оставшихся) кольцевые маршруты. Такие кратчайшие маршруты получаются, если перед началом расчётов столбец j = k не удалять из табл. 1.

2. В правом столбце табл. 9 приведены средние значения длины кратчайшего маршрута как интегральная характеристика k -го узлаисточника A :

k n Llk = L0, k =1,n, L0,k = 0.

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

Усреднение длины кратчайших маршрутов по всему их множеству n L = L k n k =может рассматриваться как некая обобщённая характеристика графа с данной топологической структурой и полнотой, что важно при проектировании сетей передачи данных.

Таблица 4 Таблица t Tic 1 2 3 4 5 6 1 2 3 4 5 k=1 0 – – – 1 222,2 6 133,3 5 4 3 – – – 125,2 125,5 6 6 – 86,3 96,6 4 3 5 – Ntc 2 3 3 2 1 Nt+ 0 1 2 2 2 Таблица 6 (=0,4) Таблица 7 Таблица t LTic k, jt k, jt t 1 2 3 4 5 6 1 2 3 4 1 1,4 31,61,5 61,k=1 3 6 8 0 – – 2 1,4,6 2 6 9 3 1,5 3 1,4,5 54,6 64,3 5 3 8 – 4 1,4,6,3 4 3 2 3 – – 5 1,4,6,2 5 6 6 125,2 125,86,3 8 6,3 6,6 4 3 c + N = 11, N = k,l Таблица 9. Совмещенная матрица, L = 7,7, = 0,Lk,l l, j, УП Aj Lk 1 2 3 4 5 1,4,6,3,1 1,4,6,2 1,4,6,3 1,4 1,5;1,4,5 1,4,1 5,13 9 8 3 6 2,3,1 2,3,4,6,2 2,3 2,3,4 2,3,4,5 2,3,4,2 8,11 15 6 9 12 3,1 3,4,6,2 3,4,6,3 3,4 3,4,5 3,4,УИ 3 4,5 9 8 3 6 Ai 4,6,3,1 4,6,2 4,6,3 4,5,4 4,5 4,i, k 4 4,10 6 5 8 3 5,2,3,1 5,2 5,2,3 5,2,3,4 5,2,3,4,5 5,2,3,4,5 11,17 6 12 15 12 6,3,1 6,2 6,3 6,3,4 6,3,4,5 6,3,4,6 5,8 4 3 6 9 Подробнее о практических аспектах использования результатов, получаемых на основе решения задачи о кратчайшем пути, можно ознакомиться по другим источникам, например [3 – 8].

2.3. Алгоритм эстафетного метода (ЭМ) Рассмотренная схема расчётов может быть представлена в форме алгоритма, для описания которого введем дополнительно некоторые обозначения:

Gt - множество номеров вершин Aj, к которым при выполнении t -го шага (итерации) процесса ещё не найдены кратчайшие маршруты (например, G1 = {j k }) ;

Git - множество номеров вершин Aj, к которым при выполнении t -го шага от вершины Ai существует конечная дуга (cij > 0) и, следовательно, к этим вершинам ещё возможно построение маршрута t Git = { j | cij > 0, j Gt},i I, t I - множество номеров вершин Ai (УИ Ai ), от которых за все t шагов где стартовали группы гонцов (например, I1 = {k});

{jt}- множество номеров концевых вершин Aj, к которым на t -м шаге были найдены кратчайшие маршруты;

Проиллюстрируем динамику работы алгоритма ЭМ при построении кратчайшего маршрута 1,3, блок-схема которого представлена на рис. 2.

Исходной информацией является матрица c (табл. 1) и концевые вершины (k;l)= (1;3) - пункт 10. Для первого шага (t =1; пункт 20) вычисляются начальные значения текущих величин:

30 : G1 = {2,3,4,5,6}, G1 ={j | c1 j > 0, j {2,3,4,5,6}}= {4,5,6}, I1 = {1}, T1c = 0.

Начало отсчёта (время старта каждой группы гонцов) не зависит от номера шага t и при «ручных» расчётах последовательно в ходе процесса записывается справа от табл. 1.

Множество концевых дуг {(i, jt )} лидеров стартовавших групп для шага t = 1 ( I1 = {k} = {1}) согласно 40 равно:

i =1: min(c1, j ) = min(c1,4;c1,5;c1,6 ) = min(3;6;8) = 3 (i, j1) = (1;4).

jGКонцевые дуги (i, jt ) и их длины cij запоминаются в памяти ЭВМ t (при «ручных» расчётах записываются в табл. 2, t =1).

Поскольку множество концевых дуг лидеров не пусто (50 -), то это означает, что к некоторым вершинам могут быть построены маршруты.

Пункт 60 позволяет найти концевые дуги кратчайших маршрутов (таких маршрутов может быть более одного). Чтобы выявить кратчайший t маршрут необходимо момент прибытия каждого из множества I лидеров привести к единой (относительно момента старта первой группы Tkc = 0 ) системе отсчёта времени, при этом наименьшее время и обозначит собой концевую дугу очередного кратчайшего маршрута (60 ):

min(Ti1 + ci.4) = 0 + 3 = 3 {(1;4)},{ j1} = {4},{i1} = {1}.

i{1} Поскольку на первом шаге старт произведен только из УИ A1, то лидер этой группы и определит первый кратчайший маршрут, самый короткий из всего множества, записанный в строке t = 1 (табл. 9).

Согласно 70 сам кратчайший маршрут будет получен путём достраивания его недостающей части слева от концевой дуги (1;4):

1,4 = k,...,i1 (i1; j1) = 1,...,1 (1;4) = 1;4.

Длина построенного кратчайшего маршрута L0 при единичной kjскорости движения гонцов численно равна моменту прибытия лидера на концевую вершину A4 кратчайшего маршрута 1,4.

Конечные результаты фиксируются в памяти ЭВМ, а при «ручных» расчётах записываются в табл. 3.

Если номер l = 3 искомой вершины содержится среди номеров концевых вершин { jt} найденных кратчайших маршрутов (80 + ), то выводятся и записываются полученные результаты (110 ), процесс заканчивается. В противном случае (80 - ) производится пересчет текущих величин (90 ) и делается переход к очередной итерации (100 ).

Согласно пункту 90 вначале уточняются множество номеров вершин Aj, к которым ещё не построены кратчайшие маршруты, и множество номеров вершин, от которых проведен старт групп:

G2 = {2,3,4,5,6} \ {4} = {2,3,5,6}, I = {1} {4} = {1;4}.

Начало Ввод:, k, l c = cij t =t t Gt = {j k},Gk = { j | ckj > 0, j Gt}, I = {k},Tkc = Определение множеств {(i, jk )};{jk} из условия k t i I : min(cij )= cij {(i, jt )},i I ;{jt} t jGit + t i I :{(i, jt )}= – Построение множества концевых дуг КМ:

{it, jt}:min(Tic +cij )=Tic +ci jt {(it, jt)},{jt},{it} t t t iIt Определение КМ и их длин по концевым дугам:

kj = k,...,it (it, jt )= k,..., jt,{jt};L0 = Tic + kjt t t + l {jt} – t+1 t Gt+1 = Gt \{jt}; I = I {i = jt};

Пересчет t+1 c Git+1 = Git \{jt}, i I ;Ti= jt = Tjc = Lkjt t t =t + Вывод:

0 kl = kj, jt {jt}; L0 = Lkl kjt t Конец Рис. 2. Блок-схема алгоритма построения кратчайшего маршрута (КМ) эстафетным методом Уточнение множества Gt равносильно удалению соответствующих столбцов в матрице c при «ручных» расчётах.

Номера концевых вершин Aj, к которым ещё возможно построение маршрута на втором шаге (t = 2 ) процесса из пунктов старта Ai i I = {1;4}, найдутся по рекуррентной формуле (пункт 90 ) i =1: G12 = G1 \ { j1} = {4;5;6} \ {4} = {5;6}, I = 2 i = 4 : G4 = G4 \ { j1} = {5;6} \ {4} = {5;6}.

Величины задержек моментов старта гонцов остаются прежними для t всех стартовавших ранее групп (i I ), а для стартовавших вновь (поле t -го шага процесса) задержка численно равна длине кратчайшего маршрута до соответствующего УИ Ai (i { jt}). Для t = 2 согласно имеем Tjc = T4c = L1,4 = 3.

Далее осуществляется переход к шагу t = 2 (пункт 100 ), и весь цикл повторяется уже с двумя стартовавшими группами ( I = {1;4}).

Согласно 40 определяются концевые дуги лидеров {(i, jt )} (табл. 2;

t = 2 ). Так как найденное множество дуг не пусто (50 - ), то определяется (60 ) концевая дуга очередного кратчайшего маршрута (или множество { jt}), строится сам кратчайший маршрут (70 ) и находится его длина L1,6 = 5 (табл. 2; t = 2 ; 70 ), полученный результат при «ручных» расчётах заносится в табл. 3, t = 2.

Поскольку искомый кратчайший маршрут не найден (l = 3{6}, 80 - ), то после пересчёта текущих величин (90 ) выполняется очередная итерация (100, t = 3), время задержки новой группы гонцов, стартующей от УИ A6 T6c = 5, записано справа от строки i = 6 в табл. 1.

На итерации t = 3 согласно 60 множество концевых дуг содержит уже три элемента:

{(i3, j3)} = {(1;5),(4;5),(6;3)} (табл. 2; t = 3).

Две дуги соответствуют более коротким маршрутам ( L1,5 = 6 < L 1,4,6,3 = 8 ) и ведут к одному УП A5. Значит, к вершине Aсуществуют два равных по длине кратчайших маршрута. Согласно 70 это маршруты 0 0 0 1,5 = 1;5 и 1,5 = 1;4 (4;5) = 1;4;5, L(1,5) = L 1,5 = 6.

Так как l = 3 5, то согласно 80 - 100 начинается новый цикл (t = 4 ), в ходе которого и будет построен искомый кратчайший маршрут 1,3 = 1,4,6,3 (см. табл. 7; 8).

Циклический алгоритм достаточно прост, что обеспечивает решение задач больших размеров ( n >1000 ) за приемлемое для практических целей время.

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

Pages:     | 1 || 3 | 4 |   ...   | 13 |






















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

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