Метода - ветвь
Cтраница 2
Очень легко приспособить для решения таких задач метод ветвей и границ. [16]
В [4] дается обзор некоторых других алгоритмов, например метода ветвей и границ. [17]
Специфика рассматриваемой задачи позволяет успешно применить для ее решения метод ветвей и границ. [18]
Эта последовательность должна быть предельно рациональна, должна строиться по методу ветвей и границ, - отсекающего целые семейства заведомо непригодных решений. [19]
Изложенное означает, что для того чтобы применить в данном случае метод ветвей и границ необходимо сначала сформировать указанные матрицы для всех возможных сочетаний ( h v), i и у, а потом уже реализовывать этот метод. Поэтому в данном случае эффективнее применить следующий эвристический комбинаторный алгоритм, позволяющий получить оптимальное решение в ходе генерации допустимых вариантов решения задачи. [20]
На рисунке знаком х обозначается, что дальнейшее рассмотрение прерывается по методу ветвей и границ, так как сложность функции заведомо не будет улучшена. Минимальная сложность / 1 получилась равна единице. [21]
Для решения многомерной задачи о рюкзаке разработаны алгоритмы, основанные на методе ветвей и границ и на идеях динамического программирования. При относительно малой размерности задачи эти алгоритмы достаточно эффективны. [22]
Для решения задач используется ряд методов линейного программирования, дискретного программирования, методы ветвей и границ, сетевого планирования и управления. [23]
В комбинированных алгоритмах могут применяться как общие правила отсева, применяемые в методе ветвей и границ ( при поиске точных и приближенных решений), так и правила отсева, использующие специфику задачи. Примером может служить отсев с использованием принципа оптимальности Беллмана для задачи коммивояжера. Разумеется, применение отсева с учетом специфики задачи требует дополнительных вычислительных ресурсов. [24]
Наиболее удачный алгоритм порождения всех остовных деревьев графа аналогичен показанному на рис. 4.17 методу ветвей и границ для решения задачи коммивояжера. Множество всех остовных деревьев графа G делится на два класса: класс, содержащий выделенное ребро ( и, и), и класс, его не содержащий. [25]
В динамических АСУ для решения задач такого типа используются также методы теории расписаний, методы ветвей и границ, приближенные и эвристические методы. Это могут быть методы пошагового решения, последовательного анализа вариантов, а также методы случайных выборов, называемый методом статистических испытаний или методом Монте-Карло - Теория расписаний часто оперирует известными методами ( в основном динамического программирования) в приложении к конкретным классам задач по определению оптимальной последовательности решений, поэтому результаты теории также являются полезными для динамических АСУ. [26]
Соответственно, время работы алгоритмов, основанных на полном переборе или на построении дерева решений ( методы ветвей и границ, золотого сечения и др.), растет экспоненциально в зависимости от числа вершин графа. Эти алгоритмы способны решать задачу для малого числа вершин ( п и 20) за полиномиальное время. Поэтому для решения сложных задач о коммивояжере используются различные эвристики. [27]
 |
Дерево вариантов в задаче резервирования. [28] |
Отметим еще, что рассматриваемые нами состояния образуют дерево вариантов ( рис. 66) - такое же, как в методе ветвей и границ, - и отличие метода переработки списка состояний заключается в том, что отбрасывание вариантов производится по результатам их попарного сравнения. [29]
Итерационные алгоритмы ( например, метод парных перестановок, метод групповых перестановок, методы, использующие механические или электрические аналогии, методы ветвей и границ), которые улучшают начальное размещение, имеют преимущество перед конструктивными алгоритмами. Оно заключается в том, что на любом этапе работы итерационного алгоритма уже существует законченный вариант размещения, пригодный для практического использования. [30]
Страницы: 1 2 3 4