![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Метод ветвей и границ. Решение коммивояжера
Метод вариаций используется в задачах, где можно произвести полный анализ задач, т.е. полный перебор вариантов. Если такое невозможно, то используются методы неполного перебора, напр. Метод ветвей и границ: Нужно найти х0 Алгоритм: 6. Мн-во М разбиваем на не пересекаемые подмн-ва: 7. На каждом подмн-ве находим границу. Сn* – точная граница, если 8. Если есть точные границы у подмн-в, то находим самую наименьшую из них. Т.е. подмн-ва, у которых границы Ci > Cn исключаем из рассмотрения. 9. Если все подмн-ва исключены, то останавливаем алгоритм. 10. Если существует мн-во, у которого Сi*< Сn, то данное подмн-во снова разбиваем и переходим к п.2. Для реализации алгоритма используется схема: Задача Коммивояжера: Пусть имеется n- населённых пунктов, соединенных дорогами. Расстояние между пунктами заданы матрицей: Если между пунктами Требуется составить маршрут проход. через все пункты ровно по одному разу с возвратом в исходную точку, имеющую минимально возможную длину. Для использования метода ветвей и границ выберем след. способ ветвления: будем выбирать одну из дорог к одному из подмн-в отнесем все маршруты, проход. через данную дорогу, а в другом маршруте все дороги не использующие ее. В первом случае, удаляем из матрицы Во втором случае, данное значение коэффициента матрицы Точную границу будем определять след. образом: 1. Находим минимум в каждой строке. 2. Находим минимум по каждому столбцу. Тогда
|