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

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

ПРИЛОЖЕНИЕ 1

(а) Возможно разбиение Pj на четыре подзадачи Pj, Pjj, Pj, и Pj4, причем для подзадачи Р; мы полагаем = а, для Pj полагаем I = Ь, для Pjg - = с и для Pj4 - = d. Каждая




Рис. П.З. Три возможных способа ветвления в вершине

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

(б) Возможно другое разбиение Pj на две подзадачи Pj и Р,, где для Pj, мы полагаем = а, а для Р, полагаем а, т. е. I равно Ь, с или d (рис. П.З (б)).

(в) Еще одно возможное разбиение Pj на две подзадачи Р и Рг, где для Pi, I = а или Ь, а для Pj = с или d (рис. П.З (в)).

Все три ветвления являются допустимыми и удовлетворяют условию (П.З). Какому из них отдать предпочтение - зависит от природы решаемой задачи, причем возможности типа (а) или (б) используются чаще остальных.

3. Типы поиска, использующего дерево решений

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

3.1. Поиск по глубине

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




СледующЕЕ / Задача решена

ветвление начинать

здесь

Рис. п.4а. Дерево поиска по глубине.


Рис. П.46. Дерево поиска по ширине. Задача решена.

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

3.2. Поиск по ширине

При поиске по ширине ветвление происходит от уровня к уровню, так что если на уровне 1 начальная задача Ро разбивается на подзадачи Р^, Р^ , Pk, о каждая из этих подзадач исследуется раньше, чем задачи уровня 2. Задачи уровня 1, которые не могут быть разрешены, разбиваются на подзадачи уровня 2, и опять все они исследуются до исследования какой-либо подзадачи, могущей возникнуть на уровне 3, и т. д. Вид дерева решений при этом типе поиска показан на рис. П.46.

4. Применение границ

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



5. Функции ветвления

Как при поиске по глубине, так и при поиске по ширине выбор очередной вершины для ветвления не был полностью определен.

При поиске по глубине, когда после ветвления задача Р; разбивается на подзадачи Pj, . . ., Pj, очередное ветвление, как уже говорилось, производится в одной из этих только что порожденных подзадач. Но мы не указали, в какой именно, и любая из них может рассматриваться как последняя порожденная . При поиске по ширине, как уже было сказано, все подзадачи данного уровня должны исследоваться до исследования задач следующего уровня, но не был указан порядок их исследования.

Функция ветвления - это функция, которая позволяет вычислить , какая из допустимых вершин должна использоваться при следующем ветвлении. Для вершины, соответствующей подзадаче Рj, эта функция является некоторой мерой вероятности того, что оптимальное решение всей задачи Ро является решением для Pj. Совершенно очевидно, что вершина, соответствующая подзадаче с большими шансами на оптимальное решение, должна пользоваться правом преимущественного выбора при очередном ветвлении. Можно указать несколько эвристических мер этой вероятности, причем одна из полезных мер связана просто с вычислением для вершин нижних или верхних границ. Для такой меры вершина с более низкой нижней границей (для случая минимизации) считается имеющей большую вероятность.

После введения понятия функции ветвления сразу же возникает мысль о другом типе поиска с деревом решений (в дополнение к описанным ранее поискам по глубине и ширине). Можно использовать функцию ветвления и так, чтобы она полностью определяла выбор следующей для ветвления вершины. Например, если значениями функции ветвления являются границы вершин (нижние и верхние), как упоминалось выше, то всегда можно производить ветвление в той висячей вершине, нижняя граница которой наименьшая. Этот тип поиска является, вообще говоря, гибридом поисков по глубине и ширине, хотя в литературе он часто называется поиском по ширине.

соответствует рассматриваемой висячей вершине. Таким образом (для задачи минимизации), если окажется, что нижняя граница для вершины, соответствующей задаче Р^, больше, чем величина наилучшего ответа, полученного ранее при поиске, то в Pi нет необходимости производить дальнейшее ветвление, так как в {Р,} нет решения, лучшего, чем текущий наилучший ответ. В соответствии с толкованием (II) термина разрешение задачи из разд. 1 подзадача Р; окажется автоматически разрешенной.



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