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

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

(2) если Зг; 6 R, такое, что rt Su и $ Sj, V/ =5 /с, то Sh должно присутствовать во всех решениях и задачу можно свести к меньшей , положив R = R - {г,} -а S - - {и}

(3) пусть Vi = {У I Ti 6 Sj}\ тогда если Зр, 9 6 {1, f} такие, что Vp F то можно удалить из /?, поскольку любое множество, которое покрывает Гр, должно также покрывать г^, т. е. Гр доминирует над

(4) если для некоторого семейства множеств а S справедливы соотношения U Э iS и 2 ; ft Для любых

Sk - то Sh может быть вычеркнуто из S, поскольку и Sj доминирует над S-

Предположим, что все эти упрощения выполнены (если они возможны) и что исходная ЗНП уже переформулирована в соответствующей неприводимой форме.

4.3. Алгоритм решения ЗНР, использующий дерево понска

Как отмечалось ранее, ЗНР тесно связана с ЗНП, являясь по существу ЗНП с дополнительным (неперекрываемость) ограничением. Это ограничение выгодно, если мы пытаемся решить задачу с помощью некоторого метода, использующего дерево поиска: при таком ограничении может рано выясниться, что некоторые возможные ветвления дерева рассматривать не надо. Учитывая вышесказанное, мы сначала займемся алгоритмом решения ЗНР (использующим дерево поиска), а затем покажем, как его можно приспособить к решению ЗНП.

Простые методы решения ЗНР, использующие дерево поиска, были предложены Пирсом [48] и Гарфинкелем и Немхаузером [27].

Сущность этих методов такова. Вначале строятся блоки столбцов, по одному на каждый элемент из Д, т. е. всего М блоков, /с-й блок состоит из таких множеств семейства S (представленных столбцами), в которых содержится элемент г^, но отсутствуют элементы с меньшими индексами - Tj, . . ., r.j. Следовательно, каждое множество (столбец) появляется точно в одном определенном блоке и совокупность блоков может быть представлена в виде таблицы, как показано на рис. 3.1. В конкретных задачах некоторые из блоков могут отсутствовать.

В процессе работы алгоритма блоки отыскиваются последовательно и формирование к-то блока начинается после того, как каждый элемент г,-, 1 < г < /с - 1, будет покрыт частным решением. Таким образом, если какое-то множество в блоке к содержит элементы с индексами, меньшими к, то оно должно быть отбро-



шено (на этом этапе) в соответствии с требованием неперекрываемости.

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

Исходная таблица

Таблица 3,1

L ок 1

блок 2

Ьлок 3

Ьлок 4

l

Owul

etc.

Текущее наилучшее решение В со стоимостью z известно на любом этапе поиска {В обозначает семейство соответствующих покрывающих множеств). Если В ж z - соответствующие семейство и стоимость на данной стадии поиска, а Е - множество, представляющее те элементы (т. е. строки) г;, которые покрываются множествами из В, то один из простых алгоритмов, использующих дерево поиска, можно описать следующим образом.

Присвоение начальных значений

Шаг 1. Построить исходную таблицу и начать с частного решения: 5=0, Е = 0, z = 0 и z=oo.

Расширение

Шаг 2. Найти р = min Н \ Е]. Над блоком р поставить метку (над его первым множеством, которое, как следует из построения таблицы, имеет наименьшую стоимость).

Шаг 3. Начиная с отмеченной позиции в блоке р, перебирать его множества Sj, скажем, в порядке возрастания индекса /.

(i) Если найдено множество S, такое, что S [\ Е = 0 и z-bCj<:z (где cj -стоимость множества 5f), то перейти к шагу 5.



(ii) в противном случае, т. е. если блок р исчерпан или выбра-но множество iSf, такое, что z + Cj* > z, перейти к шагу 4.

Шаг возвращения

Шаг 4. В не может привести к лучшему решению. Если 5=0 (т. е. блок 1 исчерпан), то алгоритм заканчивает работу и оптимальным решением является В. В противном случае удалить последнее множество, скажем, 5h, добавить его в В, положить р = I, поставить метку над множеством S, удалить предшествующую метку в блоке I и перейти к шагу 3.

Проверка нового решения

Шаг 5. Обновить данные: В = В {} {5, Е = Е \] Sj, z = = z -f Cj*. Если найдено лучшее решение Е = R, то положить В = В, Z = Z я перейти к шагу 4. Иначе перейти к шагу 2.

Если поиск оканчивается с исчерпыванием блока 1 (см. выше шаг 4), то целесообразно переставить блоки в порядке возрастания числа столбцов (множеств) в каждом блоке. Это может быть осуществлено (перед построением исходной таблицы) перенумерацией элементов (строк) г^, . . ., Vjj в порядке увеличения числа множеств из S, содержащих соответствующие элементы.

Прежде чем показать, как алгоритм для ЗНР распространяется на ЗНП, кратко упомянем о некоторых других методах, применяемых при решении ЗНР. В [49] Пиро и Ласки дали ряд модификаций приведенного выше основного алгоритма, используя в качестве вспомогательного средства линейное программирование; в [45] Мишо описал другой алгоритм неявного перебора, который основан на задаче линейного программирования, соответствующей ЗНР с блочной структурой (рассмотренной выше и игравшей вспомогательную роль).

Предлагались также алгоритмы, включающие итерации симплексного типа, как прямые [4, 5], так и двойственные [58, 37]. В [37] Йенсен успешно применил метод динамического программирования к определенному типу ЗНР.

4.4. Алгоритм решения ЗНП, использующий дерево поиска

В алгоритме, описанном выше в разд. 4.3, единственным шагом, характерным для ЗНР, является шаг 3 (i). Если удалить в этом шаге требование неперекрываемости [] Е = 0, то алгоритм может быть использован для ЗНП. Однако в этом случае исходная таблица будет несколько отличаться от табл. 3.2. Итак, положим 7 = {п.- rj, rj3, . . .}, где /i </2 </з <. . . . Теперь недостаточно включить Sj только в блок 7i, поскольку без требования



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