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

Министерство  образования и науки Российской Федерации

ГОУ ВПО Магнитогорский государственный  технический университет

им. Г.И. Носова

СП  «Многопрофильный колледж»

Направление подготовки «Металлургия, машиностроение и автоматизация»

Тема

Пояснительная записка

к курсовому  проекту по дисциплинам:

Математические  методы и Технология разработки программных  продуктов

КП. 230105.24.00. 00. ПЗ

 

 

 

Руководители проекта

………………  Н. Н. Буркова

«…»………………………….2011

……………. Л.А. Фетисова

«…»………………………….2011

Разработал  студент

группы  ПРК – 07 – 9

……………….Туронёк  А.С

2011

 

 

 

Содержание

Введение

1.Теоретическое обоснование решения  задачи коммивояжёра;

2.Пример решения задачи коммивояжёра  одним из методов;

3.Решение задачи коммивояжёра  средствами MS Excel;

4.Алгоритм решения задачи;

5.Листинг программы для решения  задачи.

Литература                                          

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

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

Комбинаторика – раздел математики, посвящённый решению задач выбора и расположения элементов некоторого, обычно конечного множества в соответствии с заданными правилами.  

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

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

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

Большой вклад в систематическое развитие комбинаторных методов был произведен Г. Лейбницем (диссертация "Комбинаторное искусство"), Я. Бернулли (работа "Искусство предположений"), Л. Эйлером. Можно считать, что с появлением работ Я. Бернулли и  Г. Лейб-ница комбинаторные методы выделились в самостоятельную часть математики. В работах Л.Эйлера по разбиениям и композициям натуральных чисел на слагаемые было положено начало  одному из основных методов перечисления комбинаторных конфигураций – методу производящих функций. В 1859 г. У. Гамильтон придумал игру "Кругосветное путешествие", состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа, чтобы посетить каждую вершину однократно и возвратиться в исходную. Пути, обладающие таким свойством, называются гамильтоновыми циклами.

Разделы комбинаторики:

- Перечислительная комбинаторика

- Структурная комбинаторика

- Экстремальная комбинаторика

- Теория Рамсея

- Вероятностная комбинаторика

- Топологическая комбинаторика

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

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

Методы  решения.

Простейшие:

-полный перебор

-случайный перебор

-жадные алгоритмы

-метод ближайшего соседа

-метод включения ближайшего города

-метод самого дешёвого включения

-метод минимального остовного дерева

-метод имитации отжига

 

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

 

Существует  также постановки, в которых задача коммивояжера становится NP-полной. Обычно такие постановки выглядят следующим образом: существует ли на заданном графе G такой обход, что его стоимость не превышает x. Часто на ней проводят обкатку новых подходов к эвристическому сокращению полного перебора.

 

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

 

Формулируется следующим образом:

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

Алгоритм  прост в реализации, быстро выполняется, но, как и другие «жадные» алгоритмы, может выдавать неоптимальные решения. Одним из эвристических критериев оценки решения является правило: если путь, пройденный на последних шагах алгоритма, сравним с путём, пройденным на начальных шагах, то можно условно считать найденный маршрут приемлемым, иначе, вероятно, существуют более оптимальные решения. Другой вариант оценки решения заключается в использовании алгоритма нижней граничной оценки (lower bound algorithm).

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

Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в  неизвестном порядке города 2,1,3..n и вернуться в первый город. Расстояния между городами известны.

Итак, города перенумерованы числами jÎТ=(1,2,3..n). Тур коммивояжера может быть описан циклической перестановкой t=(j1,j2,..,jn,j1), причём все j1..jn – разные номера; повторяющийся в начале и в конце j1, показывает, что перестановка зациклена. Расстояния между парами вершин  Сij образуют матрицу С. Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал

Во-первых, в постановке Сij означали расстояния, поэтому они должны быть неотрицательными, т.е. для всех jÎТ:

Сij³0; Cjj=∞

 (последнее равенство означает запрет на петли в туре), симметричными, т.е.  для всех i,j:

Сij= Сji.

и удовлетворять  неравенству треугольника, т.е. для  всех:

Сij+ Сjk³Cik

В математической постановке говорится о произвольной матрице. Сделано это потому, что имеется много прикладных задач, которые описываются основной моделью, но всем условиям (2)-(4) не удовлетворяют. Особенно часто нарушается условие (3) (например, если Сij – не расстояние, а плата за проезд: часто туда билет стоит одну цену, а обратно – другую). Поэтому различать вариант задачи коммивояжёра: симметричную задачу, когда условие (3) выполнено, или несимметричный - в противном случае. Условия (2)-(4) по умолчанию считаются выполненными.

Второе замечание  касается числа всех возможных туров. В несимметричной задаче коммивояжёра все туры t=(j1,j2,..,jn,j1) и t’=(j1,jn,..,j2,j1) имеют разную длину и должны учитываться оба. Разных туров очевидно (n-1)!.

На первом и последнем месте в циклической перестановке номер будет j1, а оставшиеся n-1 номеров будет (n-1)! возможными способами. В результате получим все несимметричные туры. Симметричных туров имеется в два раз меньше, т.к. каждый засчитан два раза: как t и как t’.

Можно представить, что С состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро (i,j)  проведено, если Сij=0 и не проведено, если Сij=1. Тогда, если существует тур длины 0, то он пройдёт по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом. Незамкнутый гамильтонов цикл называется гамильтоновой цепью (гамильтоновым путём). В терминах теории графов симметричную задачу коммивояжёра можно сформулировать так:

Дана  полная сеть с n  вершинами, длина ребра (i,j)= Сij. Найти гамильтонов цикл минимальной длины. В несимметричной задаче коммивояжёра вместо «цикл» надо говорить «контур», а вместо «ребра» - «дуги» или «стрелки».

Метод ближайших соседей — простейший метрический классификатор, основанный на оценивании сходства объектов. Классифицируемый объект относится к тому классу, которому принадлежат ближайшие к нему объекты обучающей выборки.

Метод ближайшего соседа является, пожалуй, самым простым алгоритмом классификации. Классифицируемый объект  относится к тому классу , которому принадлежит ближайший объект обучающей выборки .

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

Метод "ближайшего соседа" ("nearest neighbour") относится к классу методов, работа которых основывается на хранении данных в памяти для сравнения с новыми элементами. При появлении новой записи для прогнозирования находятся отклонения между этой записью и подобными наборами данных, и наиболее подобная (или ближний сосед) идентифицируется.

Например, при рассмотрении нового клиента банка, его атрибуты сравниваются со всеми существующими клиентами  данного банка (доход, возраст и  т.д.). Множество "ближайших соседей" потенциального клиента банка выбирается на основании ближайшего значения дохода, возраста и т.д.

При таком подходе используется термин "k-ближайший сосед" ("k-nearest neighbour"). Термин означает, что выбирается k "верхних" (ближайших) соседей для их рассмотрения в качестве множества "ближайших соседей". Поскольку не всегда удобно хранить все данные, иногда хранится только множество "типичных" случаев. В таком случае Прецедент - это описание ситуации в сочетании с подробным указанием действий, предпринимаемых в данной ситуации.

Подход, основанный на прецедентах, условно  можно поделить на следующие этапы:

- сбор подробной информации о поставленной задаче;

- сопоставление этой информации с деталями прецедентов, хранящихся в базе, для выявления аналогичных случаев;

- выбор прецедента, наиболее близкого к текущей проблеме, из базы прецедентов;

- адаптация выбранного решения к текущей проблеме, если это необходимо;

- проверка корректности каждого вновь полученного решения;

- занесение детальной информации о новом прецеденте в базу прецедентов.

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

Метод ближайшего соседа является, пожалуй, самым простым алгоритмом классификации. Классифицируемый объект относится к тому классу , которому принадлежит ближайший объект обучающей выборки .

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

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