Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Представим, что необходимо обойти все города страны. Так как их много, то определить кратчайший путь затруднительно. Тогда можно выбрать некоторое разбиение множества городов, например, рассматривать республики, области или районы, и определить кратчайший путь, пересекающий каждое из выбранных подмножеств разбиения только один раз. Затем уже в пределах выбранных подмножеств достроить полученный путь до требуемого. Такой подход используется в методе ветвей и границ. Этот метод позволяет опознать бесперспективные частичные решения, в результате чего от дерева поиска на одном шаге отсекается целая ветвь. Тем не менее, удовлетворительных оценок быстродействию алгоритма Литтла, основанного на этом методе, и родственных алгоритмов нет, хотя практика показывает, что на современных ЭВМ они иногда позволяют решить задачу коммивояжера для графов с количеством вершин, меньшим 100.
Впервые метод ветвей и границ был предложен Лендом и Дойгом в 1960 для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его “второе рождение” связано с работой Литтла, Мурти, Суини и Кэрела, посвященной задаче коммивояжера. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям. Столь большой успех объясняется тем, что авторы первыми обратили внимание на широту возможностей метода, отметили важность использования специфики задачи и сами воспользовались спецификой задачи коммивояжера.
Дата публикования: 2014-12-08; Прочитано: 298 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!