Cтраница 4
Так как метод ветвей и границ в данном случае неэффективен, а эвристика бесполезна, найти решение задачи о выполнимости вообще весьма сложно. [46]
Можно применить метод ветвей и границ к этой задаче и более эффективно. [47]
Основная идея метода ветвей и границ крайне проста. Используя некоторый способ, множество допустимых решений разбивают на подмножества. Далее каждое подмножество в свою очередь по этому или другому способу разбивается на подмножества. Такое деление выполняется до конечного единичного варианта. Построение схемы ветвления составляет процедуру перебора, которая может осуществляться различными способами. Оценивая образуемые подмножества по экстремальному значению целевой функции, сокращают перебор. При выполнении определенных соотношений исключаются из дальнейшего рассмотрения отдельные подмножества, так как в них заведомо отсутствует оптимальное решение. Выбор оценок и схемы ветвления взаимосвязаны и зависят от специфики решаемой задачи. Общие рекомендации по применению на практике данного метода отсутствуют. [48]
Для реализации метода ветвей и границ применительно к задаче о коммивояжере необходимо конкретизировать правила ветвления, вычисления оценок и нахождения решений. [49]
Узловым элементом метода ветвей и границ является использование возможности получения оптимистических оценок выигрыша, соответствующего выбираемой ветви дерева или совокупности ветвей, имеющих общее начало. [50]
С помощью метода ветвей и границ можно сокращать множество ветвей некоторых деревьев, что позволяет точно решать задачи большой сложности. [51]
В основе методов ветвей и границ лежат следующие основные алгоритмы, позволяющие для достаточно широкого класса целевых функций - и ограничений существенно уменьшить объем перебора. [52]
Между алгоритмами метода ветвей и границ, положенными в основу большинства используемых программ для ЭВМ, и описанным выше алгоритмом имеются определенные различия, которые главным образом связаны с правилами выбора последовательности рассмотрения подзадач и переменных, инициирующих процессы ветвления в вершинах. Обычно это эвристические правила, разработанные в ходе машинных экспериментов. [53]