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

АННОТАЦИЯ

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

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

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

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

В заключении приведены основные выводы, полученные в результате проведенного исследования.

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ.

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ.

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

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

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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