Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Метод ветвей и границ. Решение коммивояжера






    Метод вариаций используется в задачах, где можно произвести полный анализ задач, т.е. полный перебор вариантов. Если такое невозможно, то используются методы неполного перебора, напр. Метод ветвей и границ:

    Нужно найти х0 . Число Сn – граница множества М, если .

    Алгоритм:

    6. Мн-во М разбиваем на не пересекаемые подмн-ва:

    7. На каждом подмн-ве находим границу. Сn* – точная граница, если

    8. Если есть точные границы у подмн-в, то находим самую наименьшую из них. Т.е. подмн-ва, у которых границы Ci > Cn исключаем из рассмотрения.

    9. Если все подмн-ва исключены, то останавливаем алгоритм.

    10. Если существует мн-во, у которого Сi*< Сn, то данное подмн-во снова разбиваем и переходим к п.2.

    Для реализации алгоритма используется схема:

    Задача Коммивояжера:

    Пусть имеется n- населённых пунктов, соединенных дорогами. Расстояние между пунктами заданы матрицей:

    Если между пунктами и нет соед. их дороги, то .

    Требуется составить маршрут проход. через все пункты ровно по одному разу с возвратом в исходную точку, имеющую минимально возможную длину.

    Для использования метода ветвей и границ выберем след. способ ветвления: будем выбирать одну из дорог к одному из подмн-в отнесем все маршруты, проход. через данную дорогу, а в другом маршруте все дороги не использующие ее.

    В первом случае, удаляем из матрицы строку и столбец соответственно выбранной дороге. После чего, остальные звенья маршрута будем искать по оставшимся элементам матрицы.

    Во втором случае, данное значение коэффициента матрицы .

    Точную границу будем определять след. образом:

    1. Находим минимум в каждой строке.

    2. Находим минимум по каждому столбцу.

    Тогда начальная оценка.


     






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.