2.2 Приближенные методы решения задачи коммивояжера.
Приближенные методы решения позволяют решать задачу достаточно быстро, но с достаточно большой погрешностью.
Одним из известных приближенных методов является «жадный алгоритм». Суть этого алгоритма в том, чтобы, находясь в определенном городе, выбирать ближайший из ранее не посещенных городов.
Рассмотрим пример кода данного алгоритма на Maple.
> with(combinat):
> N:=9; N1:=N-1;
> 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;
Сложность этого алгоритма O(n^3). Данное решение позволяет вычислять для количества городов порядка 10^3.
Качество решений, получаемых данным алгоритмом, достаточно мало, и в некоторых случаях погрешность вычислений может стремиться к бесконечности.
Еще одним из приближенных методов является метод поиска эйлеровых циклов. Суть этого алгоритма:
Строится каркас минимального веса(алгоримы Прима или Крускала)
Каждое ребро дублируется, и каркас превращается в эйлеров граф
В построеном графе находится эйлеров цикл
Эйлеров цикл преобразуется в гамильтонов цикл.
Рассмотрим этот алгоритм на 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);
Извлечём в эту переменную последовательность
степеней вершин графа
> eNum:=DegreeSequence(Letter);
Проверим, что в этом графе существует
эйлеров цикл.
Если получаем пустое множество, то в
графе нет вершин нечётной степени
> remove(type,convert(eNum,set),even);
Теперь eNum можно использовать по назначению
> eNum:=NumberOfEdges(Letter);
Построение цикла начнём с вершины 1
> start:=5:
Euler:=[]
Будем использовать алгоритм Флёри
> v:=start:
for num to eNum do
Nlist:=Neighbors(Letter,v):
Aset:=convert(ArticulationPoints(Letter),set):