Главная Бухгалтерия в кармане Учет расходов Экономия на кадровиках Налог на прибыль Как увеличить активы Основные средства
Главная ->  Гамильтоновы циклы 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 [ 92 ] 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

( ) Последовательно уменьшаемые штрафы

При использовании фиксированных штрафов может возникнуть ситуация, когда вершина Х;, с = 3 (например), оштрафованная в некоторый момент на у, превратится в вершину с = 1 после следуюш,ей итерации, иными словами, вершина Xi сверх-оштрафована . Если используется смешанная стратегия (I (с)), то на следующей итерации вершина будет оштрафована на величину - 7, и ЭТО может привести к тому (не обязательно), что снова станет равным 3. Из-за этих колебаний величины может потребоваться неоправданно большое число итераций.

Было найдено, что в такой ситуации для большинства графов лучший метод состоит в уменьшении ранее наложенного штрафа, так что на следующей итерации для вышеприведенного примера следовало бы оштрафовать вершину Xi на - ау вместо - у, где О <а <1.

Ситуация, аналогичная описанной, возникает и тогда, когда вершина со степенью df = 1 сверхштрафуется на отрицательную величину, в результате чего после очередной итерации она получает > 2. В этом случае поступают как и в предыдущем.

В численных экспериментах, результаты которых приведены в табл. 10.2, было использовано значение а = 0,5.

( /) Вычисляемые штрафы

(а) Только положительные штрафы

В этом случае все вершины с > 2 штрафуются на р (г), где р (г) вычисляется как минимальный положительный штраф, который, будучи применен к вершине Xi (изолированно), уменьшает на одну единицу после одной итерации. Штрафы р (г) применяются тогда одновременно - каждый к своей вершине.

Величина р (г) для заданной вершины Xi вычисляется следующим образом. Удалим из дерева Т = (X, А^) только одно из ребер {Xi, Xj.), инцидентных вершине Xj. Это приведет к распадению Т на два поддерева и Т^. Найдем ребро наименьшего веса, соединяющее эти два поддерева, т. е. найдем ребро (xj, xl) с весом

с(а:, а:ь) = min min [с(а:,-, ar)], (10.16)

где х) и Xh - оптимальные значения Xj и а: соответственно, а Ti и обозначают как деревья, так и соответствующие множества их вершин. Вес с (а: , xJ) является поэтому наименьшим весом связи поддеревьев Т^ тл Т^ одно дерево, когда удалено первоначальное ребро (а:,-, Хг). Таким образом, штраф с (а:, а:) -



С (Xi, Хг), налагаемый на вершину Xt, является наименьшим штрафом, который удалил бы ребро (х;, х^) из кратчайшего остова при следуюш;ей итерации. Поэтому если штраф выбран как

p(i)= min [c{x:,x)-c(xi,xr)h (10.17)

то штраф р (i), наложенный только на вершину Xf, удалил бы (в предположении, что р (i) является единственным) только одно ребро (Xi, X*) из множества ребер, инцидентных Xi, т. е. уменьшил бы на единицу. Ребро (а;,-, х*) является как раз тем ребром, которое минимизирует выражение (10.17).

Здесь следует отметить, что когда все штрафы р (i), вычисленные по (10.17), накладываются одновременно каждый на свою вершину, степени некоторых вершин могут уменьшиться более чем на 1, в то время как степени других вершин могут вообще не уменьшиться (или могут даже увеличиться). Это объясняется совместным влиянием штрафов вершин на веса ребер при следующей итерации. Таким образом, хотя использование штрафов, найденных из (10.17), не гарантирует получение ответа после заданного числа итераций, но, как было обнаружено (см. табл. 10.2), этот метод штрафования лучше, чем методы (I) и (II).

(Ь) Только отрицательные штрафы

Это тот случай, когда все вершины х^ с = 1 штрафуются на отрицательную величину р (i), где р (i) вычисляется как максимальный (наименьший отрицательный) штраф, который, будучи применен только к вершине Xi, сделает степень df равной 2 после одной итерации, т. е. добавит второе ребро к вершине Xi. Однако штрафы р (i) применяются одновременно - каждый к своей вершине.

Значение р (i) для данной вершины xt вычисляется следующим образом. Добавим ребро (х;, Хг) к дереву Т. Это добавление приведет к замыканию цикла, составленного из ребра (xt, Хг) вместе с ребрами дерева Т, входящими в цепь от Хг до Х;. Пусть множество ребер дерева Т в цепи от х^ до Xt (исключая последнее ребро, инцидентное Xi) будет St- Если тогда добавить ребро (х;, х^} к ребрам Т и удалить одно какое-либо ребро из iS,-, то получится другое дерево, в котором степень вершины Xt равна двум. Если, таким образом, накладывается единственный штраф р (i) на вершину Xi, где

p{i) = minlc{Xi, Хг)- min {c(xj,Xk)}], (10.18)

(т. е. р (i) равен наименьшему дополнительному весу добавления ребра от Xi к какой-нибудь другой вершине х^ и удаления ребра



Таблица 10.2

Вычислительные результаты в методе штрафования вершин

Число вершин п

Стратегия штрафования

1(c)

П

а

а

а

а

а

д

а

Д

0,15

0,13

0,11

0,18

0,18

0,16

0,12

0,27

0,24

0,29

0,20

0,42

0,39

0,50

0,88

0,71

0,80

0,38

0,59

0,48

0,67

1,83

1,41

1,66

1,02

0,47

0,71

0,46

0,91

1,11

0,95

1,41

1,63

1,37

2,23

1,99

1,00

3,09

4,43

9,70

13,6

а: Число итераций Р Время вычисления (СдС 6600) t 1\аждый злемент является средним значением для 3 графов одного и того те размера



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 [ 92 ] 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

© 2024 Constanta-Kazan.ru
Тел: 8(843)265-47-53, 8(843)265-47-52, Факс: 8(843)211-02-95