Диссертация (1149246), страница 14

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

ПРОГРАММНАЯ РЕАЛИЗАЦИЯАЛГОРИТМА ALLIS> restart;> AllIS:=proc(A,n)local Dekart2,Delta_S,Constr_P,i,j,kolvo_uzlov,r,k,J,Q,ind,MG;local Z_Delta,F,continue,nDelta,nS,removeQ,maximum,l,temp;local temp1,temp2,nTemp,alpha,alpha1,alpha2,R,t,a,a1,a2;local vsm,nD,kolD,PP,nP,exist,JtminusJ,nJt,omega,FF,kol;local real_kol,short_JtminusJ;> Dekart2:=proc(a,b) #строит декартово произведение множествlocal j,i,n,m,Dek;Dek:={};n:=nops(a);m:=nops(b);for i from 1 to n dofor j from 1 to m doDek:={op(Dek),{a[i],b[j]}};end do;end do;return(Dek);end proc:> Delta_S:=proc(S,omega) #строим множество Deltalocal Delta, i,j,m,r,p;Delta:={};m:=nops(omega);r:=nops(S);136if r=0 then Delta:=omega;elsefor i from 1 to m dop:=0;for j from 1 to r doif omega[i]=S[j][1] or omega[i]=S[j][2] thenp:=1;end if;end do;if p=0 then Delta:={op(Delta),omega[i]}; end if;end do;end if;return(Delta);end proc:> Constr_P:=proc(a,b,M)#формируем окрестность Plocal kol,i,P;P:={};kol:=nops(M):for i from 1 to kol doif member(a,M[i]) and member(b,M[i])thenP:=P union {M[i]};end if;end do;return P;end proc:#************************************************#Вспомогательные построения алгоритма:#************************************************137omega||0:={}:for i from 1 to n doomega||0:={op(omega||0),i}:end do:for i from 1 to n doh||i:={}:for j from 1 to n doif A[i,j]=0 thenh||i:={op(h||i),j};end if:end do:end do:S||0:={}:kolvo_uzlov:=0:for i from 1 to n-1 dofor j from i+1 to n doa||i||j:=h||i intersect h||j;if member(i,a||i||j) and member(j,a||i||j)D||0||i||j:=a||i||j;S||0:={op(S||0),{i,j}};kolvo_uzlov:=kolvo_uzlov+1:elseD||0||i||j:=a||i||j minus a||i||j;end if;:end do:end do:r:=kolvo_uzlov:Delta||0:=Delta_S(S||0,omega||0):G||0:=S||0:then138#************************************************#Основная схема алгоритма:#************************************************k:=0; J:={}; Q:=[]; ind:=0; real_kol:=0; MG:={}; Z_Delta:={};P||0:=MG; F:=S||0;continue:=true;while continue=true doDelta||k:=Delta||k minus Z_Delta;nDelta:=nops(Delta||k);if nDelta<>0 thenfor i from 1 to nDelta doJ||i:=J union {Delta||k[i]};MG:=MG union {J||i};real_kol:=real_kol+1;for j from 0 to k-1 doP||j:=P||j union {J||i};end do;end do;Delta||k:={};end if;nS:=nops(S||k);if nS=0 thenif k=0 thencontinue:=false;elseremoveQ:={Q[ind][1],Q[ind][2]};J:=J minus removeQ;Q:=remove(type,Q,Q[ind]);ind:=ind-1;139k:=k-1;end if;elsemaximum:=0; #выбираем узел по мощностимножества Dfor l from 1 to nS dotemp:=S||k[l];temp1:=temp[1]; temp2:=temp[2];nTemp:=nops(D||k||temp1||temp2);if nTemp>maximum then maximum:=nTemp; alpha:=temp; end if;end do:alpha1:=alpha[1]; alpha2:=alpha[2];#формируем множество непереспективных элементовR:={}:S||k:=S||k minus {alpha};t:=nops(S||k);for i from 1 to t doa:=S||(k)[i];a1:=a[1]; a2:=a[2];if member(alpha1,D||k||a1||a2) and member(alpha2,D||k||a1||a2)thenvsm:=D||k||a1||a2;nD:=nops(vsm);kolD:=0;for l from 1 to nD doif member(vsm[l],D||k||alpha1||alpha2) thenkolD:=kolD+1;end if;end do;if kolD=nD then140R:=R union {{a1,a2}};end if;end if:end do:S||k:=S||k union {alpha};#процесс построения окрестностей:Z_Delta:={};P||(k+1):=Constr_P(alpha1,alpha2,P||(k));PP:=P||(k+1);nP:=nops(PP);exist:=0;#проверяем, существует ли МНМ, которое совпадает#с базовым множеством этого уровняfor l from 1 to nP doJtminusJ:=PP[l] minus J;short_JtminusJ:=JtminusJ minus {alpha1,alpha2};nJt:=nops(short_JtminusJ);if nJt=1 then Z_Delta:=Z_Delta union short_JtminusJ;if nops(D||k||alpha1||alpha2)=3 then exist:=1; end if;elseif D||k||alpha1||alpha2=JtminusJ then exist:=1; end if;end if;end do;if exist=1 thenS||k:=S||k minus {alpha}; S||k:=S||k minus R; k:=k;elseJ:=J union {alpha1,alpha2};Q:=[op(Q),[alpha1,alpha2]];ind:=ind+1;141omega:=D||k||alpha1||alpha2 minus {alpha1,alpha2};if nops(omega)=0 thenS||(k+1):={}; Delta||(k+1):={};MG:=MG union {J}; real_kol:=real_kol+1;# пополнение окрестноcтейfor j from 0 to k-1 doP||j:=P||j union {J};end do;elseS||(k+1):=S||k intersect Dekart2(omega,omega);FF:=F intersect Dekart2(omega,omega);Delta||(k+1):=Delta_S(FF,omega);r:=nops(S||(k+1));for i from 1 to r doa:=S||(k+1)[i];a1:=a[1]; a2:=a[2];D||(k+1)||a1||a2:=D||k||a1||a2 intersect omega;end do;end if;S||k:=S||k minus {alpha};S||k:=S||k minus R;k:=k+1;end if;end if;end do;kol:=nops(MG);return MG,kol,real_kol;end proc:142ПРИЛОЖЕНИЕ 6.

ПРОГРАММНАЯ РЕАЛИЗАЦИЯАЛГОРИТМА MAXIS> restart;> MaxIS:=proc(A,n) #A - матрица смежности графа, n - его размерностьlocal Dekart2,Delta_S,Constr_P,i,j,kolvo_uzlov,r,k,J,Q,ind,MG;local Z_Delta,F,continue,nDelta,nS,removeQ,maximum,l,temp;local temp1,temp2,nTemp,alpha,alpha1,alpha2,R,t,a,a1,a2;local vsm,nD,kolD,PP,nP,exist,JtminusJ,nJt,omega,FF,kol;local real_kol,short_JtminusJ,nOmega,Jmax,nJm,nDk,Find_vertex;local vertex,Find_Tw_E,TwE,nV,Ew;> Dekart2:=proc(a,b) #декартовопроизведение множествlocal j,i,n,m,Dek;Dek:={};n:=nops(a);m:=nops(b);for i from 1 to n dofor j from 1 to m doDek:={op(Dek),{a[i],b[j]}};end do;end do;return(Dek);end proc:#функция для нахождения одного ребра в опорном множестве> Find_vertex:=proc(w)local nw,find,i,j,v1,v2,vertex:nw:=nops(w):find:=0:for i from 1 to nw-1 do143v1:=w[i]:for j from i+1 to nw dov2:=w[j];if A[v1,v2]=1 then vertex:=v1; find:=1: break; end if;end do:if find=1 then break; end if:end do:return vertex:end proc:#функция для нахождения ребер E в опорном множестве#и повторяющейся вершины Tw> Find_Tw_E:=proc(w)local nw,find,i,j,v1,v2,Vertex,Tw,E:nw:=nops(w):E:={}:Vertex:={}:find:=0:for i from 1 to nw-1 dov1:=w[i]:for j from i+1 to nw dov2:=w[j];if A[v1,v2]=1 thenfind:=find+1:E:={op(E),[v1,v2]};if member(v1,Vertex) then Tw:=v1:else Vertex:={op(Vertex),v1}:end if:if member(v2,Vertex) then Tw:=v2:else Vertex:={op(Vertex),v2}:144end if:end if;#for if A[v1,v2]=1if find=2 then break: end if:end do:if find=2 then break; end if:end do:return Vertex,Tw,E:end proc:#************************************************#Вспомогательные построения алгоритма:#************************************************omega||0:={}:for i from 1 to n doomega||0:={op(omega||0),i}:end do:nOmega:=0;for i from 1 to n doh||i:={}:for j from 1 to n doif A[i,j]=0 thenh||i:={op(h||i),j};end if:end do:end do:S||0:={}:kolvo_uzlov:=0:for i from 1 to n-1 dofor j from i+1 to n doa||i||j:=h||i intersect h||j;145if member(i,a||i||j) and member(j,a||i||j)then D||0||i||j:=a||i||j;S||0:={op(S||0),{i,j}};kolvo_uzlov:=kolvo_uzlov+1:else D||0||i||j:={};end if;:end do:end do:r:=kolvo_uzlov:G||0:=S||0:#************************************************#Основная схема алгоритма:#************************************************k:=0; J:={}; Q:=[]; Jmax:={}; nJm:=0; ind:=0; F:=S||0;continue:=true;while continue=true donS:=nops(S||k);if nS=0 thenif (nops(omega||k)<>0 and 2*k+1>nJm) thenJmax:=J union {omega||k[1]};nJm:= nops(Jmax): omega||k:={}:end if:if k=0 then continue:=false;elseremoveQ:={Q[ind][1],Q[ind][2]} union d||(k);J:=J minus removeQ;Q:=remove(type,Q,Q[ind]);ind:=ind-1;k:=k-1;146end if;elsemaximum:=0;for l from 1 to nS dotemp:=S||k[l];temp1:=temp[1]; temp2:=temp[2];nTemp:=nops(D||k||temp1||temp2);if nTemp>maximum then maximum:=nTemp; alpha:=temp; end if;end do:alpha1:=alpha[1]; alpha2:=alpha[2];d||(k+1):={}: #добавочка, которую нужно будет удалить из Q#при возвращении на предыдущий уровеньnDk:=maximum:if nDk+2*k>nJm thenR:={}:S||k:=S||k minus {alpha};t:=nops(S||k);for i from 1 to t doa:=S||(k)[i];a1:=a[1]; a2:=a[2];if member(alpha1,D||k||a1||a2) and member(alpha2,D||k||a1||a2)then vsm:=D||k||a1||a2;nD:=nops(vsm);kolD:=0;for l from 1 to nD doif member(vsm[l],D||k||alpha1||alpha2)then kolD:=kolD+1;end if;end do;147if kolD=nD thenR:=R union {{a1,a2}}; end if;end if:end do:S||k:=S||k union {alpha};J:=J union {alpha1,alpha2};Q:=[op(Q),[alpha1,alpha2]];ind:=ind+1;omega||(k+1):=D||k||alpha1||alpha2 minus {alpha1,alpha2};nOmega:=nops(omega||(k+1));if nOmega=0 thenS||(k+1):={}; Jmax:=J: nJm:=nops(Jmax):elif nOmega=1 thenS||(k+1):={}; Jmax:=J union omega||(k+1): nJm:=nops(Jmax):elif nOmega>1 thenS||(k+1):=S||k intersect Dekart2(omega||(k+1),omega||(k+1));r:=nops(S||(k+1));for i from 1 to r doa:=S||(k+1)[i];a1:=a[1]; a2:=a[2];D||(k+1)||a1||a2:=D||k||a1||a2 intersect omega||(k+1);end do;############## МОДИФИКАЦИИ: НАЧАЛО ##################if (r<>0 and r=nOmega*(nOmega-1)/2)then #print(’ПЕРВОЕ_УСЛОВИЕ_ВЫПОЛНЕНО’);d||(k+1):=omega||(k+1): #добавочка, которую нужно будет удалить#из Q при возвращении на предыдущий уровеньJ:=J union d||(k+1):Jmax:=J; nJm:=nops(Jmax):148S||(k+1):={};omega||(k+1):={};elif (r<>0 and r=nOmega*(nOmega-1)/2-1)then #print(’ВТОРОЕ_УСЛОВИЕ_ВЫПОЛНЕНО’);if nDk+2*k-1>nJm thenvertex:=Find_vertex(omega||(k+1)):d||(k+1):=omega||(k+1) minus {vertex}:J:=J union d||(k+1):Jmax:=J; nJm:=nops(Jmax):end if:S||(k+1):={}: omega||(k+1):={}:elif (r<>0 and r=nOmega*(nOmega-1)/2-2)then #print(’ТРЕТЬЕ_УСЛОВИЕ_ВЫПОЛНЕНО’);if nDk+2*k-1>nJm thenTwE:=Find_Tw_E(omega||(k+1)):nV:=nops(TwE[1]):if nV=3 thend||(k+1):=omega||(k+1) minus {TwE[2]}:J:=J union d||(k+1):Jmax:=J; nJm:=nops(Jmax):elif nV=4 thenif nDk+2*k-2>nJm thenEw:=TwE[3]:d||(k+1):=omega||(k+1) minus {Ew[1][1],Ew[2][1]}:J:=J union d||(k+1):Jmax:=J; nJm:=nops(Jmax):end if:end if:#for if nV=3end if:#for if nDk+2*k-1>nQm149S||(k+1):={}: omega||(k+1):={}:end if: #for if (nSk<>0 and nSk=nOmega*(nOmega-1)/2)############# МОДИФИКАЦИИ: КОНЕЦ ##############end if; #for if nOmega=0;S||k:=S||k minus {alpha};S||k:=S||k minus R;k:=k+1;else #for nDk+2*k<=nJmS||k:={};end if; #for nDk+2*k>nJmend if; #for if nS=0end do; #for whilereturn Jmax:end proc:.

Характеристики

Список файлов диссертации