Кирсанов М.Н. Графы в Maple M.: Физматлит 2007
| > | #Программа 37 c. 152 |
Алгоритм отжига
| > | restart; |
| > | with(LinearAlgebra): |
| > | n:=8: |
| > | Z:=Vector(n): |
| > | m:=rand(0..20): |
| > | for i to n do #Координаты вершин |
| > | x[i]:=m():y[i]:=m(): |
| > | od: |
| > | W:=Matrix(n,shape=symmetric): |
| > | for i to n do # Расстояния |
| > | for j from i to n do |
| > | W[i,j]:=evalf(sqrt((x[i]-x[j])^2+(y[i]-y[j])^2)); |
| > | od; |
| > | od; |
| > | for i to n do W[i,i]:=infinity:od: |
| > | m:=rand(1..n): |
| > | p:=rand(1..100): |
| > | S:={}: k:=1: |
| > | while k<n+1 do |
| > | Z[k]:=m(); |
| > | if not(Z[k] in S) then S:= S union {Z[k]};k:=k+1; fi;od: |
| > | L0:=infinity: T:=100.: |
| > | alpha:=0.99: |
| > | Z0:=Z: |
| > | k:=0: |
| > | for i to 120 do |
| > | i1:=m():i2:=m(): |
| > | Z:=Z0: |
| > | z:=Z[i1]:Z[i1]:=Z[i2]:Z[i2]:=z:#Меняем местами i1 - i2 |
| > | L1:=add(W[Z[i],Z[i+1]],i=1..n-1)+W[Z[n],Z[1]]:#Длина Z |
Если длина маршрута уменьшилась - выбираем этот маршрут
| > | if L1<L0 then L0:=L1: Z0:=Z: k:=k+1:TT[k]:=T: L[k]:=L1: |
| > | V0:=map(`*`,Z,1); |
Если больше, то в зависимости от Р, выбираем или нет
| > | else |
| > | P0:=p()/100.: #Случайное число |
| > | P:=exp(-(L1-L0)/T):#Вероятность выбора худшего решения |
| > | if P0<P then Z0:=Z:fi: |
| > | fi: |
| > | if (i mod 10) = 0 then T:=alpha*T: fi; |
| > | od: |
| > | L[k],Transpose(V0); |