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

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

Литература

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

Алгоритм прост в реализации, быстро выполняется, но, как и другие «жадные» алгоритмы, может выдавать неоптимальные решения. Одним из эвристических критериев оценки решения является правило: если путь, пройденный на последних шагах алгоритма, сравним с путём, пройденным на начальных шагах, то можно условно считать найденный маршрут приемлемым, иначе, вероятно, существуют более оптимальные решения. Другой вариант оценки решения заключается в использовании алгоритма нижней граничной оценки (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 и более нечётность уже не помогает, и ситуации неоднозначности всё равно могут возникать. Тогда -му соседу приписывается вес , как правило, убывающий с ростом ранга соседа . Объект относится к тому классу, который набирает больший суммарный вес среди ближайших соседей.

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

Пусть требуется провести классификацию заданного множества объектов методом ближайшего соседа. Расстояние между двумя классами определяется как расстояние между ближайшими их представителями.

Рис.1 Расстояние между двумя классами.

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

Рис.2 Матрица расстояния между объектами.

Решение:

Шаг 1. На первом шаге каждый объект представляет собой отдельный кластер: |1|, |2|, |3| и |4|. Согласно критерию классификации, объединение происходит между кластерами, расстояние между ближайших представителей которых наименьшее: кластеры |1| и |2|. Расстояние, на котором произошло объединение – 2.06. Необходимо произвести перерасчет матрицы расстояний с учетом нового кластера:

Рис.3 Шаг 1.

Шаг 2. Кластеры на данном шаге: |1,2|, |3| и |4|. Согласно новой матрицы расстояний, кластеры |3| и |4| наиболее близкие. Расстояние объединения – 2.24. Необходимо произвести перерасчет матрицы расстояний с учетом нового кластера:

Рис.4 Шаг 2.

Шаг 3. Кластеры на данном шаге: |1,2| и |3,4|. Расстояние между кластерами равно 2.50 – это расстояние между 2 и 3 объектом. Образование кластеров закончено. Результат классификации методом ближайшего соседа представлен в виде дендрограммы:

Рис.5 Шаг 3.

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