Приближенные методы решения задачи коммивояжера
Приближенные методы решения позволяют решать задачу достаточно быстро, но с достаточно большой погрешностью. Одним из известных приближенных методов является «жадный алгоритм». Суть этого алгоритма в том, чтобы, находясь в определенном городе, выбирать ближайший из ранее не посещенных городов. Рассмотрим пример кода данного алгоритма на 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. Качество решений, получаемых данным алгоритмом, достаточно мало, и в некоторых случаях погрешность вычислений может стремиться к бесконечности.
Еще одним из приближенных методов является метод поиска эйлеровых циклов. Суть этого алгоритма: 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); Извлечём в эту переменную последовательность степеней вершин графа > 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): 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); > Euler; Сложность этого алгоритма 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): > readlib(randomize)(); random:=rand(1..N*N): Генерация случайной матрицы > 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); Базовый узел > bn:=1; Построение начальных туров > 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]:
Популярное: Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... Почему стероиды повышают давление?: Основных причин три... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (449)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |