Курсовая работа: Задача коммивояжёра

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ. 2

1.ТЕОРЕТИЧЕСКАЯ ЧАСТЬ. 2

1.1Неформальная постановка задачи коммивояжёра. 2

1.2Постановка задачи коммивояжёра в терминах теории графов. 2

1.3Математическая модель задачи. 2

1.4Принадлежность к классам сложности. 2

2.ПРАКТИЧЕСКАЯ ЧАСТЬ. 2

2.1Алгоритм полного перебора. 2

2.2Алгоритм ветвей и границ. 2

ЗАКЛЮЧЕНИЕ. 2

БИБЛИОГРАФИЧЕСКИЙ СПИСОК.. 2

ПРИЛОЖЕНИЯ.. 2

ВВЕДЕНИЕ

Комбинаторика – раздел элементарной математики, изучающий количество комбинаций, подчиняющихся тем или иным условиям, которые могут быть сформированы из заданного конечного набора объектов (любой природы, например, букв, цифр, произвольных символов) [1].

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

Задача коммивояжёра впервые появляется в письменном виде в немецкой брошюре, которая была опубликована в 1832 году под названием «Коммивояжёр – каким он должен быть и что он должен делать для того, чтобы получать заказы и быть уверенным в счастливом успехе своего предприятия, – составлено опытным коммивояжёром». Австрийский математик Карл Менгер назвал задачу коммивояжёра «задачей посыльного», и он был первым, кто обсуждал ее в технической литературе в конце 1920-х и начале 1930-х годов [2, с. 612].

Одним из ранних вариантов задачи можно назвать игру “Икосиан”, разработанную ирландским математиком Уильямом Гамильтоном в 1857 году. В ней нужно было найти маршруты на графе с двадцатью узлами [3, с.193].

Некоторое время спустя появилась и известная вариация задачи — задача странствующего торговца (коммивояжёра), которую предложил американский математик Хасслер Уитни [4, с. 244].

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

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

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

Объект исследования – задача коммивояжёра.

Цель курсовой работы – изучить алгоритм решения задачи коммивояжёра методом ветвей и границ и методом полного перебора. Реализовать алгоритмы решения задачи коммивояжёра на языках программирования Pascal и Python.

Поставленная цель определила следующие задачи:

1. Изучить теоретические основы задачи коммивояжёра, методы её решения и существующие подходы к реализации алгоритмов.
2. Ознакомиться с алгоритмом решения задачи коммивояжёра методом полного перебора.
3. Реализовать алгоритм решения задачи коммивояжёра методом полного перебора на языке программирования Python.
4. Ознакомиться с алгоритмом решения задачи коммивояжёра методом ветвей и границ.
5. Реализовать алгоритм решения задачи коммивояжёра методом ветвей и границ на языке программирования Pascal.
6. Проанализировать полученные результаты и сделать выводы о преимуществах и недостатках каждого из методов решения задачи коммивояжёра.