Метода - ветвь
Cтраница 4
Другим подходом является максимальное сокращение объема перебора при решении задачи, хотя при этом признается возможность экспоненциального времени работы алгоритма на какой-либо из индивидуальных задач. К наиболее широко используемым приемам сокращения перебора относятся приемы, основанные на методе ветвей и границ или других методах неявного перебора. Эти приемы состоят в построении частичных решений, представленных в виде дерева поиска и применении мощных методов построения оценок, позволяющих идентифицировать бесперспективные частичные решения, в результате чего от дерева поиска на одном шаге может быть отсечена целая ветвь плохих решений. Известны и другие методы, кроме метода ветвей и границ. [46]
При использовании автоматических штабелеров на многономенклатурных комплектовочных складах эффективно применение ЭВМ для выбора оптимальной траектории перемещения. Решение этой задачи основано на методах линейного программирования, например, на методе ветвей и границ, методе коммивояжера и др. При значительном числе точек отбора ( 10 - 15) точное определение наивыгоднейшей траектории связано со значительными затратами машинного времени. [47]
КОМБИНАТОРНЫЕ МЕТОДЫ РЕШЕНИЯ ЭКОНОМИЧЕСКИХ ЗАДАЧ [ combinatorial methods in economics ] - совокупность ( не вполне определенная) методов, основанных на идеях комбинаторики - отдела математики, изучающего вопросы, связанные с размещением, перемещением и взаимным расположением частей конечного множества объектов. Они состоят либо в замене исходной задачи деревом более легких задач ( см. Методы ветвей и границ), либо в построении правил, отсеивающих заведомо неоптимальные варианты решения. [48]
Вычисление медианы Кемени является задачей целочисленного программирования. Для ее нахождения используют различные алгоритмы дискретной математики, в частности, основанные на методе ветвей и границ. Применяют также алгоритмы, основанные на идее случайного поиска, поскольку для каждого бинарного отношения нетрудно найти множество его соседей. [49]
 |
Типовая графовая модель вариантов построения основных подсистем информационного обеспечения АСУ. [50] |
Необходимость в оптимизации отдельных подсистем информационного обеспечения, а следовательно, и в решении подобных задач возникает как в процессе синтеза, так и при эксплуатации системы. Ниже для оптимизации подсистем формирования выхода из главных массивов и главных массивов из входа системы применяются методы ветвей и границ и динамического программирования. [51]
Основные принципы динамического программирования хорошо прослеживаются на примере задачи о коммивояжере. Начнем с этого примера, не забывая, однако, о том, что для задачи о коммивояжере метод ветвей и границ значительно эффективнее метода динамического программирования. [52]
Наибольшее распространение получили поисковые методы как наиболее гибкие и универсальные. Кроме того, поисковые методы могут быть эффективно использованы при синтезе оптимальной структуры химико-технологических систем, который в общем случае представляет собой задачу дискретно-непрерывного программирования; в частности, они могут быть использованы при получении нижних оценок в методе ветвей и границ ( см. гл. [53]
Страницы: 1 2 3 4