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

Глава 11. Задача коммивояжера

Читайте также:
  1. I. 3.1. Двойственная задача линейного программирования
  2. I. ГЛАВА ПАРНЫХ СТРОФ
  3. II. Глава о духовной практике
  4. II.2. Задача о назначениях
  5. II.4. МЕТОД ВЕТВЕЙ И ГРАНИЦ В ЗАДАЧАХ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ
  6. III. Глава о необычных способностях.
  7. IV. Глава об Освобождении.
  8. IV. Глава подразделения по стране
  9. VI. Общая задача чистого разума
  10. XI. ГЛАВА О СТАРОСТИ
  11. XIV. ГЛАВА О ПРОСВЕТЛЕННОМ
  12. XVIII. ГЛАВА О СКВЕРНЕ

 

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

На каждом шаге описываемого алгоритма задача включает n городов, причем из n шагов маршрута k могут быть уже установлены и нужно выбрать оптимальным образом оставшиеся .

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

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

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