Правило - ветвление
Cтраница 1
Правило ветвления В для алгоритма указывает способ получения из Д0 ( Х) новых разрезаний Д ( Х), используя для ветвления ДД-операцию. [1]
Правило ветвления ставит в соответствие области R некоторое конечное дерево подмножеств. Конечность дерева подмножеств следует из конечности пространства X. [2]
Правило ветвления, которое определяет процесс ветвления по отношению к дереву поиска; назначение правила заключается в разбиении пространства решений на непересекающиеся подмножества, которые либо подвергаются дальнейшему исследованию, либо отбрасываются. [3]
Правило ветвления Bf описывает процесс ветвления в задаче о перестановках. [4]
Выбирается также правило ветвления, состоящее в выборе разветвляемого подмножества X из числа подмножеств, на которые к данному шагу разбито множество X, и выборе способа разбиения X на непересекающиеся подмножества. Обычно из числа кандидатов на ветвление выбирается множество X с наименьшей оценкой, поскольку именно в таком множестве естественно искать минимум в первую очередь. [5]
Таким образом, правило ветвления задает некоторое разбиение области допустимых решений на подмножества. [6]
 |
Шаги алгоритма динамического программирования FLDS. [7] |
Вь представляет собой правило ветвления для задачи двоичного разбиения. L Тогда я о представляет листья полного поддерева, имеющего пга в качестве корня. Это поддерево соответствует множеству полных решений, имеющих в качестве общего предка частичное решение пга. [8]
В алгоритме Литтла правилом ветвления служит способ определения пары ( / с, Z), по которой производится разбиение. [9]
 |
Поиск, использующий дерево решений из примера. [10] |
А дерева решений, показанного на рис. 10.19. Исключение цикла ( 2, 4, 3) по правилу ветвления В приводит к трем подзадачам, изображаемых на рис. 10.19 узлами В, С ж О. [11]
Поскольку в оптимальной вершине соответствующее множество делится на два множества, то иногда говорят о ветвлении в оптимальной вершине, а правило разбиения называют правилом ветвления. [12]
Ясно, что если при некотором / G3 старая нижняя оценка функционала совпадает с новой, то при /: / оценки можно не перечитывать, Итак, основные вопросы, возникающие при использовании метода ветвей и границ, состоят в оценке минимального значения функционала на подмножестве множества допустимых решений и в определении правила ветвления дерева допустимых решений. [13]
БВЬ оказывается, по меньшей мере, такой же, а часто и превышает оценку, достигнутую алгоритмом ВВг. Поскольку мы исполь-зуем правило ветвления LLB, то активная вершина, имеющая наименьшую нижнюю оценку стоимости, всегда является текущей вершиной ветвления. Эта нижняя оценка стоимости, обозначенная L, совместно с окончательной верхней оценкой 0 может быть использована для оценки точности приближения к оптимальному решению. [14]
Рассмотрим более тонкий алгоритм субоптимального разрезания х графа, основанный на структурированном методе ветвей и границ. Алгоритм структурируется в виде семерки А - ( и, В, L, F, D, S, Е), где R - правило представления разрезания, В - правило ветвления, L - функция характеристики разрезания, F - граничная функция, D - правило предпочтения разрезания, S - правило выбора разрезания, Е - правило исключения разрезаний. [15]
Страницы: 1 2