Приближенные методы решения задачи коммивояжера

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

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

Рассмотрим пример кода данного алгоритма на Maple.

> with(combinat):

> N:=9; N1:=N-1;

Приближенные методы решения задачи коммивояжера - student2.ru

Приближенные методы решения задачи коммивояжера - student2.ru

> PermList:=permute(N1):

> readlib(randomize)();

> random:=rand(1..N*N):

> GTS:=proc(N::posint,start::posint,cost::matrix)

local TourCost, MinCost, MinIndex, index, current;

global Tour;

current:=start;

Tour:= [current]:

TourCost:=0:

while nops(Tour) < N do

MinCost:=infinity:

For index from 1 to N do

if not member(index, Tour) and (cost[current, index] < MinCost)

then MinCost := cost[current, index]:MinIndex:=index

fi

od;

Tour:=[op(Tour), MinIndex]:

TourCost:=TourCost+MinCost:

current:=MinIndex

od;

TourCost:=TourCost+cost[MinIndex,start]

end:

> NearIns:=proc(N::posint, start::posint,cost::matrix)

Local

TourCost, MinCost, MinIndex, index, current, InsPoint, before, after;

global Tour;

MinCost:=infinity:

For index from 1 to N do

if(index<>start) and(cost[index, start] < MinCost)

Then

MinCost:=cost[index,start]:

MinIndex:=index

fi

od:

Tour:=[start, MinIndex, start];

TourCost:=2*MinCost:

while nops(Tour) <= N do

MinCost:=infinity:

For index from 1 to nops(Tour) - 1 do

For current from 1 to N do

if not member(current, Tour) and (cost[current, Tour[index]] < MinCost)

Then

InsPoint:=index:

MinCost:=cost[current, Tour[index]]:

MinIndex:=current

fi

od

od:

after:=cost[Tour[InsPoint+1], MinIndex]-cost[Tour[InsPoint+1],Tour[InsPoint]]:

if InsPoint=1

then InsPoint:=nops(Tour)

fi:

before:=cost[Tour[InsPoint-1], MinIndex] - cost[Tour[InsPoint-1], Tour[InsPoint]]:

if before < after

then InsPoint:=InsPoint-1

Else

if InsPoint=nops(Tour)

then InsPoint :=1

fi

fi:

TourCost:=TourCost+MinCost+min(before, after):

Tour:=[op(1..InsPoint, Tour), MinIndex,op(InsPoint+1..nops(Tour),Tour)]

od:

TourCost

end:

> while true do

> CostMatrix:=matrix(N,N):

> for r from 1 to N do CostMatrix[r,r]:=infinity; od:

For r from 1 to N do

For c from 1 to r - 1 do

CostMatrix[r,c]:=random():

CostMatrix[c,r]:=CostMatrix[r,c]

od

od:

> evalm(CostMatrix);

> MinCost:=infinity:

> for r from 1 to nops(PermList) do

TourPermut:=PermList[r];

TourCost:=CostMatrix[TourPermut[N1],N] + CostMatrix[N, TourPermut[1]]:

For c from 1 to N-2 do

TourCost:=TourCost + CostMatrix[TourPermut[c],TourPermut[c+1]]

od:

if TourCost<=MinCost

then MinCost:=TourCost:

lprint(`Tour->`,[op(TourPermut), N], `Cost=`, MinCost)

fi

od:

> MinGTScost:=infinity:

For r from 1 to N do

GTScost:=GTS(N, r, CostMatrix):

if GTScost<MinGTScost

Then

MinGTScost:=GTScost:

GTStour:=copy(Tour):

print(`Start node->`, r, MinGTScost):

fi

od;

> if MinGTScost>MinCost

Then

lprint(`Minimal GTS cost->`,MinGTScost, `Optimal solution->`, MinCost):

Break

fi;

> od;

Приближенные методы решения задачи коммивояжера - student2.ru

Приближенные методы решения задачи коммивояжера - student2.ru Приближенные методы решения задачи коммивояжера - student2.ru Приближенные методы решения задачи коммивояжера - student2.ru

Сложность этого алгоритма O(n^3).Данное решение позволяет вычислять для количества городов порядка 10^3.

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

Еще одним из приближенных методов является метод поиска эйлеровых циклов. Суть этого алгоритма:

v Строится каркас минимального веса(алгоримы Прима или Крускала)

v Каждое ребро дублируется, и каркас превращается в эйлеров граф

v В построеном графе находится эйлеров цикл

v Эйлеров цикл преобразуется в гамильтонов цикл.

Рассмотрим этот алгоритм на Maple.

> with(GraphTheory):

> Letter:=Graph([$1..6],{{1,2},{1,6},{2,6},{2,5},{3,5},

{2,3},{5,6},{5,4},{3,4},{3,6}}):

Так рисуется граф по умолчанию

> DrawGraph(Letter,style=circle);

Приближенные методы решения задачи коммивояжера - student2.ru

Извлечём в эту переменную последовательность

степеней вершин графа

> eNum:=DegreeSequence(Letter);

Приближенные методы решения задачи коммивояжера - student2.ru

Проверим, что в этом графе существует

эйлеров цикл.

Если получаем пустое множество, то в

графе нет вершин нечётной степени

> remove(type,convert(eNum,set),even);

Приближенные методы решения задачи коммивояжера - student2.ru

Теперь eNum можно использовать по назначению

> eNum:=NumberOfEdges(Letter);

Приближенные методы решения задачи коммивояжера - student2.ru

Построение цикла начнём с вершины 1

> start:=5:

Euler:=[]

Будем использовать алгоритм Флёри

> v:=start:

For num to eNum do

Nlist:=Neighbors(Letter,v):

Aset:=convert(ArticulationPoints(Letter),set):

If member(v,Aset)

Then

Aset:=convert(Nlist,set) minus Aset minus {start}:

if Aset={}

then newv:=Nlist[1]

else newv:=Aset[1]

fi

else newv:=Nlist[1]

fi:

Euler:=[op(Euler),[v,newv]]:

DeleteEdge(Letter,{v,newv}):

v:=newv:

od:

> eLetter:=Graph([$1..6],convert(Euler,set)):

> DrawGraph(eLetter);

Приближенные методы решения задачи коммивояжера - student2.ru

> Euler;

Приближенные методы решения задачи коммивояжера - student2.ru

Сложность этого алгоритма O(n*log(n)). Он позволяет вычислять маршрут для количества городов порядка 10^7.

Еще одной эвристикой является Saving Heuristic.

Алгоритм этой эвристики:

v Шаг первый: экономные вычисления

Ø Вычисляем сбережения si j=ci 0 + c0 j - ci j ,для i, j = 1..n, i≠j

Ø Создать nмаршрутов (0,i,0), I = 1..n

Ø Отсортировать полученные сбережения в невозрастающем порядке

v Шаг второй: Наилучшее возможное слияние Начиная с верхней части списка, выполняем следующее:

Ø Учитывая сбережения si j ,определить существуют ли два пути, которые могут быть объединены.

ü Начиная с (0, i)

ü Заканчивая (j, 0)

Ø Объединяя эти два пути, удалив (0, i)и (j, 0),вводим(I,j)

Рассмотрим код этого алгоритма на Maple.

> with(plots):

with(plottools):

> with(combinat):

Number of towns

> N:=8;N1:=N-1:

> PermList:=permute(N1):

Приближенные методы решения задачи коммивояжера - student2.ru

> readlib(randomize)();

random:=rand(1..N*N):

Приближенные методы решения задачи коммивояжера - student2.ru

Генерация случайной матрицы

> CostMatrix:=matrix(N,N):

For r from 1 to N do

CostMatrix[r,r]:=infinity

od:

> for r from 2 to N do

For c from 1 to r-1 do

CostMatrix[r,c]:=random():

CostMatrix[c,r]:=CostMatrix[r,c]

od

od;

> evalm(CostMatrix);

Приближенные методы решения задачи коммивояжера - student2.ru

Базовый узел

> bn:=1;

Приближенные методы решения задачи коммивояжера - student2.ru

Построение начальных туров

> Tours:=[]:

For r from 1 to N do

if r=bn

Then next

else Tours:=[op(Tours),[bn,r,bn]]

fi

od;

Сама процедура savings

> while nops(Tours)>1 do

MaxSaving:=[[0,0],[0,0],-infinity]:

Наши рекомендации