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

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

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

Рис.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.

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

Пример решения задачи средствами MS Excel.

Дана  матрица состоящая из цифр.

 

Рис.6 шаг первый решения задачи(Пример)

Шаг первый.

Находим ближайший город к первому.

 

Рис.7 шаг первый решения задачи(Пример)

Шаг второй.

 

Удаляем город №5 (столбец), так как в  нём мы уже были  и переходим  на

 

строчку №5 и находим минимум.

 

 

Рис.8 шаг второй решения задачи(Пример)

Шаг третий.

 

Переходим на четвертую строчку, так как на предыдущем шаге в пятой

 

  строке, минимум находится в четвертом  столбце и вычеркиваем 

 

четвертый столбец, чтобы не было цикла.

 

Рис.9 шаг четвертый задачи(Пример)

 

Ответ: Последовательность посещения: 1-5-2-4-6-1

Длина пути: 30

Скриншот:

 

Uses CRT; 
Label Out; 
Const 
N=8; 
Var 
C: array [1..N,1..N] of word; {Матрица расстояний} 
Tour, P: array [1..N] of word; {Оптимальный и текущие туры} 
l, s: word; 
i, j, k, min, ind: byte; 
All: boolean; {Признак окончания перебора} 
Graph: text; 
Begin 
ClrScr; 
{Ввод данных} 
Assign(Graph,'D:\matr.in'); 
Reset(Graph); 
TextColor(14); 
WriteLn('=========================ЗАДАЧА КОММИВОЯЖЕРА (Перебор)========================='); 
WriteLn('Матрица смежности:'); 
WriteLn('========================================= ======================================'); 
For i:=1 To N Do For j:=1 To N Do Read(Graph, C[i,j]); 
For i:=1 To N Do 
Begin 
For j:=1 To N Do Write(C[i,j],' '); 
WriteLn; 
End; 
{Инициализация} 
All:=False; {Перебраны не все варианты} 
l:=MaxInt; {Оптимальный тур неизвестен} 
For i:=1 To N Do P[i]:=i; {Строим первый тур} 
Repeat 
{Вычисляем его длину} 
s:=0; 
For i:=1 To N-1 Do s:=s+C[P[i],P[i+1]]; 
s:=s+C[P[n],P[1]]; 
{Полагаем первый тур текущим} 
If l>s Then 
Begin 
Tour:=P; 
l:=s; 
End; 
{Генерируем все (N-1)! перестановок} 
For i:=N DownTo 3 do 
Begin 
If P[i]<P[i-1] Then continue; 
min:=N+1; 
k:=P[i-1]; 
{Ищем миним. число из тех, что больше k и правее} 
For j:=i To N Do If (P[j]>k) and (P[j]<min) Then 
Begin 
min:=P[j]; 
ind:=j; 
End; 
{Рокировка min и k} 
P[i-1]:=min; 
P[ind]:=k; 
{Элементы на местах от i до N упорядочиваем по возрастанию} 
For j:=i To N-1 Do 
Begin 
min:=N+1; 
For k:=j To N Do If min > P[k] Then 
Begin 
min:=P[k]; 
ind:=k; 
End; 
k:=P[j]; 
P[j]:=min; 
P[ind]:=k; 
End; 
GoTo out; 
End; 
{Проверяем перебраны ли все перестановки} 
All:=true; 
Out: 
Until All; 
{Если перебраны все перестановки, то выдаем оптимальный тур} 
WriteLn('========================================= ======================================'); 
Write('Минимальный тур: '); 
For i:=1 To N Do Write(Tour[i],'-'); 
Write('1'); 
WriteLn(' имеет длину ',l); 
WriteLn('========================================= ======================================'); 
Close(Graph); 
ReadKey; 
END.

 

 

 

 

 

 

 

 

Алгоритм: