Дерево - вариант
Cтраница 2
Отметим еще, что рассматриваемые нами состояния образуют дерево вариантов ( рис. 66) - такое же, как в методе ветвей и границ, - и отличие метода переработки списка состояний заключается в том, что отбрасывание вариантов производится по результатам их попарного сравнения. [16]
 |
Дерево вариантов приводов. [17] |
На рис. 1.14 показано множество структур приводов в виде дерева вариантов. Поскольку каждая ветвь имеет вес 0 или 1, дерево является бинарным. Ветвление дерева идет по уровням ключевых элементов привода начиная с корня А. Нулевой или единичный вес каждой ветви присваивается коэффициенту соответствующего уровня. На последнем ветвлении получаются полные структурные варианты приводов подач. [18]
На рис. 128 показано множество структур приводов в виде дерева вариантов. [19]
Таким образом, введение указанного эвристического правила позволяет существенно сократить дерево вариантов. Но введение всякого эвристического правила должно приводить к ухудшению схем теплообмена ( увеличению 3), так как схемы выбираются из ограниченного множества вариантов. Значит, с одной стороны, эвристическое правило полезно, с другой - вредно. Вопрос о применении того или иного эвристического правила может быть в какой-то степени решен экспериментально: если при применении эвристического правила решение задачи синтеза сильно облегчается, а 3 увеличивается слабо, то такое эвристическое правило, конечно, следует применять при решении практических задач синтеза. [20]
Формально процесс поиска искомого решения может быть представлен в виде некоторого дерева вариантов, где каждая вершина ( не концевая) соответствует определенному частичному решению. [21]
Для поиска оптимальных решений ИЗС используют три операции упорядоченного перебора вершин дерева вариантов: волнового ветвления, лучевого ветвления и волно-лучевого ветвления. [22]
 |
Дерево вариантов. [23] |
Сущность комбинаторных методов состоит в том, что для решения задачи строится дерево вариантов или порфириан. [24]
Для полного детального описания алгоритма нам не достает только способа задания информации о дереве вариантов. Удобный метод задания этой информации был предложен А. Вся информация задается целочисленным вектором g IN ], в котором glN N ] - О Ш N ], g [ / ] k, если х [ / ] было k - и по счету единицей в текущем частичном решении ( отмененные единицы здесь не учитываются), g [ / ] - k, если х [ / ] было сделано нулем между назначением ( k - 1) - й и k - й единицы в данном частичном решении. [25]
Отметим, что уравнение ( 14) охватывает также задачи оптимального управления при поиске на дереве вариантов; при этом оптимальное управление в га-м приближении по ( 18) состоит в выборе управления по результатам прощупывания веточек дерева на п шагов вперед. [26]
Описанный метод называется методом ветвей и границ, так как в нем поиск оптимального решения идет по ветвям дерева вариантов, и при этом ветвлении используются границы - оценки. [27]
В работе [41 ] для задачи синтеза оптимальных систем теплообмена были впервые применены вышеизложенные идеи решения комбинаторных задач путем построения сокращенного дерева вариантов. Прежде всего, было введено эвристическое правило: в оптимальной схеме теплообмена при теплообмене между какими-то горячим и холодным потоками переходит максимальное количество теплоты, допускаемое минимальным температурным сближением DTmin. Это эвристическое правило резко сокращает дерево вариантов, максимальное число висячих вершин падает от пгп до ml ( от NN до ЛП для задачи синтеза систем теплообмена), так как в каждой схеме любая пара потоков встречается только один раз. [28]
Понятно, что при переборе вариантов из всех эквивалентных представлений достаточно взять только одно, за счет чего и сокращается дерево вариантов. Поэтому важно уметь определять эквивалентность представлений. Эквивалентность представлений определяется с помощью следующей теоремы. [29]
После того как предметы, весящие более 30 кг, удалены, а остальные расположены в каком-либо порядке, определим дерево вариантов следующим образом. [30]
Страницы: 1 2 3 4