Экономико-математическое моделирование : Решение задачи о коммивояжере

Решение задачи о коммивояжере

Аннотация

Задача о коммивояжере состоит в том, чтобы объехать заданные города по одному разу в таком порядке, чтобы пройденное расстояние было минимальным.

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

Оглавление

• Введение3
• Постановка задачи4
• Метод решения5
• Язык программирования7
• Описание алгоритма8
• Описание основных структур данных12
• Описание интерфейса с пользователем14
• Заключение16
• Литература17
• Текст программы18

Задача состоит в том, чтобы коммивояжер (торговец) обошел все намеченные города единожды и в таком порядке, чтобы его путь был наименьшим.

Эта задача заинтересовала меня потому, что её решение интересно с точки зрения программирования и составления алгоритма. Важно нахождение такого алгоритма, который позволит наиболее оптимально решить задачу.

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

Поэтому данная проблема на современном этапе развития общества имеет не самое последнее по значимости место.