WWW.DISSERS.RU

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

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


Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 13 |

Поскольку априори вероятность P1 неизвестна, то в алгоритме (рис. 3) реализована следующая схема останова процесса решения: процесс прекращается после появления варианта, совпадающего с лучшим к этому времени вариантом, хранящимся в ОЗУ ЭВМ (12). В соответствии с этим правилом для полученного решения (3.3) будем иметь L1 = 62 L0 = (9–) и 62 (11–), поэтому вместо L0 = в ОЗУ 5 записывается L1 = 62, 1 (3.3) (12). Вычисляются номер очередного варианта начального цикла (10) и исходные данные нового цикла – Исходные циклы 1(k, j,k) 1( j,k, j) приводят к одному и тому же решению, т.к. они и равносильны перестановке интервалов, что на решение не влияет.

2 = 2,3,2 (2). Полученное решение L5 2,1,3,5,6,4,2 = 42, проходя цепочку 8+, 9–, 11–, 12, заменяет прежнее лучшее решение L1 = 62 на L5 = 42 (12).

Далее выполняется переход 10 к очередному варианту – 3 = 3,4,3, (2). Полученный третий вариант решения L5 3,5,6,4,2,1,3 = 42 совпадает (табл. 12) с лучшим (11+). Это решение записывается как оптимальное (13).

Примечание. Если бы очередной начальный вариант 2, как и 1, дал бы ошибочное решение L5 = 62, совпавшее с первым, то полученный согласно 11+ результат также был бы ошибочным.

Такой случай наиболее возможен, если вероятность P1 низка и, следовательно, вероятность получения подряд двух неверных решений (1- P1) велика. Снизить вероятность ошибочного решения можно заменой начального значения L0 = на лучшее решение, полученное из ряда m вариантов. Приняв, например, P1 = 0,2 при m = 10, согласно (2.8) почти достоверно можно утверждать, что лучший из этих 10 вариантов – оптимальный.

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

Указанные доработки не повлияют существенно на порядок и объем вычислений.

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

Nb (Ln-1 - L0) - 42) 1 (l = = = 0,127 (12,7%), Nb l=1 L0 15 где Nb = Cn – общее количество возможных вариантов; l – номер варианта.

Если снять жесткое условие об однократности включения номера вершины в цикл, то в ряде случаев некоторого улучшения полученного решения можно добиться путем проверки и выполнения первого необходимого условия оптимальности: расстояние между любой парой смежных вершин (i,j) в решении равно длине кратчайшего маршрута между ними.

t Таблица 12. Динамика расширения цикла k 1 2 3 4 k k L1 k L2 k L3 k L4 k Lk k k k k 1,2,1 16 1,2,4,1 26 1,2,4,5,1 33 1,2,4,5,6,1 48 1,2,4,5,6,3,1 1,3,1 35 1,3,5,1 35 1,3,5,2,1 42 1,3,5,4,2,1 62 1,3,5,6,4,2,1 1,4,1 46 1,2,4,1 26 1,2,4,5,1 33 1,2,4,5,6,1 48 1,2,4,5,6,3,1 1,5,1 32 1,2,5,1 29 1,2,3,5,1 48 1,2,4,3,5,1 59 1,2,4,6,3,5,1 1,6,1 49 1,3,6,1 40 1,3,6,2,1 33 1,3,6,4,2,1 32 1,3,5,6,4,2,1 2,3,2 48 2,3,6,2 30 2,3,6,4,2 29 2,1,3,6,4,2 32 2,1,3,5,6,4,2 2,4,2 3 2,4,1,2 26 2,4,5,1,2 33 2,4,5,6,1,2 48 2,4,5,6,3,1,2 2,5,2 20 2,5,6,2 21 2,5,6,4,2 20 2,3,5,6,4,2 20 2,1,3,5,6,4,2 2,6,2 30 2,5,6,2 21 2,5,6,4,2 20 2,1,5,6,4,2 39 2,1,3,5,6,4,2 3,4,3 45 3,6,4,3 37 3,6,4,2,3 29 3,6,4,2,1,3 32 3,5,6,4,2,1,3 3,5,3 34 3,5,6,3 29 3,5,6,2,3 40 3,5,6,4,2,3 39 3,5,6,4,2,1,3 3,6,3 19 3,5,6,3 29 3,5,6,2,3 40 3,5,6,4,2,3 39 3,5,6,4,2,1,3 4,5,4 41 4,5,6,4 21 4,2,5,6,4 20 4,2,1,5,6,4 39 4,2,1,3,5,6,4 4,6,4 21 4,5,6,4 21 4,2,5,6,4 20 4,2,1,3,6,4 32 4,2,1,3,5,6,4 5 5,6,5 26 5,6,2,5 21 5,6,4,2,5 20 5,6,4,2,3,5 39 5,6,4,2,1,3,5 Это условие будет выполнено, если элементы сij являются минимальными в строках или столбцах матрицы с или, в противном случае, будут заменены кратчайшими маршрутами ij, например:

L 1,2,4,5,6,3,1 = с12+с24+с45+с56+с63+с31 =6+1+12+5+16+22 = 62. (3.5) Три выделенных элемента не являются минимальными ни в столбцах, ни в строках матрицы с. Найденные для них кратчайшие маршруты и их длины соответственно равны:

L 4,2,5 = 11, L 6;3 =16 = c63, L 3,6,4,2,1 = 19. (3.6) Заменяя соответствующие дуги в (3.5) на кратчайшие маршруты (3.6), получим улучшенное решение, в котором включенные элементы выделены жирным шрифтом: L 1,2,4, 2,5,6,3,6,4,2,1 = 58. В новом решении некоторые элементы содержатся более одного раза, а значит, могут быть удалены. Если повторяющийся элемент совместно с двумя смежными с ним не образует кратчайший маршрут, то он удаляется (второе необходимое условие оптимальности). Согласно этому условию элемент j = 4 удаляется, так как маршрут 2,4,2 не является кратчайшим (табл. 14;

k = 2 ).

Совместно с j = 4 удаляется и одна из двух оказавшихся рядом двоек.

Окончательно получим L 1,2,5,6,3,6,4,2,1 = 55.

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

Таблица 13. || 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 kj Таблица 14. Совмещенная матрица Lkj j 1 2 3 4 5 k 1,2,1 1;2 1;3 1,2,4 1,2,5 1,3,16 6 13 7 15 2;1 2,4,2 2;3 2;4 2;5 2,5,10 3 20 1 9 3,6,4,2,1 3,6,4,2 3,6,3 3,6,4 3;5 3;19 9 19 7 8 4,2,1 4;2 4,2,3 4,2,4 4,2,5 4,2,5,12 2 22 3 11 5;1 5,6,4,2(5,2) 5,6,3 5,6,4 5,6,4,2,5 5;14 11 21 9 20 6,4,2,1 6,4,2 6;3 6;4 6,4,5 6,3,16 6 16 4 16 3.3. Модифицированный метод расширения цикла, примеры вычислений и эффективность метода Основное отличие модифицированного метода расширения цикла от метода расширения цикла состоит в том, что на каждом t -м шаге процесса при пробном включении j -й ( j Gt ) вершины в интервал t ( k – i ) вместо дуг (k, j) и ( j,i) при вычислении приращения k ji [см. формулу (3.1)] используются кратчайшие маршруты kj и 0,i :

j t 0 k ji = L(kj)+ L(0 )- cki = L(kj U 0 )- cki, j Gt, (3.7) ji ji где точки в (3.7) между k, i ; j, i отражают тот факт, что соответствующие вершины соединены через кратчайшие маршруты.

Использование (3.7) предполагает отказ от жесткого условия об однократности включения каждой вершины в цикл, а следовательно, создает дополнительные условия для уменьшения его длины.

Вычисление приращений по формуле (3.7) обеспечивает и выполнение отмеченного выше необходимого условия оптимальности, что исключает необходимость его проверки. Проиллюстрируем порядок расчетов на числовом примере табл. 13.

Из (3.7) видно, что для вычисления приращений исходной информацией будут являться кратчайшие маршруты kj и их длины, вычисляемые по мере необходимости эстафетным методом (рис. 2), и длины дуг cij (табл. 13). Для иллюстрации удобно кратчайшие маршруты и их длины вычислить заранее и поместить в совмещенной матрице kj Lkj (табл. 14). Длины дуг cij записаны в табл. 13. Например, для начального цикла 3,6,3 согласно табл. 14 имеем = = { }.

t 1; L1 3,6,3, G1 1,2,4,rt =1 rt =1 1 2 316 = L 3,6,4,2,1,3,6 -3=19+16-3=32, 346 =10,7, 613 = L 6,4,2,1,3 -16=16+13-16=13, 61.3 =4,3, 1 1 2 326 = L 3,6,4,2,5,6 -3=9+14-3=20, 3.26 =6,7, 623 = L 6,4,2,3 -16=6+20-16=10, 623 =5, (3.8) 1 1 2 346 = L 3,6,4,2,5,6 -3=7+16-3=20, 346 =6,7, 643 = L 6,4,2,3 -16=4+22-16=10, 643 =5, 1 1 2 356 = L 3,5,6 -3=8+5-3=10, 356 =10, 653 = L 6,4,5,6,3 -16=16+21-16=21 653 =10,5.

, Принудительно включаемый в r-й интервал текущего цикла элемент j (3.7), разделяющий кратчайшие маршруты kj и 0, выделен в (3.8) ji жирным шрифтом. Длины соответствующих кратчайших маршрутов берутся из табл. 14, например L0 j = L01 3,6,4,2,1 =19, L16 = L 1,3,6 =16, k c3,6 = 3 (табл. 13). Однако теперь совместно с принудительно включаемым в цикл элементом j в цикл могут быть попутно включены и некоторые другие элементы из множества Gt.

t Таким образом, наряду с показателем k ji необходимо учитывать и t другой показатель nk ji – общее количество номеров вершин, {j} Gt, которые впервые включаются в цикл на t-м шаге. Например, при вычислении 316 (3.8) наряду с элементом j = 1 в цикл будет включено и множество элементов {j}= {2;4} G1.

Указанные два частных критерия могут быть объединены в один:

среднее приращение длины цикла, приходящееся на каждый впервые включенный элемент j Gt, t t t = k ji nk ji, j Gt, rt. (3.9) k ji Вычисленный удельный прирост длины цикла (3.9) эквивалентен главному критерию L(k ), т.к. при n = const минимизация среднего расстояния между вершинами L(k ) n равносильна минимизации его длины L(k ).

Из (3.8) следует, что 1 613 =13, n113 = 3, ({j}= {4,2,1} G1) и =133 4,3.

6 Найденный удельный прирост является минимальным для всех j G1 и интервалов r1 (3.8). Поэтому на первом шаге в интервал с номером rt = r1 = 2 между его левой (j = 6) и правой (j = 3) границами включаются элементы {jt}= {4,2,1} (см. L 6,4,2,1,3, 613 в (3.8)).

После пересчета текущих величин ко второму шагу процесса имеем t = 2 : L2 3,6,4,2,1,3 = 32, G2 = {5}.

Так как осталось включить в цикл только один элемент, то согласно 2 (3.9) для каждого интервала имеем = k5i :

k5i r2 =1 r2 = 2 r2 = 2 2 3.5.6 = 10, 6.5.4 =16+ 9 - 4 = 21, 4.5.2 =11+11- 2 = 20, r2 = 4 r2 = 2.5.1 = 9 + 14 -10 =13, 125.3 =15 + 21 -13 = 23.

.

Поскольку минимальное приращение соответствует включению элемента j2 = 5 в первый интервал, то согласно (3.7) и табл. 14 в развернутом виде имеем 2 0 356 = L 3,5 U 5,6 - c3,6 = L 3,5,6 - c3,6 = 8 + 5 - 3 =10, т.е. в интервал r = 1, (3 6) включается только элемент j2 = 5.

Окончательно получаем L 3,5,6,4,2,1,3 = 42.

Исходный цикл влияет на точность решения, а в модифицированном методе расширения цикла он будет влиять и на объем вычислений. В качестве начального цикла (t =1) в модифицированном методе расширения цикла целесообразно брать цикл, составленный из двух кратчайших маршрутов, которые соединяются между собой включаемым в нулевой цикл k,k номером j. По аналогии с методом расширения цикла можно записать 1 = k j k, (метод расширения цикла k = k, j,k ), k k = 1;n -1, j k, (3.10) где точка между индексами означает, что k, j и k соединены кратчайшими маршрутами. Например, на основании табл. 14 имеем 1 3 = 3 1 3 = 3,6,4,2,1,3, L1 = L 3 =19 + 13 - 0 = 32.

Совместно с принудительно включенным элементом j =1 в цикл вошли элементы {6;4;2} ( n313 = 4), и, следовательно, удельный прирост длины цикла (3.9) равен = 32 4 = 8.

В табл. 15 приведено множество решений, полученных методом расширения цикла и модифицированным методом расширения цикла при всех начальных циклах, образованных включением в цикл k,k элемента j по кратчайшим маршрутам согласно (3.10) и табл. 14.

Из сравнения вариантов решений, записанных в табл. 9, можно видеть, что средняя погрешность для модифицированного метода расширения цикла (ММРЦ) снизится до 7,6 % и останется практически прежней для метода расширения цикла (МРЦ) и совмещенного метода (5,2 %), (правый столбец). Для обоих методов число итераций существенно сокращается.

Если матрица с не является полной ( <1), то решение может быть получено только модифицированным методом расширения цикла.

Решение также следует начать с нулевого цикла k,k, поочередно включая в него элементы j k. Порядок решения проиллюстрируем на числовом примере, представленном в табл. 16 (рис. 1).

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

Для начального цикла 1 = 1;1 с помощью табл. 17 запишем пять циклов первого шага с последовательным включением в них элемента j G1, соединяющего два кратчайших маршрута.

Согласно (3.7) и табл. 17 для первого шага имеем:

t = 1, L(1 )= 0, G1 = {2,3,4,5,6}:

1 1 121 = L 1,4,6,2,3,1 - 0 = 9 +11 = 20, n121 = 4, 121 = = 5,0;

1 1 131 = L 1,4,6,3,1 - 0 = 8 + 5 = 13, n131 = 3, 131 = 4,3;

1 1 141 = L 1,4,6,3,1 - 0 = 3 +10 = 13, n141 = 3, 141 = 4,3;

1 1 151 = L 1,4,5,2,3,1 - 0 = 6 +17 = 23, n151 = 4, 151 = 5,7;

1 1 161 = L 1,4,6,3,1 - 0 = 5 + 8 =13, n161 = 3, 161 = 4,3.

В соответствии с минимальным удельным приращением цикла = 4,( ) в цикл включено множество номеров {4,6,3}. За последующие два шага поочередно в цикл будут включены и последующие два оставшихся элемента множества G2 = {2;5}. Однако для уменьшения числа шагов необходимо проверить возможность включения в цикл большего числа элементов, чем у маршрута 131, который соответствует минимальному значению удельного приращения.

Цикл 131 может быть заменен более расширенным циклом при 1 jвыполнении трех условий:

- удельное приращение 1 j1 является ближайшим к минимальному 131;

- новый цикл 1 j1 включает в себя рассматриваемый 1 121 = 1,4,6,2,3,1 1,4,6,3,1 = 131;

- новый цикл ( 131 ) содержит в себе большее количество элементов множества G1, чем 131: n1 j1 > n131.

Этим условиям удовлетворяет только маршрут 121 (j = 2), он 1 1 доминирует над маршрутом 131, (1.2.1 f 1.3.1), поэтому после первого шага вместо 131получим t = 2 : L(121) = L 1,4,6,2,3,1 = 20, G2 = {5}. (3.11) Таблица Начальные циклы МРЦ ММРЦ min 1 1 k( j) k ( j) k·j·k k L1 n1 jk Gk jk L1 L1 Lk L2 L1 Lk k k jk k k k k k 1·2·1 1,2,1 16 1 16 3,4,5,6 1,2,4,5,6,3,1 62 20 1,3,6,4,2,5,6,4,2,1 52 10 1·3·1 1,3,6,4,2,1 32 4 8,0 5 1,3,5,6,4,2,1 42 0 1,3,5,6,4,2,1 42 0 1·4·1 1,2,4,2,1 19 2 9,5 3,5,6 1,2,4,2,5,6,3,1 61 19 1,3,6,4,2,5,6,4,2,1 52 10 1·5·1 1,2,5,1 29 2 14,5 3,4,6 1,2,4,3,5,1 62 20 1,3,6,4,2,5,6,4,2,1 52 10 1·6·1 1,3,6,4,2,1 32 4 8,0 5 1,3,5,6,4,2,1 42 0 1,3,5,6,4,2,1 42 0 2·3·2 2,3,6,4,2 29 3 9,7 1;5 2,1,3,5,6,4,2 42 0 2,1,3,5,6,4,2, 42 0 2·4·2 2,4,2 3 1 3 1,3,5,6 2,4,5,6,3,1,2 62 20 2,5,1,3,6,4,2 45 3 2·5·2 2,5,6,4,2 20 3 6,7 1;3 2,1,3,5,6,4,2 42 0 2,5,4,1,3,6,4,2 45 3 2·6·2,5,6,4,2 20 3 6,7 1;3 2,1,3,5,6,4,2 42 0 2,5,1,3,6,4,2 45 3 3·4·3,6,4,2,3 29 3 9,7 1;5 3,5,6,4,2,1,3 42 0 3,5,6,4,2,1,3 42 0 3·5·3,5,6,3 29 2 14,5 1,2,4 3,5,6,4,2,1,3 42 0 3,5,6,4,2,1,3 42 0 3·6·3,6,3 19 1 19 1,2,4,5 3,5,6,4,2,1,3 42 0 3,5,6,4,2,1,3 42 0 4·5·4,2,5,6,4 20 3 6,7 1;3 4,2,1,3,5,6,4 42 0 4,2,5,1,3,6,4 45 3 4·6·4,2,5,6,4 20 3 6,7 1;3 4,2,1,3,5,6,4 42 0 4,2,5,1,3,6,4 45 3 5·6·5,6,4,5 21 2 10,5 1,2,3 5,6,4,2,1,3,5 42 0 5,1,3,6,4,2,5 45 3 i 79 48 Lk %, (2.7) 12,5 7,6 5,В один из пяти интервалов цикла осталось включить только номер вершины j = 5. На основании (3.7) и табл. 17 имеем r =1:

1254 = L 1,5,2,3,4, - c14 = 6 + 15 - 3 =18 = 154, r = 2:

2 456 = L 4,5,2,3,4,6 -c46 = 3+17- 2 =18 =, r = 3 :

2 652 = L 6,3,4,5,2 - c62 = 9 + 6 - 4 = 11 =, r = 4:

2 253 = L 2,3,4,5,2,3 - c23 =12 +12- 6 =18=253, r = 5:

2 351 = L 3,4,5,2,3,1 - c31 = 6 +17 - 5 =18 = 154.

Таблица 16. c = || cij ||, = 0,j 1 2 3 4 5 i 1 3 6 2 13 3 5 4 3 5 6 4 В соответствии с минимальным удельным приращением =11 в 6.5.интервал r = 3 в (3.11) включаются номера вершин {3,4,5}, из них два – повторно. Окончательно, заменяя интервал 6;2 в (3.11) на 6,3,4,5,2, получим L 1,4,6,3,4,5,2,3,1 = 31. (3.12) Решение оптимально.

kj Таблица 17. Совмещенная матрица КМ Lkj j 1 2 3 4 5 k 1,4,6,3,1 1,4,6,2 1,4,6,3 1;4 1,4,5(4,5) 1,4,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,11 15 20 9 12 3;1 3,4,6,2 3,4,6,3 3;4 3,4,5 3,4,5 9 8 3 6 4,6,3,1 4,6,2 4,6,3 4,6,3,4 4;5 4;10 6 5 8 3 5,2,31 5;2 5,2,3 5,2,3,4 5,2,3,4,5 5,2,3,4,17 6 12 15 18 6,3,1 6;2 6;3 6,3,4 6,3,4,5 6,3,4,8 4 3 6 9 Если в качестве начального цикла взять любой оптимальный неполный цикл (главная диагональ табл. 9), то также будут получены оптимальные решения, при этом решение (3.12) не является единственным, например:

L 1,5,2,3,4,6,3,1 = 31.

Решение задачи при < 1 существует, если матрица c = cij является сильно связной. Необходимым и достаточным условием сильносвязности матрицы является возможность построения хотя бы одного гамильтонова цикла. Такой цикл возможен, если из матрицы с может быть выделена подматрица, содержащая по одному элементу сij в каждой строке и каждом столбце, при этом ни одна пара элементов не является симметричной относительно главной диагонали. Полная матрица кратчайших маршрутов не существует, если матрица с не является сильно связной.

Выводы 1. При полной ( =1) матрице смежности с (матрице расстояний) для решения задачи определения гамильтонова цикла на графе наиболее целесообразно использовать метод расширения цикла (рис. 3). В качестве H начального цикла k при этом могут быть использованы циклы, H H образованные двумя кратчайшими маршрутами ( k = k jk, например H, табл. 15).

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 13 |






















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

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