11. Metode de elaborare a algoritmilorper/Fp -_-/Fp_13.pdfproblema are soluţie, chiar dacăspaţiul...

11/35/35

11.11. MetodeMetode de de elaborareelaborare a a algoritmiloralgoritmilor

C_C_1133 / 11.01.20/ 11.01.201133

1.1. MetodaMetoda GreedyGreedy

2.2. MetodaMetoda Divide et Divide et ImperaImpera

3.3. MetodaMetoda Back TrackingBack Tracking

4.4. MetodaMetoda ProgramăriiProgramării DinamiceDinamice

5.5. MetodaMetoda Branch and Bound Branch and Bound -- doardoar teoreticteoretic!!

6.6. MetodeMetode EuristiceEuristice

7.7. AlgoritmiAlgoritmi GeneticiGenetici -- nu se nu se cercer!!

22/35/35

11.5.11.5. MetodaMetoda Branch_and_BoundBranch_and_Bound (nu se (nu se cerecere la la probaproba practicapractica))

Metoda Branch_and_Bound (ramifică şi mărgineşte) se aseamănă cu metodaBack_Tracking, însă diferă în primul rând prin ordinea de parcurgere a spaţiuluisoluţiilor posibile (a spaţiului stărilor).

Am văzut că la metoda Back_Tracking mulţimile ce compun spaţiul stărilorposibile trebuie să fie finite şi de asemenea componentele vectorului X căutat iauvalori fără nici o prioritate (preferinţă).

La metoda Branch_and_Bound, spaţiul stărilor este parcurs într-un mod maiinteligent, algoritmul fiind capabil să simtă soluţia, să se îndrepte spre aceasta, şi înplus metoda Branch_and_Bound nu poate conduce la un ciclu infinit, dacăproblema are soluţie, chiar dacă spaţiul stărilor este infinit.

În continuare vom încerca să descriem această metodă, apoi algoritmul general de rezolvare a unei probleme prin aceasta.

33/35/35

MetodaMetoda Branch_and_BoundBranch_and_Bound

Fie S={s1,s2,...,sn} o mulţime de stări posibile, care conţine o stare iniţială sp

cunoscută (precizată) şi o stare finală sf cunoscută (dată) sau care poate firecunoscută (admisă ca stare finală) după anumite cerinţe (condiţii sau caracteristiciprecizate în problemă). Pot exista mai multe stări finale FS.

Dintr-o stare si se poate trece (ramifica) în mai multe stări si1,si2,...sij, printr-otransformare (dată de problema concretă pe care o avem de rezolvat) de forma :

T : S P(S) , T(si)={si1,si2,...sij}, pentru i=1,2,…,n.

Se cere să determinăm o succesiune de stări începând cu starea iniţială sp pânăla starea finală sf aplicând succesiv transformarea T. Aceasta înseamnă că va trebuisă determinăm şirul stărilor de forma sk1,sk2,...skm, pentru care:

sk1=sp, sk2=T(sk1), … , ski=T(ski-1), … , skm=T(skm-1)=sf F .

Pentru că în general putem avea mai multe soluţii (chiar o infinitate), se poatecere să determinăm cea mai scurtă secvenţă rezultat, adică cea pentru care m esteminim.

44/35/35


Pentru a ajunge la starea finală vom utiliza o mulţime de stări active (posibilepentru continuare spre starea finală) din care vom alege acea stare care este cât maiaproape de starea iniţială şi de starea finală (distanţa de la starea iniţială + distanţapână la starea finală este minimă).

Distanţa faţă de starea iniţială se poate uşor măsura (determina) fiind numărulde transformări aplicate stării iniţiale pentru a obţine acea stare:

d1 : S N , d1(s) = k dacă s Tk(sp).

Distanţa de la o stare si la starea finală sf, în general este greu de calculat, de cele mai multe ori nu se poate determina doar după ce am rezolvat problema însine. Din această cauză va trebui să căutăm o aproximantă a acesteia, care poate fiuşor calculată pentru problema concretă dată. Această distanţă va fi de forma :

d2 : S R+ , iar d2(sf)=0.

Criteriul de alegere din mulţimea stărilorstărilor activeactive constă în determinarea aceleistări care realizează minimul sumei distanţelor d1 şi d2. Aceasta înseamnă că dacăla un moment dat, mulţimea stărilor active este Sa={sa1,...,sal}, atunci se alege stareasaj, pentru care :

d1(saj)+d2(saj) = minmin { d1(sai)+d2(sai) / sai Sa } .

55/35/35


Strategia Branch_and_Bound este următoarea : iniţial Sa={sp}, iar pentru o mulţime de stări active obţinută la un moment dat se alege o stare curentă sc (o stare de continuare, aşa cum am arătat mai sus) iar în locul ei se depune înmulţimea stărilor active acele stări care se ramifică din ea ( Sa:=Sa \ {sc} T(sc) ).

Dacă printr-o astfel de transformare (ramificare) am ajuns la o stare finală sfFproblema este rezolvată.

Pentru ca într-o problemă să putem aplica metoda Branch_and_Bound, vatrebui să ne asigurăm că problema are soluţie, altfel strategia prezentată poateconduce la un ciclu infinit.

Cele două distanţe (d1 şi d2) nu ne vor permite să ne îndepărtăm prea mult de starea iniţială (d1) şi de asemenea dacă d2 este mărginită ( kkN : d2(s) kk, sS), atunci metoda nu admite o abatere de la calea corectă (spre soluţie) decât cu celmult kk paşi (mărginirea posibilităţilor).

Pentru a putea reconstitui drumul parcurs de la starea iniţială la starea finalăvom reţine pentru fiecare stare care rezultată dintr-o ramificaţie starea care se transformă. Dacă T(s)={s1,s2,...,st}, atunci Pred(si):=s, pentru fiecare i=1,2,…,t saumai simplu, ceeea ce este suficient pentru a reconstitui calea inversă.

66/35/35


AlgoritmulAlgoritmul generalgeneral de tip Branch_and_Bound este următorul:AlgoritmulAlgoritmul Branch_and_BoundBranch_and_Bound Este :Este :

Date Date sp,Fsp,F; ; { { CiteCiteşştete stareastarea iniiniţţialăială şşii starilestarile finale }finale }Sa:={sp};Sa:={sp}; { { stareastarea iniiniţţialăială sp sp esteeste prima stare prima stare activăactivă }}RepetăRepetă

sc:=sc:=Aleg(SaAleg(Sa); ); { { stareastarea curentăcurentă realizeazărealizează min dmin d11+d+d22 }}DacăDacă sc sc F F AtunciAtunci { { stareastarea curentăcurentă esteeste stare stare finalăfinală?}?}Sa:=SaSa:=Sa\\{sc}; {sc}; { { stareastarea eleasăeleasă deviedevie pasivăpasivă }}St:=St:=T(scT(sc); ); { { ramificăramifică stareastarea curentăcurentă ((cautăcaută noinoi stăristări) }) }PentruPentru ssStSt ExecutăExecută s.Preds.Pred:=sc ; { :=sc ; { rereţţineine caleacalea de de îîntoarcerentoarcere }}Sa:=Sa Sa:=Sa StSt

PânăPână_Când_Când Sa=Sa= sausau scscFF; ; { Nu { Nu existăexistă solusoluţţieie sausau am am găsitgăsit o stare o stare finalăfinală } } DacăDacă scscFF AtunciAtunci

sksk:=sc; :=sc; TipăreTipăreşştete sksk; ; { { parcurgeparcurge caleacalea inversăinversă }}

RepetăRepetă sksk:=:=Pred(skPred(sk); ); TipăreTipăreşştete sksk {de la {de la stareastarea fianlăfianlă la la stareastarea iniiniţţialăială}}

PânăPână_Când_Când sksk=sp=spAltfelAltfel TipăreTipăreşştete ""ProblemaProblema nu are nu are solusoluţţieie""

Sf_AlgoritmSf_Algoritm..

77/35/35


Pentru rezolvarea unei probleme de tip Branch_and_Bound, vom utiliza o listăînlănţuită ordonată crescător după suma distanţelor d1 şi d2 care va conţine toatetoate stările generate (plecând de la starea iniţială), atât cele active (care urmeazăsă fie alese) cât şi cele pasive (care au fost deja alese, păstrate pentru a darezultatul), diferenţierea acestora fâcându-se prin câmpul numit Tip {Activă, Pasivă}. În acest mod, alegerea se va efectua simplu, deoarece starea aleasă va fiprima stare activă din listă. Adăugarea în listă se va efectua în aşa fel încât lista sărămână ordonată. Elementele listei vor conţine pe lângă câmpul ce caracterizeazăo stare sS (configuraţia) şi cheia de ordonare egală cu d1(s)+d2(s). De asemenea, pentru a determina cât mai rapid distanţa d1 a unei stări faţă de starea iniţială, se vareţine şi această distanţă pentru fiecare stare (element al listei), decid1(s):=d1(Sc)+1. Pentru a putea reconstitui calea parcursă de la starea iniţială pânăla starea finală, vom reţine şi adresa stării din care s-a produs transformarea stăriicurente (Pred). Elementele listei înlânţuite (prin Leg) vor avea structura următoare:

Dacă o stare activă este aleasă ca stare curentă, ea devine pasivă pentru a nu vamai fi aleasă. Mai precizăm că este de preferat ca o stare nouă să nu o adăugăm înlistă dacă ea are acceaşi configuraţie cu o altă stare deja existentă (activă saupasivă).

TipTipPredPredd1d1 Leg.Leg.ConfiguraConfiguraţţiaiad1+d2d1+d2AdrAdr. . urmurm. Element . Element InformaInformaţţiileiile stăriistăriiCheieCheie

88/35/35


a) Problema CanibalilorPe malul unui râu se află 2n băştinaşi dintre care n sunt canibali. Aceştia doresc

să traverseze un râu utilizând o barcă, care poate transporta cel mult k oameni şinu poate circula singură. Dacă pe un mal sau în barcă vor fi mai mulţi canibali, atunci aceştia îi vor mânca pe ceilalţi. Cum reuşesc să treacă toţi pe malul opus?

•• ConfiguraConfiguraţţiaia unei stări este (c,b,p), unde c şi b reprezintă numărul canibalilorrespectiv al băştinaşilor necanibali (de pe primul mal), iar p este poziţia bărcii(malul pe care se află). Configuraţia iniţială este (n,n,1) iar cea finală este(0,0,2). La p se poate renunţa deoarece p = d1 Mod 2 + 1 !

•• DistanDistanţţaa dd11 (a unei stări faţă de starea iniţială) reprezintă numărul de traversări cu barca.

•• DistanDistanţţaa dd22 (a unei stări faţă de soluţie) este: d2(c,b)=c+b , reprezentând numărulde persoane care mai trebuie transportate (care nu sunt la locul lor!). Se observăcă d2(sf)=0.

•• TransformareaTransformarea TT (a unei stări sc=(c,b,d1)) este corectă prin transportul(i,j){0,…,n}2 pentru care ((i+j){1,…,k}) şi ((ij) sau (j=0)), dacă(c'=ci,b'=bj){0,…,n}2 şi ((c'b') sau (b'=0)) şi ((c'b') sau (b'= n)).

Exemple:

99/35/35


Programul Pascal este următorul:Program Program Brach_and_BoundBrach_and_Bound;;Type Type TipStTipSt =(=(Activa,PasivaActiva,Pasiva); ); AdrAdr=^Elem; =^Elem; ConfigConfig = Record = Record c,bc,b :Byte End;:Byte End;

Stare = Record d1_2:Byte; Stare = Record d1_2:Byte; Conf:ConfigConf:Config; d1:Byte; ; d1:Byte; Pred:AdrPred:Adr; ; Tip:TipStTip:TipSt End;End;Elem = Record Elem = Record InfInf : Stare; : Stare; Leg:AdrLeg:Adr End;End;

Procedure Procedure Inits(varInits(var s:Stares:Stare; d1_plus_d2,can,bas,d_1:Byte; ; d1_plus_d2,can,bas,d_1:Byte; Adr_Pred:AdrAdr_Pred:Adr; ; t:TipStt:TipSt););Begin With Begin With s,Confs,Conf Do BeginDo Begin

d1_2:=d1_plus_d2; c:=can; b:=bas; d1:=d_1; d1_2:=d1_plus_d2; c:=can; b:=bas; d1:=d_1; PredPred:=:=Adr_predAdr_pred; Tip:=t End; Tip:=t EndEnd;End;Procedure Procedure Ado(VarAdo(Var Sa:AdrSa:Adr; ; s:Stares:Stare); ); VarVar Nou:AdrNou:Adr;;Begin With Begin With Sa^,InfSa^,Inf DoDo

If (Sa<>Nil) And (d1_2<s.d1_2) Then If (Sa<>Nil) And (d1_2<s.d1_2) Then Ado(Leg,sAdo(Leg,s) Else Begin ) Else Begin New(NouNew(Nou););With With NouNou^ Do Begin ^ Do Begin Nou^.InfNou^.Inf:=s; :=s; Nou^.LegNou^.Leg:=Sa; Sa:=:=Sa; Sa:=NouNou End End EndEnd

End;End;Function Function Aleg(Sa:Adr):PointerAleg(Sa:Adr):Pointer;;Begin If Begin If Sa^.Inf.TipSa^.Inf.Tip==ActivaActiva Then Then AlegAleg:=Sa Else :=Sa Else AlegAleg:=:=Aleg(Sa^.LegAleg(Sa^.Leg) End;) End;Function Function Finala(s:Adr):BooleanFinala(s:Adr):Boolean; Begin With ; Begin With s^.Inf.Confs^.Inf.Conf Do Do FinalaFinala:=:=c+bc+b=0 End;=0 End;Function Vida (Function Vida (S:Adr):BooleanS:Adr):Boolean; Begin With ; Begin With s^,Infs^,Inf Do Vida:=(S=Nil) OrDo Vida:=(S=Nil) Or

((Tip=((Tip=PasivaPasiva) And ) And Vida(LegVida(Leg)) End;)) End;

1010/35/35


Procedure Procedure Transf(sc:AdrTransf(sc:Adr; ; k,n:Bytek,n:Byte; ; VarVar Sa:AdrSa:Adr););Function Function Corect(c,b,n:Integer):BooleanCorect(c,b,n:Integer):Boolean;;Begin Begin CorectCorect:=(c In [0..n]) And (b In [0..n]) And :=(c In [0..n]) And (b In [0..n]) And

((c<=b) Or (b=0)) And ((c>=b) Or (b=n)) ((c<=b) Or (b=0)) And ((c>=b) Or (b=n)) End;End;Function Exista(x,y,d_1:Integer; Function Exista(x,y,d_1:Integer; Sa:Adr):BooleanSa:Adr):Boolean;;Begin With Begin With Sa^,Inf,ConfSa^,Inf,Conf DoDo

ExistaExista:=(Sa<>:=(Sa<>Nil)And(((xNil)And(((x==c)And(yc)And(y=b)And(Odd(d1)=Odd(d_1)))=b)And(Odd(d1)=Odd(d_1)))Or Exista(x,y,d_1,Leg)) Or Exista(x,y,d_1,Leg))

End;End;VarVar i,j,x,y:Integeri,j,x,y:Integer; ; s:Stares:Stare;;BeginBegin

For i:=0 To n Do For j:=0 To n DoFor i:=0 To n Do For j:=0 To n DoIf ((If ((i+ji+j) In [1..k]) And ((i<=) In [1..k]) And ((i<=j)Or(jj)Or(j=0)) Then With =0)) Then With sc^,Inf,Confsc^,Inf,Conf Do BeginDo BeginIf Odd(d1) Then Begin x:=If Odd(d1) Then Begin x:=c+ic+i; y:=; y:=b+jb+j EndEnd

Else Begin x:=Else Begin x:=cc--ii; y:=; y:=bb--jj End;End;If If Corect(x,y,nCorect(x,y,n) And (Not Exista(x,y,d1+1,Sa)) Then Begin) And (Not Exista(x,y,d1+1,Sa)) Then Begin

Inits(s,d1+1+x+y,x,y,d1+1,sc,Activa); Inits(s,d1+1+x+y,x,y,d1+1,sc,Activa); Ado(Sa,sAdo(Sa,s) End ) End EndEndEnd;End;

1111/35/35


Procedure Procedure Tipar(sc:Adr;n:ByteTipar(sc:Adr;n:Byte););Begin If sc<>Nil Then With sc^, Begin If sc<>Nil Then With sc^, InfInf, Conf Do Begin, Conf Do Begin

WritelnWriteln( c:3, b:3,Chr(32( c:3, b:3,Chr(32--((d1+1) Mod 2)*14):3);((d1+1) Mod 2)*14):3);WritelnWriteln('('~~~~~~~~~~~');');Writeln(nWriteln(n--c:3,nc:3,n--b:3,Chr(32b:3,Chr(32--(d1 Mod 2)*14):3,#10);(d1 Mod 2)*14):3,#10);ReadlnReadln; ; Tipar(Pred,nTipar(Pred,n))

End; End; End;End;VarVar Sa,sc:AdrSa,sc:Adr; ; n,k:Byten,k:Byte; ; sp:Staresp:Stare; ; BeginBegin

Write(' Write(' Canibali/necanibaliCanibali/necanibali, , nr.locurinr.locuri in in barcabarca : '); : '); Readln(n,kReadln(n,k););Inits(spInits(sp, n+n,n,n,0,Nil,Activa); Sa:=Nil; , n+n,n,n,0,Nil,Activa); Sa:=Nil; Ado(Sa,spAdo(Sa,sp););RepeatRepeatsc:=sc:=Aleg(SaAleg(Sa); ); sc^.Inf.Tipsc^.Inf.Tip:=:=PasivaPasiva;;If Not If Not Finala(scFinala(sc) Then ) Then Begin With sc^, Begin With sc^, InfInf, Conf Do, Conf Do

Tip:=Tip:=PasivaPasiva; ; Transf(sc,k,n,SaTransf(sc,k,n,Sa) End) EndUntil Until Vida(SaVida(Sa) Or ) Or Finala(scFinala(sc););If If Finala(scFinala(sc) Then ) Then Tipar(sc,nTipar(sc,n))

Else Else WritelnWriteln(' (' ProblemaProblema nu are nu are solusoluţţieie'); '); ReadlnReadlnEnd.End.

1212/35/35


b) Problema Ţăranului

Pe malul altui râu se află un ţăran cu un lup, o capră, o varză şi o barcă. Cum

reuşeşte ţăranul să transporte cu barca cele trei cadouricadouri ştiind că nu poate pune în

barcă decât unul sigur iar capra nesupravegheată poate fi atacată de lup sau poate

să mănânce varza?

• Configuraţia unei stări este (l,c,v,,ţţ), unde l,c şi v malul pe care se află, iar ţţ este

(malul pe care se află ţăranul şi barca). Configuraţia iniţială este (1,1,1,1) iar cea

finală este (2,2,2,2). La ţţ se poate renunţa deoarece ţţ = d1 Mod 2 + 1 !

• Distanţa d1 reprezintă numărul de traversări cu barca.

• Distanţa d2 este: d2(l,c,v) = 6-l-c-v , reprezentând numărul de cadouri care mai

trebuie transportate (sunt pe primul mal). ObservămObservăm că d2(sf)=0.

• Transformarea unei stări sc=(l,c,v,d1) este corectă prin transportul unui cadou

dacă acela se află pe malul curent iar capra este supravegheată sau rămâne

singură.

1313/35/35


c) Perspico

Fiind dată o configuraţie a tablei de perspico, se cere să se aşeze piesele într-opoziţie indicată!

• Configuraţia unei stări este matricea de 4x4 cu numere de la 0 la 15 (0=spaţiu).• Distanţa d1 reprezintă numărul de mutări efectuate.• Distanţa d2 = numărul de piese care nu sunt la locul lor.• Transformarea unei stări în alte 4 stări (cel mult) se poate face prin ocuparea

spaţiului liber (00) de către o piesă vecină (având 2, 3 sau 4 posibilităţi).

10105544332211009988776615151414131312121111

00151514141313121211111010998877665544332211

??

1414/35/35

3. Cum trec două şiruri de câte n capre un pod fără să se ocolească, dacă vindin direcţii opuse şi nu se poate sări decât peste o capră adversă?

TemeTeme::

1. Să se rezolve problema corespunzătoarejocului alăturat (configuraţia iniţială fiind cea din partea stângă iar cea finală cea din dreapta), prinmutări similare jocului anterior (perspico). Piesamare trebuie adusă jos prin translaţiile pieselor.

2. Fiind date două cercuri cu câte n bile (din care cele două din intersecţiesunt comune), se cere să se aducă bilele albastre pe cercul albastru, prin operaţii de rotire (vezi figura de mai jos pentru n=10) a celor două cercuri.

__ __

1515/35/35

11.6.11.6. MetodeMetode EuristiceEuristice

În situaţiile în care pentru anumite probleme complexe, pentru a cărorrezolvare nu se cunosc algoritmi, sau aceştia sunt ineficienţi (timp, memorie, cost), se preferă utilizarea unor algoritmi care rezolvă problema dată mult mai rapid, cu efort mic, însă nu ne va furniza întotdeauna cea mai bună soluţie, ci doar soluţiiacceptabile, adică soluţii corecte care pot fi eventual îmbunătăţite.

Prin algoritmalgoritm euristiceuristic vom înţelege un algoritm care furnizează soluţii bunebune, nu neapărat optime, care poate fi implementat rapid şi furnizează rezultate în timp util.

O idee frecvent utilizată constă în descompunerea procesului de determinare a soluţiei în mai multe etape succesive pentru care se poate determina optimul local.

1616/35/35

MetodeMetode EuristiceEuristice

O metodă euristică poate să împartă rezolvarea în mai multe etape, se determină optimul din fiecare etapă (până în acel moment) urmărind prin aceasta ca rezultatul final să fie cât mai bun. Dacă este posibil să determinăm rapid mai multeastfel de soluţii, atunci rezultatul dat va fi cel mai bun dintre acestea.

La scrierea unui algoritm euristic vom aplica doar condiţiile simple darnecesare pentru o soluţie corectă, care eventual va mai fi îmbunătăţită.

În practică se găsesc de multe ori soluţii aproximativeaproximative, mai ales dacăalgoritmul se foloseşte de puţine ori şi efortul de determinare al soluţiei optime estemai mare decât beneficiul obţinut.

Optimul global nu poate fi obţinut întotdeauna prin determinări succesive de optimului local, deci nu se poate aplica metoda Greedy, doar o startegie de acesttip.

1717/35/35

a) Problema Comis-Voiajorului

Fiind date n localităţi şi distanţele dintre ele se cere să se determine traseul de lungime minimă pe care îl parcurge comis-voiajorul pentru a vizita o singurădată fiecare localitate, iar apoi să se reîntoarcă în localitatea de unde a plecat.

• Strategia: se alege întotdeauna cea mai apropiată localitate (dintre cele

nevizitate).• Imbunătăţire: deoarece un traseu este un circuit închis, putem considera ca

punct de plecare oricare dintre localităţi (traseul optim nu depinde de localitateade start). Pentru fiecare localitate considerată ca localitate de plecare, se determină traseul preferat, apoi dintre aceste k trasee corecte se determinătraseul cel mai bun (de lungime minimă) dat ca rezultat final (care nu esteneapărat traseul optim). Evident că traseul final va fi refăcut astfel încât să aibăca localitate de start localitatea de domiciliu a comis voiajorului (în exemplul datam considerat toate cele n variante, deci k=n).

Exemple:MetodeMetode EuristiceEuristice

1818/35/35

Programul Pascal este următorul:

Program Program Metode_Euristice_Comis_VoiajorMetode_Euristice_Comis_Voiajor;;Const Dm = 10;Const Dm = 10;Type Dist = Array[1..Dm,1..Dm] Of Word;Type Dist = Array[1..Dm,1..Dm] Of Word;

Drum = Array[1..Dm] Of Byte;Drum = Array[1..Dm] Of Byte;MultMult = Set Of Byte;= Set Of Byte;

Procedure Procedure Date(VarDate(Var n,s:Byten,s:Byte; ; VarVar d:Distd:Dist););varvar i,j:Bytei,j:Byte; ; Pas:TextPas:Text; ; Rand:StringRand:String;;Begin Begin Assign(Pas,'Me_ComAssign(Pas,'Me_Com--V.PasV.Pas'); '); Reset(PasReset(Pas););

Repeat Repeat Readln(Pas,RandReadln(Pas,Rand) Until Rand='End.';) Until Rand='End.';Read(Pas,n,sRead(Pas,n,s););For i:=1 To n Do Begin For j:=1 To iFor i:=1 To n Do Begin For j:=1 To i--1 Do Begin1 Do Begin

Read(Pas,d[i,jRead(Pas,d[i,j]); ]); d[j,id[j,i]:=]:=d[i,jd[i,j] End; ] End; Readln(Pas,RandReadln(Pas,Rand))End; End; Writeln('dWriteln('d:');:');For i:=1 To n Do Begin For j:=1 To n Do Write(d[i,j]:3); For i:=1 To n Do Begin For j:=1 To n Do Write(d[i,j]:3); WritelnWriteln; End;; End;Close(PasClose(Pas); Writeln(#10)); Writeln(#10)

End;End;


1919/35/35

Procedure Procedure Ad_T(s:ByteAd_T(s:Byte; ; VarVar T:DrumT:Drum; ; VarVar i:Bytei:Byte););BeginBegin

Inc(iInc(i); ); T[iT[i]:=s]:=sEnd;End;Function Function Aleg(VarAleg(Var NeviZ:MultNeviZ:Mult; ; d:Distd:Dist; ; n:Byten:Byte; ; VarVar k:Byte):Bytek:Byte):Byte;;VarVar s,o:Bytes,o:Byte;;Begin s:=k; k:=0; Begin s:=k; k:=0;

Repeat Repeat Inc(kInc(k) Until k In ) Until k In NeVizNeViz;;For o:=k+1 To n Do For o:=k+1 To n Do

If (o In If (o In NeVizNeViz) And () And (d[s,od[s,o]<]<d[s,kd[s,k]) Then k:=o;]) Then k:=o;AlegAleg:=k; :=k; NeVizNeViz:=:=NeVizNeViz--[k[k]]

End;End;Procedure Procedure Traseu(n,s:ByteTraseu(n,s:Byte; ; d:Distd:Dist; ; VarVar T:DrumT:Drum););VarVar i,k,j:Bytei,k,j:Byte; ; Neviz:MultNeviz:Mult;;BeginBegin

i:=0; k:=s; i:=0; k:=s; Ad_T(k,T,iAd_T(k,T,i); ); NeVizNeViz:=[1..n]:=[1..n]--[k];[k];For j:=2 To n Do For j:=2 To n Do Ad_T(Aleg(NeViz,d,n,k),T,iAd_T(Aleg(NeViz,d,n,k),T,i); );

Ad_T(s,T,iAd_T(s,T,i))End;End;


2020/35/35

Function Function Dr_Min(T:DrumDr_Min(T:Drum; ; d:Distd:Dist; ; n:Byte):Wordn:Byte):Word;;VarVar i:Bytei:Byte; ; Lung_Dr:WordLung_Dr:Word;;Begin Begin Lung_DrLung_Dr:=0;:=0;

For i:=1 To n Do Inc(Lung_Dr,d[T[i],T[i+1]]); For i:=1 To n Do Inc(Lung_Dr,d[T[i],T[i+1]]); Dr_MinDr_Min:=:=Lung_DrLung_DrEnd;End;Procedure Procedure Tip_Tr(T:DrumTip_Tr(T:Drum; ; d:Distd:Dist; ; n,s:Byten,s:Byte););VarVar i,k:Bytei,k:Byte; ; M:DrumM:Drum;;BeginBegin

i:=0; Repeat i:=0; Repeat Inc(iInc(i) Until ) Until T[iT[i]=s; M[n+1]:=s;]=s; M[n+1]:=s;k:=0; Repeat k:=0; Repeat Inc(kInc(k); ); M[kM[k]:=]:=T[iT[i]; ]; Inc(iInc(i); If i>n Then i:=1 Until k=n;); If i>n Then i:=1 Until k=n;For i:=1 To n Do Writeln(M[i]:3,'For i:=1 To n Do Writeln(M[i]:3,'------',d[M[i],M[i+1]],'',d[M[i],M[i+1]],'---->',M[i+1]);>',M[i+1]);

End;End;VarVar n,s,i:Byten,s,i:Byte; ; d:Distd:Dist; ; Tm,T:DrumTm,T:Drum; ; Lm,Ld:WordLm,Ld:Word;;BeginBegin

Date (Date (n,s,dn,s,d); Traseu(n,1,d,Tm); Lm:=); Traseu(n,1,d,Tm); Lm:=Dr_Min(Tm,d,nDr_Min(Tm,d,n););For i:=2 To n Do Begin For i:=2 To n Do Begin Traseu(n,i,d,TTraseu(n,i,d,T ); Ld:=); Ld:=Dr_Min(TDr_Min(T ,,d,nd,n););

If Ld<Lm Then Begin Tm:=T; Lm:=Ld End If Ld<Lm Then Begin Tm:=T; Lm:=Ld End EndEnd;;Writeln('DrWriteln('Dr. Min. '); . Min. '); Tip_Tr(Tm,d,n,sTip_Tr(Tm,d,n,s););Writeln('Lg.:',Lm:3); Writeln('Lg.:',Lm:3); ReadlnReadln

End.End.


2121/35/35

6 3 6 3 1 2 3 4 5 1 1 2 3 4 5 1 N S ...N S ...2 2 2 2 D D ……4 3 4 3 335 4 2 5 4 2 445 7 5 4 5 7 5 4 559 5 6 5 79 5 6 5 7 66


Dr. Min.3---2-->44---4-->55---7-->66---5-->22---2-->11---4-->3

Lg.: 24

Rezultate

Date

2222/35/35

a) Problema Execuţiei Lucrărilor de către mai multe ProcesoareCum sunt repartizate m lucrări la n procesoare astfel încât execuţia lor să se termine cât mai repede. Mai precizăm că procesoarele pot lucra simultan şi oriceprocesor poate executa orice lucrare, iar o lucrare nu va fi executată de către maimulte procesoare. Timpul de execuţie al lucrării i este ti ( i = 1,2,…,m).

• Strategia: se alege lucrarea neexecutată de durată maximă (se ordoneazălucrările descrescător după timpul de execuţie) care va fi repartizată primuluiprocesor liber. Practic se va determina o ordine O de execuţie a celor m lucrări(oi reprezintă a câta lucrare se execută a i-a, adică este pe locul i în coada de aşteptare).

• Imbunătăţire: deoarece strategia nu garantează optimul (de exemplu pentrutimpii 3,3,2,2,2 rezultatul dat va fi 7 ore la o prelucrare cu două procesoare, însăoptimul este 6) vom încerca diverse perturbării ale acestei ordini propuse, iardintre variantele obţinute o vom reţine pe cea mai convenabilă (în speranţa că vafi chiar cea optimă).


2323/35/35


Program Program Metode_Euristice_ProcesoareMetode_Euristice_Procesoare;;

Const Dm = 100;Const Dm = 100;

Type Type TimpiTimpi = Array[1..Dm] Of Word;= Array[1..Dm] Of Word;CoadaCoada = Array[1..Dm] Of Byte;= Array[1..Dm] Of Byte;

Procedure Procedure Date(VarDate(Var n,m:Byten,m:Byte; ; VarVar T:TimpiT:Timpi););VarVar i,j:Bytei,j:Byte; ; Pas:TextPas:Text; ; Rand:StringRand:String;;

Begin Begin Assign(Pas,'Me_Rep_L.PasAssign(Pas,'Me_Rep_L.Pas'); '); Reset(PasReset(Pas););

Repeat Repeat

Readln(Pas,RandReadln(Pas,Rand) )

Until Rand='End.';Until Rand='End.';

Readln(Pas,nReadln(Pas,n); ); Read(Pas,mRead(Pas,m););

For i:=1 To m Do For i:=1 To m Do Read(Pas,t[iRead(Pas,t[i]);]);

Close(PasClose(Pas))

End;End;


2424/35/35

Procedure Procedure Ordine(T:TimpiOrdine(T:Timpi; ; VarVar O:CoadaO:Coada; ; m:Bytem:Byte););

varvar i,k:Bytei,k:Byte; ; Ordonat:BooleanOrdonat:Boolean; ; Aj:WordAj:Word;;

Begin k:=1; For i:=1 To m Do Begin k:=1; For i:=1 To m Do o[io[i]:=i;]:=i;

Repeat Repeat OrdonatOrdonat:=True;:=True;

For i:=1 To For i:=1 To mm--kk DoDo

If If t[o[it[o[i]]<t[o[i+1]] Then Begin]]<t[o[i+1]] Then Begin

AjAj:=:=o[io[i]; ]; o[io[i]:=o[i+1]; o[i+1]:=]:=o[i+1]; o[i+1]:=AjAj; ; OrdonatOrdonat:=False End;:=False End;

Inc(kInc(k););

Until Until OrdonatOrdonat

End;End;

Function Function Liber(P:TimpiLiber(P:Timpi; ; n:Byte):Byten:Byte):Byte; ; VarVar k,j:Bytek,j:Byte;; { Minim }{ Minim }

Begin Begin

k:=1; For j:=2 To n Do If k:=1; For j:=2 To n Do If p[jp[j]<]<p[kp[k] Then k:=j; ] Then k:=j; LiberLiber:=k :=k

End;End;


2525/35/35

VarVar n,m,i,j:Byten,m,i,j:Byte; ; T,P:TimpiT,P:Timpi; ; O:CoadaO:Coada; ; TMax:WordTMax:Word;;

BeginBegin

Date (Date (n,m,Tn,m,T); For i:=1 To m Do Write(t[o[i]]:3); ); For i:=1 To m Do Write(t[o[i]]:3); WritelnWriteln;;

Ordine(T,O,mOrdine(T,O,m); For i:=1 To m Do Write(t[o[i]]:3); ); For i:=1 To m Do Write(t[o[i]]:3); WritelnWriteln;;

For j:=1 To n Do For j:=1 To n Do p[ip[i]:=0;]:=0;

For i:=1 To m Do Begin j:=For i:=1 To m Do Begin j:=Liber(P,nLiber(P,n); ); Inc(p[j],t[o[iInc(p[j],t[o[i]]);]]);

For j:=1 To n Do Write(p[j]:3); For j:=1 To n Do Write(p[j]:3); WritelnWriteln End;End;

TMaxTMax:=p[1]; :=p[1];

For j:=2 To n Do For j:=2 To n Do

If If p[jp[j]>]>TMaxTMax Then Then TMaxTMax:=:=p[jp[j];];

WritelnWriteln(' (' TimpulTimpul nesarnesar esteeste ',',TMaxTMax); ); Readln

End.End.3 3 n n ProcesoareProcesoare

7 3 2 5 1 4 6 4 7 3 2 5 1 4 6 4 m Lucrari:t1,t2...tmm Lucrari:t1,t2...tm


1 2 3 4 5 6 76 5 4 4 3 2 16 0 06 5 06 5 46 5 86 8 88 8 89 8 8Timpul nesar este 9

Rezultate

Date

2626/35/35

TemeTeme::

Ca temă poate fi orice problemă de tip Greedyla care nu am demonstrat obţinerea optimului global !

2727/35/35

11.7. 11.7. AlgoritmiAlgoritmi GeneticiGenetici (nu se (nu se cercer la ex.)la ex.)

Aceşti algoritmi rezolvă probleme de optimizare după modelul selecţiei

naturale, conform căreia populaţia evoluează prin supravieţuirea celui mai

performant. Algorimii genetici nu garantează optimul, dar furnizează soluţii bune.

O populaţie este formată din indivizi (fiecare reprezentând o soluţie potenţială)

care evoluează (prin selecţie, (re)combinare şi mutaţie) spre optim. Un individ

este caracterizat prin unul sau mai mulţi cromozomi (formând genotipulgenotipul) Un

cromozom conţine caracteristicile individului (poartă informaţia genetică) într-un

număr fix de gene.

Un algoritm genetic este caracterizat prin codificarea spaţiului de căutare,

funcţia de evaluare (pentru selecselecţţieie) în vederea reproducerii (recombinarerecombinare) şi hazard

în evoluţie (mutamutaţţieie).

2828/35/35

AlgoritmiAlgoritmi GeneticiGenetici

Algoritmul Ag_Simplu este: Date Nr_Gen, Dim_Pop; { Nr. Max. de generaţii, Dim. Populaţiei }Init(P,Dim_Pop); t:=0; { Populaţia iniţială, la momentul t=0 }Repetă t:=t+1;

Selectează(P, Pi,Pj); { SelectezSelectez doi indivizi : i,j pt. reproducere}Combin (Pi,Pj,Desc); { Prin recombinarerecombinare un descendent }Mutatie(Desc); { care suferă o mutamutaţţieie }Pk:=CelMaiSlab(P); { Determină celcel maimai slab slab individindivid }P:=P\{Pk}{Desc}; { care se înlocuieşte cu noul individ }Pe:=CelMaiBun(P); { Determină celcel maimai bun bun individindivid }

Până_Când (f(Pe)=Max) sau (t>Nr_Gen); { S-a găsit optimul sau o aproxim. }Rezultate Pe { Soluţia sau o aproximantă a acesteia }

Sf_Ag.

Calitatea unui individ se măsoară cu funcţia de performanţă (de adecvaresau de evaluare): f : X RR , unde X este spaţiul de căutare.

Operatorii utilizaţi sunt următorii: Recombinare r : Xp Xq ,Mutaţie m : Xp Xq , Supravieţiure s : Xp BB .

2929/35/35

a) Problema determinării unei submulţimi de sumă dată.

Fiind dată o mulţime de numere reale pozitive şi un număr T, se cere să se determine o submulţime de sumă T.

Cromozomul este codificat printr-un şir de n gene {0,1} (1=se însumează, 0=nu).

Combinarea este realizată luând aleator câte o genă din cei doi cromozomipărinte.

Mutaţia este realizată schimbând eventual (aleator) câte o genă. Performanţa se măsoară în funcţie de distanţa sumei până la totalul dorit T

(Fit).

Exemplu:AlgoritmiAlgoritmi GeneticiGenetici

3030/35/35


Program Program SubmulSubmulţţime_de_suma_Daime_de_suma_Datătă;;Uses Uses Crt,GraphCrt,Graph;;Const n=15; Const n=15; T:IntegerT:Integer=250; =250; Nr_GenNr_Gen=500;=500;

A:Array[1..n] Of Word = (1,2,3,5,10,15,20,25,50,75,80,10A:Array[1..n] Of Word = (1,2,3,5,10,15,20,25,50,75,80,100,125,150,200);0,125,150,200);Type Type GenaGena=0..1; =0..1; CromozomCromozom=Array[1..n] Of =Array[1..n] Of GenaGena;;VarVar m,i,j,k,e:Bytem,i,j,k,e:Byte; ; P:Array[ByteP:Array[Byte] Of ] Of CromozomCromozom;;

Desc:CromozomDesc:Cromozom; ; Pas:IntegerPas:Integer;;Procedure Procedure Combin(x,y:CromozomCombin(x,y:Cromozom; ; VarVar z:Cromozomz:Cromozom); ); VarVar j:Bytej:Byte;;Begin For j:=1 To n DoBegin For j:=1 To n Do

If Random(2)=0 Then If Random(2)=0 Then z[jz[j]:=]:=x[jx[j]]Else Else z[jz[j]:=]:=y[jy[j]]

End;End;Procedure Procedure Mutatie(VarMutatie(Var x:Cromozomx:Cromozom); ); VarVar j:Bytej:Byte;;Begin For j:=1 To n DoBegin For j:=1 To n Do

If Random(100)<2 Then If Random(100)<2 Then x[jx[j]:=1]:=1--x[j]x[j]End;End;


3131/35/35

Function Function Fit(i:Byte):WordFit(i:Byte):Word; ; VarVar j:Bytej:Byte; ; s:Words:Word;;Begin Begin s:=0;s:=0;

For j:=1 To n DoFor j:=1 To n Dos:=s:=s+P[i][js+P[i][j]*]*a[ja[j];];

Fit:=Fit:=Abs(sAbs(s--T)T)End;End;

Function Function CelMaiSlab:ByteCelMaiSlab:Byte; ; VarVar i,k:Bytei,k:Byte;;Begin Begin k:=1;k:=1;

For i:=2 To m DoFor i:=2 To m DoIf If Fit(iFit(i)>)>Fit(kFit(k) Then k:=i;) Then k:=i;

CelMaiSlabCelMaiSlab:=k:=kEnd;End;Function Function CelMaiBun:ByteCelMaiBun:Byte; ; VarVar i,k:Bytei,k:Byte;;Begin k:=1;Begin k:=1;

For i:=2 To m DoFor i:=2 To m DoIf If Fit(iFit(i)<)<Fit(kFit(k) Then k:=i;) Then k:=i;

CelMaiBunCelMaiBun:=k:=kEnd;End;


3232/35/35

VarVar Gd,Gm:IntegerGd,Gm:Integer; ; ss:Stringss:String;;

Function Function Des_Cromo(i:Integer):WordDes_Cromo(i:Integer):Word; ; VarVar j:Bytej:Byte; ; s:Integers:Integer;;Begin s:=0;Begin s:=0;

For j:=1 To n DoFor j:=1 To n Dos:=s:=s+P[i][js+P[i][j]*]*a[ja[j];];

MoveTo(6*MoveTo(6*i,(Ti,(T--ss) Div 1 + ) Div 1 + GetMaxYGetMaxY Div 2 Div 2 -- 5);5);LineRel(LineRel(--3,+5); LineRel(+3,+5); LineRel(+3,3,+5); LineRel(+3,+5); LineRel(+3,--5); LineRel(5); LineRel(--3,3,--5);5);

End;End;

Procedure Procedure PopulatiePopulatie; ; VarVar i:Bytei:Byte;;BeginBegin

Line(1,GetMaxY Div 2,GetMaxXLine(1,GetMaxY Div 2,GetMaxX--1,GetMaxY Div 2);1,GetMaxY Div 2);For i:=1 To m DoFor i:=1 To m Do

Des_Cromo(iDes_Cromo(i););End;End;


3333/35/35

BeginBeginWrite(' Write(' DatiDati m < 256 : '); m < 256 : '); Readln(mReadln(m); ); Randomize;Randomize; { Nr. { Nr. indind. }. }

InitGraph(Gd,Gm,'c:\Bp\Bgi'); SetWriteMode(1); SetBkColor(Blue);For i:=1 To m DoFor i:=1 To m Do { { Init(PInit(P); }); }

For j:=1 To n Do For j:=1 To n Do P[i][jP[i][j]:=Random(2);]:=Random(2);Pas:=0; Pas:=0; SetColor(White); PopulatiePopulatie;;

OutTextxy(400,GetMaxY-60,'Initial... Press a Key ...'); ReadKey;OutTextxy(400,GetMaxY-40,'To Stop... press Esc key ');Repeat Pas:=Pas+1;Repeat Pas:=Pas+1; {{PopulatiePopulatie;};}

i:=Random(m)+1;i:=Random(m)+1;j:=Random(m)+1; While (i=j) Do j:=Random(m)+1;j:=Random(m)+1; While (i=j) Do j:=Random(m)+1;CombinCombin ((P[i],P[j],DescP[i],P[j],Desc););Mutatie(DescMutatie(Desc););k:=k:=CelMaiSlabCelMaiSlab; ; Des_Cromo(k); SetColor(GreenSetColor(Green););

Line(1,GetMaxY Div 2,Pas,GetMaxY Div 2); Delay(50);Line(1,GetMaxY Div 2,Pas,GetMaxY Div 2); SetColor(White);

P[kP[k]:=]:=DescDesc; ; Des_Cromo(k); Delay(25);e:=e:=CelMaiBunCelMaiBun;;

Until (Until (Fit(eFit(e)=0) Or (Pas>)=0) Or (Pas>Nr_GenNr_Gen) ) Or (KeyPressed And (ReadKey=#$1B));


3434/35/35

SetWriteMode(0); SetColor(Yellow); Des_Cromo(e);

Str(Fit(e),ss);OutTextxy(30,GetMaxY-60,'Err.:'+ss+' ');Str(Pas,ss);OutTextxy(230,GetMaxY-60,'Gen. :'+ss+' !');MoveTo (30,GetMaxY-40); Str(T,ss); OutText(ssOutText(ss+' = ');+' = ');For j:=1 To n DoFor j:=1 To n Do

If If P[e][jP[e][j]=1 Then Begin ]=1 Then Begin Str(a[j],ss);OutText('+'+ss)

End;End;OutTextxy(400,GetMaxY-20,'To Exit... Press a Key ...'); ReadKey;CloseGraph

End.End.


3535/35/35

TemeTeme::

Ca temătemă poate fi orice problemă de tip EuristicEuristic !!

. . .. . . C_C_1133 / 11.01.20/ 11.01.201133

11. Metode de elaborare a algoritmilorper/Fp -_-/Fp_13.pdfproblema are soluţie, chiar dacăspaţiul...

Documents

Transcript of 11. Metode de elaborare a algoritmilorper/Fp -_-/Fp_13.pdfproblema are soluţie, chiar dacăspaţiul...