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

РЕШЕНИЕ ЗАДАЧИ КОММИВОЯЖЕРА МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ

Читайте также:
  1. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  2. I. ЗАДАЧИ ПЕДАГОГИЧЕСКОЙ ПРАКТИКИ
  3. I. Решение логических задач средствами алгебры логики
  4. I. Ситуационные задачи и тестовые задания.
  5. II. Основные задачи и функции
  6. II. Решение логических задач табличным способом
  7. II. Типичные структуры и границы
  8. II. ЦЕЛИ, ЗАДАЧИ И ПРИНЦИПЫ ДЕЯТЕЛЬНОСТИ ВОИ
  9. II. Цель и задачи государственной политики в области развития инновационной системы
  10. III Общий порядок перемещения товаров через таможенную границу Таможенного союза
  11. III. Разрешение споров в международных организациях.
  12. III. Решение логических задач с помощью рассуждений

Задача коммивояжера формулируется следующим образом. Имеются (n+1)городов и заданны расстояниями между ними. Коммивояжер должен выехать из определенного города и вернуться в него, побывав в каждом из городов лишь один раз и проехав минимальное расстояние.

Пусть xij = 1, если коммивояжер переезжает из города i непосредственно в город j, и xij = 0 в противном случае. Задана матрица расстояний между городами

Для поиска оптимального (минимального) маршрута применим метод ветвей и границ.

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

Метод содержит три этапа: ветвление, пересчет оценок и отбрасывание вариантов.

Будем обозначать подмножества допустимых решений X (k,t), ξ (k,t) – оценку подмножества, где k – номер уровня разбиения, t – порядковый номер в уровне.


1 | 2 | 3 | 4 | 5 | 6 | 7 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)