.

Алгоритмы

Язык: русский
Формат: реферат
Тип документа: Word Doc
0 1520
Скачать документ

PAIEŠKA PAPRASTAME SĄRAŠE
1.1. Nuosekli paieška
Tegu įrašai išdėstyti atsitiktinai kaip buvo įrašyti. Reikia surasti duotą įrašą pagal raktą. Nuosekliai ieškant reikia peržiūrėti visus įrašus nuosekliai.Vid.peržiūrėų įrašų sk. ieškant yra Lap =L/2. Jei įrašo nėra teks peržiūrėti visus įrašus L. Tarkim ieškomo įrašo su tikimybe p0 nėra sąraše, tada vid. peržiūrėtų įrašų sk. Lap=L*p0+i1L (i*pi ); pi=1-p0/L. Ieškant įrašo sutvarkytame faile(įrašai išdėstyti pagal raktą) reikia peržiūrėti iš eilės, todėl vid. peržiūrėtų įrašų sk. tas pats: Lsp=L/2. Jei ieškomo įrašo nėra, tai paieška nutraukiama kai eilinis raktas bus didesnis už užduotą. Atliekant k įrašų paiešką nesutvarkytame faile vid. peržiūrėtų įrašų sk. Lkap = k * L / 2.
1.2. Paieška interpoliavimas
Jei sąrašai surūšiuoti ir žinomas pirmo įrašo raktas K(1) ir paskutinio K(n) tai galima apskaičiuoti p=X-K(1)/K(n)-K(1). X-ieškomo įrašo raktas.Paiešką pradedam nuo įrašo kurio numeris p*n.
1.3. Binarinė paieška
Naudojama surūšiuotame masyve. Jis dalinamas pusiau ir ieškomas raktas lyginamas su vidurio raktu ir t.t.. Idealus masyvo dydis 2n-1.Jei 31 įrašas reikės 5 žingsnių, kad surasti įrašą 3125-1. Bendru atveju 2n-1-1 Fk, tai imam apatinę dalį, tada VF+1, o A išlieka tas pats ir t.t.. Toks dalinimas atliekamas tol, kol nepasidaro AV. Rekurentinė lygtis aprašanti max palyginimų sk. binarinėje paieškoje yra:
f(n){1, n1 f(  n/2  )+1, n>1. Sprendžiant rekurentinę formulę galim užrašyti: f(n)  f( n/2 ) + 1  f( n/21 ) + 1( f( n/22 )+1) + 1  f( n/22 )+2 … f( n/2i ) + i, kol
 n/2i 1; ilogn. f(n)logn+1 arba f(n)  log (n+1) . Vid. palyginimų sk. ideliu atveju kai n  2k-1:
f(n)1* 1/n + 2*2/n + 3*4/n +…+ (log n + 1)*2k-1/n  1/n * i1log n+1 (i * 2i-1). 2k-1-1F1, tai ieškomas įrašas yra antroje dalyje, kuri mažesnę už pirmąją.
2r-1-12. Tas dvi dalis galim dalinti dar pusiau. T(n)  T(2k)  2T(2k-1)+2  2(2T(2k-2) + 2) +2  22T(2k-2) + 22 +2  2k-1T(2) + 2k-1 +…+ 23 +22 +2  2k-1 + 2k-1 + 2k-2 + … + 23 +22 +2  n+2k-1-2  n+n/2-2  3n/2-2. Atliekant tokią skaidymo procedūrą, algoritmo sudėtingumas sumažėja.

Rekurentinių lygčių sprendimas
T(n)  {b, n1aT(n/c) + bi, n>1
a,b,c-teigiamos const.nck; klog cn.
T(1)  b
T(c)  aT(1) + bc  ab + bc  (1+a/c);
T(c2)  aT(c) + bc2  a(ab + bc) + bc2  a2b + abc + bc2  bc2(1+ a/c + a2/c2) ……
T(n)  T(ck)  aT(ck-1) + bck  bck(1+a/c+a2/c2+…+ak/ck) . T(n)  bni0logcn (a/c)i. Jei ac, turim didėjančią geometrinę progresiją. Tuomet T(n) greitai didėja didėjant n, tai eksponentinio sudėtingumo algoritmas. Uždavinį suskaidžius į 4 dalis ir tokių dalių paėmus 4 – ias: a=c=4, gauname (nlog4n), log2n > log4n. Kas bus, kai n≠ck? Išvestos formulės netinka, bet paėmus atvejį, kai n’=ck > n, išvados galioja. Uždavinys gali būti sprendžiamas su rekursija arba be jos, tačiau uždavinio sudėtingumas nepasikeičia. Su rekursija algoritmas sprendžiamas šiek tiek ilgiau.
T Apie rekurentinės lygties tipo T(n)=aT(n\c)+f(n), kur a≥1, c≥1, f(n)-teigiama f-ja. 1) Jei f(n)= (n(logca)-) ,tai T(n)= (nlogca). 2) Jei f(n)= (nlogca) ,tai T(n)= (nlogca . log n. 3) Jei f(n)= (n(logca)+) ,tai T(n)= (f(n)), jei af(n\c)≤bf(n) (b>1 dideliems n).

Balansavimas (skaidymas į vienodas dalis). Reikia surūšiuoti n ilgio masyvą didėjimo tvarka. 1.surandam min, kurį sukeičiam su pirmu, po to iš (n-1) elemento surandam min ir sukeičiam su antru ir t.t.. Rekursyvinė lygtis aprašanti palyginimų sk.: T(n)  {0, n1T(n-1)+n-1, n>1 ;
T(n)  n(n-1)/2, o algoritmo sudėtingumas (n2). Čia skaldymas į dvi nelygias dalis: į vieno elemento ir (n-1).2. Gaunamas suskaldžius uždavinį į dvi lygias dalis  n/2. Tarkim, kad n  2k. Viena dalis nuo x1 iki xn/2 , o kita nuo xn/2+1 iki xn. Šias dalis surūšiuojam ir sujungiam palyginant minimalius elementus. Sujungimui reiks maksimum n-1 palyginimų. Tokį skaidymą galima rekursyviai tęsti toliau, kol lieka dalyse po 1 elementą. Rekursyvinė lygtis aprašanti tokį algoritmą yra:
T(n)  {0, n1 2T(n/2) + n – 1, n>1.
Šio algoritmo sudėtingumas ( n log n).

Dinaminis programavimas.
Kartais galima efektyvius algoritmus gauti naudojant dinaminį programavimą. Šiuo būdu reikėtų skaičiuoti visus dalinius uždavnius, bet sprendžiami nuo mažų prie didelių. Atsakymai prisimenami lentelėje ir uždaviniai jungiami, kad būtų išspręstas visas uždavinys ir gautas optimumas. Pvz. sudauginant n matricų yra labai svarbus daugybos eiliškumas, kuris nulemia bendrą veiksmų skaičių. Pažymim mi j minimalus veiksmų sk. dauginant matricas: Mi*Mi+1*…*Mj, kur 1  i i, i  k K2. Jeigu daugiau sukeičiam vietom. Jeigu ne nieko nedarom ir t.t. Paskutinis palyginimas bus Km > Kn. Po 1 iteracijos didžiausias skaičius atsiranda pabaigoje. Sekanti iteracija vyksta su n-1 elementu, nes paskutinio neimame ir t.t.
Pirmoje iteracijoje bus (n-1) palyginimų. Antroje iteracijoje (n-2), i-tojoje iteracijoje (n-i).
Tuomet bendras palyginimų skaičius bus

Kadangi ne visuomet elementai sukeičiami, tuomet jeigu išrūšiuota seka bus 0 pakitimų, o atvirkščiai išrūšiuota seka – n(n-1)/2 pakeitimų. Tada vidutinis pakeitimų sk. bus n(n-1)/4.
Jeigu yra n elementų seka, tai iš jos gali būti padaryti n! sekų. Mes laikome kad bet kuri seka gali pasitaikyti su vienoda tikimybe 1/n!.
Kiekvienai sekai galima parašyti inversišką seką. Jeigu turime tokias 2 sekas, ir jas surūšiuosime, tai sumalinis pakeitimų sk. bus n(n-1)/4. Algoritmo sudėtingumas (n2).
Iterpimo metodas.
Čia eilinis elementas yra įterpiamas į jau surūšiuotą elemetų seką. Tegul turime n elementų iš viso ir turime jau i surūšiuotų elementų. Mums reikia įterpti i+1 elementą Ki+1. Ki+1 atsidurs tarp Kj 0, tai t = t1- t2, S2(t)S2(t1)+ S2(t2)-2M12 t.y. dispersija mažesnė nei nepriklausomų dydžių atvju. S2(t) S2(t1)/K+ S2(t2)/K – 2K12S(t1) * S(t2)= S2(t1)/K+ S2(t2)/K – 2M12/S(t1)S(t2)* S(t1)/k * S(t2)/K = S2(t1)/K+ S2(t2)/K – 2M12/K t.y. ir vidurkio dispersija yra mažesnė, nes atsiima 2M12/K. Atitinkamai intervalinis įvertinimas: t – tpS(t) A(J) tai sukeičiame juos vietomis ir II+1 ir t.t.. Taip palyginus su visais elementais, gausime, kad kairėje pusėje elemento su kuriuo mes lyginome bus elementai mažesni už jį, o dešinėje didesni, t.y. suskaldėm seką jo atžvilgiu. Elementas pagal kurį atlikome palyginimus yra pirmasis ir vadinamas generaliniu. Čia generalinis elementas visada buvo pirmas, tačiau tai nebžtina. Gaima paimti bet kurį. Generaliniai elementai gali būti parenkami įvairiai: pirmas, atsitiktinis, mediana (vidurinis). Skaidyti pagal medianą geriausia. Galima paimti nedidelią imtį iš kelių sekos elementų ir surasti medianą. Imant visada pirmą elementą, blogiausias atvejis gaunasi, kada seka yra surūšiuota. Tada seka suskaldoma į vieną elementą ir visą likusią. Gausis taip kaip ir kituose algoritmuose. Tuo atveju algoritmo sudė-tingumas (n2), o visais kitais atvejais žymiai geriau. Šis algoritmas gerai veikia didelėm sekom, o taip pat reikia tinkamai parinkti generalinį elementą. Vid. veiksmų sk. yra:

c-koef., cn-veiksmų sk. atliekant pirmą suskaldymą. Generalinis elem. atsiranda i-ojoje vietoje ir gaunam dvi sekas (i-1) ir (n-i). Veiksmų sk. skaldant seką (i-1) yra i1n f(i-1), o seką (n-i) yra i1n f(n-i). 1/n- i su vienoda tikimybe gali atsirasti bet kurioje vietoje.
i1n [f(i-1)+ f(n-i)]f(0)+ f(n-1)+ f(1)+ f(n-2)+…+ f(n-2)+ f(1)+ f(n-1)+f(0) 2 f(0)+2f(1)+…+2f(n-2)+2f(n-1)2i1nf(i)
f(n)cn + 2/ni0n-1 f(i), kai n>1
f(0)f(1)b
f(2)2c+2/2[f(0)+f(1)]2c+2bk
f(3)3c+2/3[f(0)+f(1)+f(2)]3c+2/3[2b+2c+2b]3c+8/3b+4/3c(8b+13c)/3. Įrodyta, kad visada galioja lygybė f(n) = log n! =n log n – n/ln2+1/2 log n + 
 – paklaida. (Stirlingo formulė)
Minimalus palyginimų sk. blogiausiu atveju yra apie nlogn . Palyginus
log n! su f(n) = n log n – 2 log n + 1 pasirodo, kad suliejimo metodas pagal minimalų palyginimų sk. nėra minimalus.

IŠRINKIMAS
Maksimalaus elemento išrinkimas iš n elementų sekosRadus max elementą, reikia atlikti n-1 palyginimą. O kiek reikia priskyrimų? Jei seka – mažėjanti, tai reikės 1 prisky-rimo. Jei seka – didėjanti, tai reikės n priskyrimų. O koks vidutinis priskyrimų sk, jei bet kokia seka iš n elementų vienodai galima?
Hn=1 + P[ai > aj]  1 = 1+ 1/2  1 = = ln n +  +1/2n + 
Ši eilutė diverguojanti, t.y. didėjant n, jos reikšmė didėja.(Eulerio formulė) čia 0,577; - paklaida.

Sekančio didžiausio elemento radimas (2-ų max radimas). Norint surasti max elementą, reikia n-1 palyginimų. Po to jį pašalinam ir surandame kitą max. Tam reikia n-2 palyginimų. Todėl iš viso palyginimų sk: 2n-3. Šį algoritmą galima pagerinti suskaldžius n elementų į 2 dalis: n/2 ir n/2 Ieškome max elementų: I dalyje max el. surasti reikės n/2 – 1 palygini-mų, II dalyje – n/2 palyginimų. Po to juos reikės tarpusavyje palyginti. Iš viso
reikės palyginimų. Paskutiniame lygyje pralai-mėjusį elementą reikės palyginti su pra-laimėjusiais elementais, lyginant su mak-simaliu. Taip rasim kitą max elementą. Reikia palyginimų. Toliau galima kelti klausimą, ar negalima įėjimo seką padalinti į 4, 8 ir t.t. dalių, kol neprieisim algoritmo, kuris atitinka piramidinį rūšiavimą. Lai I fazėje lyginame po 2 elementus: n=8
a1
a1 a6
a1 a3 a6 a7
a1 a2 a3 a4 a5 a6 a7 a8
Ieškant kito max elemento, reikia a6 ly-ginti su pralaimėjusiais, randant a1
Jei a6 > a3, tai reikia palyginti ir ar a6 > a2
Jei a6 a6
Radom max per 2 palyginimus. Pirami-dėje radom per n-1 palyginimą. Tai yra sekantis randamas per log n -1 palygi-nimą. Gauname, kad šiuo metodu palygi-nimų sk. yra optimalus: n + log n – 2 .

Geriausio (max) ir blogiausio (min) elemento išrinkimas
Galima siūlyti suskaidyti seką n į 2 dalis ir surašyti šiose dalyse max ir min elementus. Palyginus max-ius elementus gaunamas max-is elementas, min-ius -min-is. Rekursyviai galima suskaidyti iki 1,2 elementų. Palyginant 2 elementus tarpusavyje iš karto gauname max ir min elementus. Rekurentinė lygtis, aprašanti tokį akgoritmą:
f(n)=
Bendras šios srities sprendinys:
(n-2log n)/2, kai n =k, tai imame S1, kuriame yra (i-1) ele-tų. Jei i . i1 ,i2 …ik = n. P(i1 ,i2 ..ik ).
Nagrinėjome šio bendro uždavinio kelis atvejus:
1.mažiausio elem, radimas P(1,n-1)=n-1. (palyginimų sk ieškant min =n-1).
2.1-mo ir 2-ro mažiausio elem, radimas P(1,1,n-2)=n+log n-2.
3.maž. ir didž. elem, radimas
P(1, n-2, 1)=3/2 n-2
4.k-tojo didesnio elem, radimas
P(k-1, 1,n-k) = ( n)
5.Dviejų mažiausių: P(2,n-2)=n+log(n-1)-2
6. trijų mažiausių: P(3,n-3)=n+2log n-3|2|1|
įvairiais atvejais priklausomai nuo n.
Galima kelti tokius uždavinius:
a.surasti k mažiausių elem, P(k,n-k).
b. surasti k-ąjį elementą P(k-1,1,n-k).
c. surasti k elementų iš eilės P(1,1,1,..,1,n-k)
P(1,1,1,..,1,n-k)> P(k-1,1,n-k)> P( k,n-k).

Veiksmai su aibemis(DS požiuriu)
Uždavinius galima suvesti į veiksmus su aibėmis. Išanalizuojam įvairias Duomenų Struktūras ir pasirenkam labiausiai tinkamą. Gero alg. Sukūrimas neatski-riamas nuo tinkamos DS pasirinkimo. Pagr. mat. veiksmai su aibėmis būdingi informacinės paieškos uždaviniams:
1:PRIKLAUSYTI (a, S). Nustato ar elem.a priklauso aibei S. Jei a priklauso S, tada TAIP, priešingu atveju NE..
2:ĮSTATYTI (a,S).Įstato elem, a į S. Gaunasi aibė S ir elem, a t.y. S{a}.
3:PAŠALINTI (a,S). Pašalina a elem, iš aibės S t.y. aibė S pakeičiama į S-{a}.
4. APJUNGTI (S1,S2,S3). Atlieka tokį veiksmą: S3= S1S2.
5:RASTI (a). Reikia rasti aibę, kurioje duotu momentu randasi elem, a. Jei rastų dvejose aibėse, tada veksmas nenustatytas.
6:SUSKALDYTI (a,S) Čia aibėselem, užduoti santykiu a}
7:MIN (S) Suranda mažiausią aibės S elem.
Šiuos veiksmus reik atlikti tam tikra seka duomenų bazėje.Mus domina laikas atliekant veiksmų seką priklausomai DB dydžio ir nuo veiksmų sekos ilgio. Šis laikinas sudėtingumas paprastai tikrinamas blogiausiu atveju ir vidutinišku.
PVZ.
Kraskalo alogoritmas.
Surasti ekonominį medį neorentuotam grafe. Yra grafas G (V, E).V-virš. aibė,E-briaunų aib. Kieikviena briauna iš E turi svorį c. Reikia surasti grafą-medį G(V,T). T-E poaibis iš. Taip kad  i T ci =>min.
Medis grafas be ciklo. Jei medyje S(V,T) pridesime kokią nors briauną, tai susidarys vienas ciklas. Grafo G mišku vadiname neorentuotų medžių aibė: {V1.,T1}, {V2.,T2},…,{Vk.,Tk} . V1 ,V2, .. Vk-suskaldyta aibė V. V=V1 V2,..Vk; V i Vj =. Atitinkamai T1,T2,…Tk yra aibės E poaibiai. Kraskalo alg sako: reikia medžius jungti minimalaus ilgio briaunomis ir apjungti sujungtus medžius į vieną. Taip atliekama tol, kol nesigauna vienas ekonominis medis.
////////// P R O G R A M A————–
1 ir 2 yra medžiai miške. Šiame algo-me E – grafo briaunų aibė. T- ekonominio medžio briaunų aibė. VS – grafo miško medžiai kurie apjungiami į ekonominį medį:
Iš pradžių VS- atskiras grafo G viršūnei kaip vieno elem, aibei(viena viršūnė-vienas miško medis).
Kadangi aibėje E yra surašytos briaunos,kurias rekia imti su minimaliu svoriu. Tai galbūt naudinga atlikti jų surūšiavimą. Tai gali būti paimtas alg, kurio sudetingumas (eloge).e-briaunų sk.
Tuomet 3-čio operatoriaus sudetingumas proporcingas viršūnių sk. n (n). Laikas reikalingas surasti aibei 1 ir 2 įkurias įeina viršūnes V ir  ir jų sujungimas, jei priklauso skirtingoms aibėms yra beveik tuščias: (n) . O jei tiksliau t.y. (n G(n)), kur G(n) – atvirkštinė f-jai F(n) =2F(n-1)
Jeigu naudosime sąrašų struktūrą, tai (7,8) šios dalies alg. sudetingumas ( MAX(e,n log n)). Todėl matom, kad visumoje Kraskalo algoritmo sudėtingumas yra (e log e), kurį nulemia rūšiavimas.

Paskirstymo metodas (heširavimo)
Mes čia nagrinėsime duomenų struktūrą besikeičiančioje aibėje S. Nauji elementai bus įstatomi, seni pašalinami ir karts nuo karto reikės atsakyti į klausimą: ar priklauso duotu momentu konkretus elementas aibei S. Bus reikalingi tokie veiksmai: PRIKLAUSYTI(a,s), ĮSTA-TYTI(a,s), PAŠALINTI(a,s). O elemen-tai, kurie gali būti aibėje S, imami iš labai didelės aibės. Panagrinėsime paskirstymo metodą, kuris leidžia gerai atlikti šiuos 3 veiksmus. A
0 h(a)=1
1 h(a)=2

h(a)=
m-1 =m-1
A-nuorodų masyvas(kiekvienas elementas – nuoroda į sarašą). Paskirstymo funkcija h(a) atvaizduoja universalios aibės elementus į sveikų skaičių 0  m-1 aibę.
Pvz.: h(a)=a mod m, ji gera kai a yra tolygiai pasiskirstę. Vadinasi mums reikia h(a) pasirinkti pagal a pasiskirstymą. A(i) – nurodo į sarašo elementą a  S, kur h(a)=i. Tai operacijos ĮSTATYTI(a,s) atlikimui reikia paskaičiuoti h(a) ir po to peržiūrėti sąrašą, į kurį nurodo h A[h(a)]. Jei elem A ten nėra, tai jį reikia įstatyti sarašo gale. PAŠALINTI(a,s) atliekama analogiškai. Tas pats ir PRIKLAU-SYTI(a,s). Blogiausiu atveju gali atsitikti, kad atliekant operaciją ĮSTATYTI visoms h(a) gaunasi tas pats skaičius ir visi elementai tada rasis viename saraše. Tuo atveju, atliekant i-tają operaciją reikės laiko, proporcingo i. Ir atliekant įstatymu reikės (n2) laiko. Šiuo atveju tai yra tas pats kaip ir paprastas sarašas. Tačiau vidutinis laikas bus žymiai geresnis. Jei h(a) įgauna reikšmę su tikimybėmis 1/m ir įstatant nan. Vadinasi yra užduotos tikimybės q0,q1,…,qn. pi+qi1.Reikia sudaryti optimalų paieškos medį ,kuriame vidutiniškai būtų atliekama mažiausiai palyginimų, ieškant įvairų elementų su užduotomis tikimybės.
a4 0
a3 a5 1
a1 3 4 5 2
0 a2 3
1 2
Fiktyviai pažymime elemtus medyje ,kurių nėra bet tenka ieškoti. Tikimybė , kad reikės ieškoti a, kuris a3=nlog n, tai šis algoritmas iš tikrųjų yra optimalus, o kai mw (w=TĖVAS[v] ). Todėl kai grįžtama prie nutrūkusios procedūros paimama sekanti briauna, kuri gali vesti į naują viršūnę arba į seną. Tada 12 ir 13 operacijos pakuoreguoja APAT[v] reikšmę. Šita briauna taip pat patenka į steką. 12 op. pataikrina ar ši briauna patekusi į medį.10 op. tikrina ar APAT[w] >=VIRNR[v], jei ne tai 11 op. pakuoreguoja APAT[v]. Jei taip tai reiškia aptikta labiausiai susijusi komponentė, o iš steko išstumia briaunas įeinančias į ją (komponentę) ir taip pat išstumiama paskutinė.

Paieška į gylį orentuotame grafe
Naudojant paieškos į gylį grafuose algoritmą orentuotame grafe galima išskirti orentuotų medžių mišką, jei kiekvienam mazgui v suskaupsime sąrašą L[v], t.y. pasiekiame viršūnių v aibę per 1 žingsnį. PVZ
V1 V2
V3
V5 V4

V7 V8
V6
V1 V6
V2 V5 V7 V8
V4 V3
Išskirtas grafo miškas (medžių linijos ištisinės, kitos punktyrinės)
Paimam viršūnę v1. Iš jos pasiekiam v2. PIEŠKA(v2) iššaukia PIEŠKA(v3). Čia Stop, niekur negalim patekti. Grįžtam į v2 ir pereinam į v4. Vėl niekur negalim patekti. Grįžtam į v1. Čia iššaukiama PAIEŠKA(v5). Iš šios viršūnės niekur negalim patekti, todėl paimama sekanti “nauja” viršūnė v6 ir t.t. Gauasi du medžiai.
Tokio algoritmo darbo rezultate gauname 4 tipų lankus:
1. Medžio lankai, kurie paieškos metu veda į naujas viršūnes 2. Tiesioginiai lankai vedantieji nuo protėvių į tiesioginius palikuonis (jei (v,w) – tiesioginis lankas vw).

Stipriai susijusių dalių isškyrimas orentuotame grafe
Stipriai susijusios dalys orentuotame grafe, tai iš bet kurios viršūnės egzistuoja kelias į bet kurią kitą. Kiekvienai orentuoto grafo viršūnei skaičiuosime APATRYŠYS[v] MIN({v}U{w | kuri priklauso skersiniam arba atbuliniam lankui (v,w) }). Čia viršūnių numeracija pagal paišką į gylį, surandant medžius. Viršūnė v orentuoto grafo stipriai susijusios dalie šaknis bus tada, kai APATRYŠYS[v]v. Atliekant paiešką į gylį galima apskaičiuoti APATRYŠYS[V], o taip pat išskirti stipriai susijusias dalis, tam grafo viršūnės talpinamos į steką, kai apeinant grafą sutinkamos. Kiekvieną kartą, kai aptinkama stip. susijusios dalies šaknis, visos viršūnės iki šios šaknies išstumiamos iš steko ir jos yra stipriai susijusios dalies viršūnės. Modifikuotos proc. paaiškinimas: APATRYŠYS[v] skaičiuojamas 4,9 ir 11 eilutėje 4 operacijoje suteikiama pradinė reikšmė (viršūnės Nr.). 9op. Priskiriam APATRYŠYS[v]MIN(APATRYŠYS[v], APATRYŠYS[w] )-tai lankams įeinantiems į medį. 10 op. išaiškina ar nįeinantis į medį lankas (v,w) yra atbulinis ar skersinis, o tai pat išaiškinama ar w stekui ;priklauso stipriai susijusiai grafo daliai. 11 op. koreguojama reikšmė APATRYŠYS[v] MIN(VIRNR[w], APATRYŠYS[v] ). Šio algoritmo sudėtin-gumas yra (MAX(n,e)) – tiesinės, n-viršūnių sk. e-lankų sk.

Grafų susietumo matrica.
G(V,E) V-viršūnių aibė, E-lankų aibė.
Susietumo matrica: |0 1 1 0|
( C )  |0 0 0 0|
|0 1 0 0|
|1 1 0 0|
cij  {0, jei nėra lanko iš i į j 1,jei yra lankas i j
Susietumo matricų daugyba. Tegul turime grafus G1(V,E 1 ) ir G2 (V, E 2 ) su tom pačiom viršūnėm, bet skirtingais lankais. Sudauginsime jų susietumo matricas CC1*C2 . Susietumo matrica C atitinka multigrafas sudarytas taip: iš vi į vj eina tiek lankų, kiek yra kelių iš vi į vj , susidedančių iš 2 lankų: pirmas lankas G1 , antras G2. Įrodymas: ar egzistuoja vi į vj kelias vi vk vj per tarpinę viršūnę vk . Galima patikrinti tokiu būdu c1ik*c2kj1; c1ikG1 , o c2kjG2 . Keičiant k nuo 1 iki n patikrinam ar egzistuoja kelias per visas tarpines viršūnes. Sumuojant, gaunam tokių kelių sk. cijk1 n c1ik* c2kj. O tai atitinka matricų daugyba, cij yra matricos C elementai. Tegul C yra grafų susietumo matrica. Tada C*C elementai parodo kiek yra skirtingų kelių iš viršūnės vi į vj , susidedančių iš dviejų lankų.
|0110| |0110| |0100|
( C )*( C )  |0000| |0000|  |0000|
|0100| |0100| |0000|
|1100| |1100| |0110|
c121 rodo kelią v1 v3 v2 .
( C )( C )( C ) Parodo kiek kelių yra vj ir vi susidedančių iš 3 lankų.
|0100| |0110| |0000|
(C)(C)(C) |0000| |0000|  |0000|
|0000| |0100| |0000|
|0110| |1100| |0100|
1 rodo, kad tarp v4 ir v2 yra kelias susidedantis iš 3 laukų, tai v4 v1 v3 v2 . (C)4 rodytų kelių sk. susidedančių iš keturių lankų, čia nėra tokių kelių. Kai nėra ciklų, tai gauname nulinę matricą. (C)n – yra tikslas skaičiuoti iki (C). Toliau bus rodomi tik ciklai. Jei susumuosime visas (C)+(C)2+…+(C)n+
|10..0|
+ |01..0|

|00..1|
matricas, tai gausime kelių sk. iš vi į vj . Jei atitinkamas elemntas cij>0, tai tas rodo, kad yra kelias tarp viršūnių vi vj . Matricos (n*n) daugybai reikia atlikti n3 daugybos veiksmų. Matricai (C)n gauti, reikia ~n4daugybos veiksmų. Kartais keliamas uždavinys surasti ar egzistuoja kelias tarp visų grafo viršūnių. T.y. surasti matricą (L), kurios
lij{0, jei nėra kelio tarp vi ir vj 1, jei yra toks kelias.
Matom, kad toks uždavynys gali būti išspręstas dauginant ir sudedant matricas. Grafas atitinkantis susietumo matricą (L) vadinamas refleksiniu -tranzitiniu grafo uždarymu.
Paaiškinimas (L) matricos radimo algoritmo: Čia visada ckij1, jei yra daugiau kelių. Todėl 5 op. 1+11. T.y. atliekami veiksmai su 0 ir 1. Čia 5 op. atliekamas n3 kartų, nes kartu atliekamas sumavimas.
Trumpiausio kelio radimas
Min kelio tarp viršūnių radimo algoritmas:
begin
1. for i1 until n do c0ii0;
2. for 1 i,j n ir j do c0ijcij;
3. for k1 until n do
4. for 1 i, j n do
5. ckij MIN(ck-1ij , ck-1ik +ck-1kj);
6. for 1 i, j n do lijcnij
end
V2 1 ir 2 op. duos matricą Cij0
V1 2 | 2 8 5|
5 V3 (Cij) |3  |
| 2 |
| 0 8 5| k1 |0 8 5|
(C0 ij)| 3 0 8| (C1ij)|3 0 8|
| 2 0| | 2 0|
C112MIN(C012 , C011+C012)8
C123MIN(C023 , C021+C013)8 Įvertina mas kelias v2v1v3 per v1.
k2 |0 8 5| C231MIN(C131 ,C132+
(C2 ij)| 3 0 8| + C121)5
|5 2 0| Įvertinamas kelias v3v2v1 per v2.
k3 |0 7 5| C312MIN(C212 ,C213+
(C2 ij)| 3 0 8| + C232)7
|5 2 0| Įvertinamas kelias v1v3v2 ,
kuris trumpesnis negu tiesioginis v1v2.
Šio algoritmo sudėtingumas (n3),nes į op. atliekamas n3 kartų , o š op. n2 kartų. 1,2 op.taip pat n2 kartų.

Uždavinys su vienu šaltiniu ( Deiks-tros algoritmas)
Randami trumpiausi atstumai nuo vienos viršūnės iki kitų garfo viršūnių.
Grafas G=(V,E), pradinė viršūnė v0V. Duotos reikšmės l(vi ,vj ) ir l(vi ,vj )= +, jei nėra lanko vi vj . Sprendžiant šį uždavinį, sudaroma viršūnių aibė SV.Taip trumpiausias atstumas nuo v0 iki vS eina per viršūnes S.

V0 2 V1
7 3
10 6 V5
4
V4 5 V3

I_| S_ |w|D[w]|D[v1]|D[v2]|D[v3]|D[v4]
Pradţ.| {v0} | – | – | 2 | + | + | 10
1. |{v0,v1} | v1| 2 | 2 | 5 | + | 9
2. |{v0,v1,v2} | v2 | 5 | 2 | 5 | 9 | 9
3. |{v0,v1,v2,v3} | v3 | 9 | 2 | 5 | 9 | 9
4. |{v0,v1,v2,v3,v4}| v4 | 9 | 2 | 5 | 9 | 9

begin
1. S{v};
2. D[v]0;
3. for vV,kaiS={v}do D[v]l(v,v)
4. while SV do
begin
5. paimti viršūnę wV, nepriklausančią S, kuriai D[w]-mminimali (wV-S)
6. pridėti viršunę w prie aibės S;
7. for vV-S do
8. D[v]MIN(D[v];D[w]+l(w,v));
end;
end;
5 op. atliekamas n kartų (n-viršūnių ksaičius), 7,8 operatoriai atliekami n kartų (max). 4 op. wile ciklas įstato kiekivieną viršūnę į S. Todėl ciklas iš 4,5,6,7,8 operatorių atleikamas n2 kartų, todėl algoritmo sudėtingumas (n2) ( 3 operatorius atleikamas n kartų, todėl algoritmo sudėtingumui įtakos neturi ).

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

Оставить комментарий

avatar
  Подписаться  
Уведомление о
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2019