Функция - ветвление
Cтраница 1
 |
Дерево 7 ( v l при прямом шаге. [1] |
Функция ветвления строится отдельно для каждого алгоритма ВВС. [2]
Функция ветвления - это функция, которая позволяет вычислить, какая из допустимых вершин должна использоваться при следующем ветвлении. Совершенно очевидно, что вершина, соответствующая подзадаче с большими шансами на оптимальное решение, должна пользоваться правом преимущественного выбора при очередном ветвлении. Можно указать несколько эвристических мер этой вероятности, причем одна из полезных мер связана просто с вычислением для вершин нижних или верхних границ. Для такой меры вершина с более низкой нижней границей ( для случая минимизации) считается имеющей большую вероятность. [3]
Функция ветвления - это функция, которая позволяет вычислить, какая из допустимых вершин должна использоваться при следующем ветвлении. Для вершины, соответствующей подзадаче Р -, эта функция является некоторой мерой вероятности того, что оптимальное решение всей задачи Р0 является решением для PJ. Совершенно очевидно, что вершина, соответствующая подзадаче с большими шансами на оптимальное решение, должна пользоваться правом преимущественного выбора при очередном ветвлении. Можно указать несколько эвристических мер этой вероятности, причем одна из полезных мер связана просто с вычислением для вершин нижних или верхних границ. Для такой меры вершина с более низкой нижней границей ( для случая минимизации) считается имеющей большую вероятность. [4]
Построить функцию ветвления, определяющую, какая из двух задач PI ( V) и P2 ( v), образованных при разбиении задачи P ( v), подлежит исследованию на следующей итерации. [5]
Особенностью данного алгоритма является построение в рассматриваемой схеме эффективной функции ветвления В, которая использует ДД-операцию. Это позволяет надеяться на получение хорошего приближения к оптимальному решению. [6]
 |
Дерево 7 ( v l при прямом шаге. [7] |
При прямом шаге необходимо указать правила выбора пары Ярд, используемой для разбиения задачи P ( v), и построить функцию ветвления, определяющую, какая из подзадач Р: ( v) / ( v) будет исследоваться на следующей итерации. [8]
В качестве активной вершины ДВР на каждом / - м уровне декомпозиции НФЗ может быть выбрана только такая вершина nk, для которой величина ее функции ветвления, или критерия выбора, не превосходит значения ВГ. [9]
Например, если значениями функции ветвления являются границы вершин ( нижние в верхние), как упоминалось выше, то всегда можно производить ветвление в той висячей вершине, нижняя граница которой наименьшая. Этот тип поиска является, вообще говоря, гибридом поисков по глубине и ширине, хотя в литературе он часто называется поиском по ширине. [10]
Построение осложняется технической трудностью; 51 ( Я) должен быть построен так, чтобы сдвигать каждую ленту непосредственно после чтения с нее символа; поэтому, если символ на ленте должен регулировать более чем один переход из состояния в состояние, то должны быть предприняты специальные шаги, чтобы переписать этот символ во внутреннее состояние автомата. При построении & ( Р), моделирующем Р, эта трудность встречается всякий раз на символах, фиксирующих значения функции ветвления Tj. Чтобы преодолеть ее, схема Р прежде всего должна быть преобразована в эквивалентную ей и более ограниченную схему, в которой ячейки проверяются только непосредственно после акта присваивания ( фактически это и есть по Патерсону ( см. [5]) процесс превращения либеральной схемы в свободную), либо автомат ЭД ( Р) прежде всего должен быть сделан как автомат с некоторой несущественной дополнительной способностью к переписи предварительно прочитанных симв9лов, либо нужно задавать сразу прямое преобразование. [11]
Страницы: 1