Кирсанов М.Н. Графы в Maple M.: Физматлит 2007
| > | #Программа 36 c.148 |
Муравьиный алгоритм
| > | restart; |
| > | with(LinearAlgebra):with(plots): |
| > | n:=7: Q:=5*n: Lmin:=1000: |
| > | a:=9: b:=5: p:=0.7:# |
| > | DWt:=Matrix(n): |
| > | Wt:= Matrix(1..n,1..n,0.1):#След |
| > | 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: |
Процедура выбора наиболее вероятного направления
| > | P:=proc(x) |
| > | local n,sm,i,Beg,End,c,s,m,j; |
| > | n:=nops(x): |
| > | sm:=0: for i to n do sm:=sm+x[i]: od: |
| > | c:=0: |
| > | for i to n do |
| > | Beg[i]:=c: End[i]:=c+x[i]/sm; c:=End[i]: |
| > | od: |
| > | m:=rand(0..100): |
| > | s:=m()/101: |
| > | for i to n do |
| > | if (Beg[i]<=s) and (End[i]>=s) |
| > | then j:=i: fi: |
| > | od: |
| > | return j; |
| > | end proc: |
| > |
| > | for k0 to 100 do# Основной цикл |
| > | for ant to n do# Цикл по муравьям |
| > | s:={$1..n}: # Список непосещенных вершин |
| > | j:=ant: # начальная вершина для муравья ant |
| > | for j1 to n-1 do |
| > | s:=s minus {j};# Tabu list увеличился |
| > | sp:=[]:k1:=0: |
| > | for i in s do # Каждой вершине - свой вес |
| > | sp:=[op(sp),1/W[j,i]^b*Wt[j,i]^a]: k1:=k1+1: nn[k1]:=i; |
| > | od: |
| > | j0:=nn[P(sp)];#Выбор направления |
| > | v[j1]:=j0; |
| > | r[j1]:=W[j,j0]; |
| > | j:=j0:# Начало следующей дуги - конец предыдущей |
| > | od:#Цикл j1 по всем вершинам для ant муравья |
| > | L:=add(r[i],i=1..n-1)+W[op(s),ant];#Добавляем последнюю дугу |
| > | v[0]:=ant; v[n]:=ant; #Начало и конец пути |
| > | v1:=seq([v[m],v[m+1]],m=0..n-1): #Дуги |
| > | for i to n do #Пометка дуг феромоном |
| > | DWt[op(v1[i])]:=DWt[op(v1[i])]+Q/L; |
| > | od: |
| > | if L<Lmin then Lmin:=L:fi:# Выбор min |
| > | od:#ant |
| > | Wt:=Wt+DWt*p:# Добавление новых следов |
| > | Wt:=Wt*(1-p):# Испарение феромона |
| > | od:# k0 |
| > | Lmin; |
| > | z:=i ->[x[i],y[i]]: |
| > | ris:=seq(seq(PLOT(CURVES([z(i),z(j)]), THICKNESS(round((Wt[i,j]+Wt[j,i])/15))),i=1..n),j=1..n): |
| > | Ver:=PLOT(seq(TEXT(map(`+`,z(i),0.5),convert(i,symbol)),i=1..n),FONT(TIMES,BOLD,14)): |
| > | display(ris,Ver); |
![[Maple Plot]](images/p362.gif)
| > |