|
1. Algoritmlerdi proektlestiriwge kirisiw
|
| bet | 6/11 | | Sana | 09.06.2024 | | Hajmi | 1,23 Mb. | | #261899 |
Bog'liq Algoritmlerdi proektlestiriw JB sorawlaralgorithm Kruskal(G) is
F:= ∅
for each v in G.V do
MAKE-SET(v)
for each {u, v} in G.E ordered by weight({u, v}), increasing do
if FIND-SET(u) ≠ FIND-SET(v) then
F := F ∪ { {u, v} }
UNION(FIND-SET(u), FIND-SET(v))
return F
E shetleri hám v noqatları bolǵan graf ushın Kruskalning algoritmi O ((E log E) waqıt ishinde, ápiwayı maǵlıwmatlar strukturaları menen isleydi. Bul jerde O, waqtın úlken O notatsiyasida ańlatadı hám log hár qanday tıykarǵa logaritm bolıp tabıladı (sebebi O-notatsiyadagi barlıq tiykarlarǵa logaritmlar ekvivalent bolıp tabıladı, sebebi olar turaqlı kópaytuvchigacha birdey) Bul waqıt shegarası kóbinese O ((E log v) retinde jazıladı, bul bólek shıńları bolmaǵan grafikalar ushın ekvivalent bolıp tabıladı, sebebi bul grafikalar ushın v / 2 ≤ E < v2 hám v hám E logaritmlari taǵı bir-biriniń turaqlı kópaytuvchisi ishinde Bul sheklengen erisiw ushın, birinshi O ((E log E) waqıt salıstırıwlaw saralaw járdeminde salmaǵı boyınsha shetlerin saralaw Túrli bolǵanınan keyin, ol hár bir qır ushın turaqlı jáneqt tártibinde qırlar arqalı sheńber múmkin Keyingi, disjoint-jıynaq maǵlıwmatlar dúzilisi paydalanıw, hár bir komponent ushın vertices bir kompleksi menen, qaysı vertices qaysı komponentler boladı izlep Bul strukturanı jaratıw, hár bir noqat ushın bólek jıynaq menen, v operatsiyalar hám O ((v) waqtın aladı Barlıq qırlar arqalı aqırǵı iteratsiya eki tabıw operatsiyaların hám itimal bir birlik operatsiyaların hár qır atqaradı Bul operatsiyalar amortizatsiya etilgen waqtın aladı O ((α ((v)) hár bir operatsiya ushın waqıt, bul shınjır ushın eń jaman jaǵday daǵı ulıwma waqtın O ((E α ((v)) beredi, bul erda α júdá aste ósip atırǵan invert Ackermann funkciyası bolıp tabıladı waqıt menen baylanıslı bolǵan bul bólim saralaw basqıshı ushın waqıttan talay kishi, sol sebepli algoritm ushın ulıwma waqıt saralaw basqıshı ushın waqıtqa ápiwayılashtirilishi múmkin Shegaralar qashannan berli saralap qoyılǵan yamasa olar tolıq sanlardı saralaw algoritmlerin, mısalı, esaplawdı saralaw yamasa radixni saralaw arqalı sızıqlǵ waqıt ishinde saralawǵa múmkinshilik beretuǵın dárejede kishi bolǵan jaǵdaylarda, disjoint jıynaq operatsiyaları algoritmdiń eń aste qalǵan bólegi bolıp tabıladı hám ulıwma waqıt O ((E α ((v)).
53. Prima algoritmi.
Prim algoritmi n ta uchi hám m qırı bolǵan salmaqlıqtaǵı yo'naltirilmagan G graf berilgen. Bul grafikdıń barlıq úshlerin baylanıstıratuǵın hám usınıń menen birge eń kishi vaznga (yaǵnıy qır salmaqlarınıń jıyındısı ) iye bolǵan tómengi terekin tabıw talap etiledi. Tómengi terek - bul barlıq shıńlardı baylanıstıratuǵın qırlardıń kompleksi hám qálegen úshten basqasına anıq bir ápiwayı jol menen kiriwińiz múmkin. Bunday terek minimal keńliktegi terek yamasa ápiwayıǵana minimal keńliktegi terek dep ataladı. Hár qanday grafda n-1 qırları bolıwın túsiniw ańsat.Tábiyiy sharayatta bul mashqala tómendegishe kórinedi: n ta qala bar hám hár bir juplıq ushın olardı jol menen jalǵaw bahası málim (yamasa olardı baylanıstırıp bolmawi málim). Barlıq qalalardı sonday bólew talap etilediki, qálegen qaladan basqasına barıw múmkin boladı hám usınıń menen birge jol jatqızıw ǵárejetleri minimal boladı. Prim algoritmi 1957 jılda bul algoritmdi jańalıq ashqan amerikalıq matematikalıq Robert Prim húrmetine atalǵan. Biraq, 1930 jılda bul algoritmdi chex matematigi voytex Yarnik jańalıq ashqan. Bunnan tısqarı, Edsger Dijkstra da 1959 jılda olardan ǵárezsiz túrde bul algoritmdi oylap tabıw etken.Algoritmdiń ózi júdá ápiwayı. Kerekli minimal skelet, bir waqtıniń ózinde qırlardı qosıp, az-azdan qurıladı. Daslep, skelet bir vertexdan ibarat dep shama etiledi (ol qálegen tańlanıwı múmkin). Keyin, bul úshten shıǵıs minimal salmaqlıq qırı saylanadı hám minimal aralıq terekke qosıladı. Sonnan keyin, skelet qashannan berli eki shıńnı óz ishine aladı hám endi minimal salmaqlıqtıń shetsi qıdırıladı hám qosıladı, bir uchi saylanǵan eki shıńdan birinde, ekinshisi bolsa kerisinshe, bul ekinen tısqarı qalǵanlarında. hám taǵı basqa, yaǵnıy. hár sapar minimal salmaqlıq qırı qıdırıladı, onıń bir uchi qashannan berli skeletga alınǵan uch bolıp tabıladı, ekinshi uchi bolsa ele alınbaǵan jáne bul shet skeletga qosıladı (eger bir neshe bunday qırlar bolsa, siz qálegenin alın ). Bul process keńeytpe tereki barlıq úshlerin (yamasa ekvivalenti, n-1 qırların ) óz ishine olguncha tákirarlanadı. Nátiyjede, minimal bolǵan skelet qurıladı. Eger grafik daslep jalǵanbaǵan bolsa, ol halda hesh qanday keńeytpeli terek tabilǵan zatydı (saylanǵan qırlardıń sanı n-1 den kem bolıp qaladı.Algoritmdiń islew waqtı, tiykarınan, uyqas qırlar arasından keyingi minimal qırdı qanday izlewimizge baylanıslı. Hár qıylı asimptotiklarga hám hár qıylı qosımshalarǵa alıp keletuǵın túrli jantasıwlar bolıwı múmkin. ámelge asırıw : O (nm) hám O (n2 + m log n) algoritmleri. Eger hár sapar biz barlıq múmkin bolǵan variantlardı kóriw arqalı qır izlasak, ol jaǵdayda barlıq múmkin bolǵanlar arasında eń kishi salmaqlıqtaǵı qırdı tabıw ushın asimptotik túrde O (m) qırlardı kóriw kerek boladı. Bul halda algoritmdiń ulıwma asimptotikasi O (nm) boladı, bul eń jaman jaǵdayda O (n^3) boladı, bul júdá aste algoritm bolıp tabıladı. Bul algoritmdi jaqsılaw múmkin, eger hár sapar barlıq qırlar emes, bálki saylanǵan hár bir úshten tek bir qır tekserilse. Bunı ámelge asırıw ushın, mısalı, hár bir úshten qırlardı salmaqlardıń ósiw tártibinde saralawıńız hám kórsetkishni birinshi ruxsat etilgen shetine saqlawıńız múmkin (este tuting, tek ele tańlanbaǵan úshler kompleksine alıp keletuǵın qırlarǵa ruxsat beriledi). Keyin, eger skeletga hár sapar qır qosılǵanda bul kórsetkishlerdi qayta esaplab shıqsak, algoritmdiń ulıwma asimptotikasi O (n2 + m) boladı, lekin aldın O (m ) dagi barlıq qırlardı tártiplew kerek boladı. log n), bul eń jaman jaǵdayda (tıǵız graf ushın ) O (n2 log n) asimptotikani beredi.
54. Ostov teregi haqqında.
Graf astında cikller bolmawinan, ol eń arzan (eń kem ǵárejetli) terek bolıp, onıń basqasha atı ostov teregi dep júritiledi. Grafning Ostov tereki (ingl.) Spanning tree) - bul baslanǵısh grafning shıńları sanına teń bolǵan bul grafning subgrafi tereki Nadurıstan -tuwrı aytqanda, túbir tereki baslanǵısh grafdan maksimal sandaǵı buwınlardı alıp taslaw arqalı payda etinadi, lekin grafning baylanıslılıǵın buzmasdan Ostov tereki baslanǵısh grafning barlıq n shıńların óz ishine aladı hám n − 1 qirg'og'ini óz ishine aladı
Ostov tereki - bul baylanıslı yo'naltirilmagan grafning barlıq shıńları óz ishine alatuǵın asiklik baylanıslı subgrafi Ósimlik tereki túsinigi hár túrlı, onıń astında tómendegi subgraflardan birin túsiniw múmkin: qananıń barlıq shıńların óz ishine alǵan, lekin ulıwma baylanıslı bolmaǵan hár qanday hákisiklik subgraf; baylanıslı bolmaǵan grafda - onıń hár bir baylanıslılıq komponenti ushın ósimlik terekleriniń birlespesinen ibarat subgraf Ostov terekti geyde qatlam terek, Ostov yamasa graf skeleti dep da ataydılar «o'stnoy» sózinde túrli avtorlardıń zarbasi birinshi (o'st sózinen) yamasa ekinshi birikpege kórsetiledi
55. Ostov teregin qurıw usılları.
Kruskal algoritmi yo'naltirilmagan shetleri salmaqlıqtaǵı grafning minimal orman daǵı ormanın tabadı Eger grafik baylanısqan bolsa, ol minimal terekti tabadı Bul ashkóz algoritm bolıp, hár bir basqıshda ormanǵa eń kem salmaqlıqtaǵı chetni qosadı, bul bolsa cikl payda etmeydi. Algoritmdiń tiykarǵı qádemleri - tártiplew hám cikllerdi anıqlaw ushın disjoint-set maǵlıwmatlar strukturasınan paydalanıw Onıń jumıs waqtı olardıń salmaǵı boyınsha barlıq graf shetlerin saralaw ushın waqıt tárepinen basqarıladı Baylanısqan vaznli grafning minimal úzilis tereki - bul cikllersiz baylanısqan subgraf bolıp, onıń subgrafdagi barlıq qırlar salmaqlarınıń jıyındısı minimal boladı Bir-birine baylanıspaǵan grafik ushın minimal oralǵan orman hár bir baylanısqan komponent ushın minimal oralǵan terekten ibarat Bul algoritm birinshi ret Jozef Kruskal tárepinen 1956 jılda baspa etilgen hám tez arada Loberman & Weinberger tárepinen qayta jańalıq ashılǵan (1957). Bul mashqala ushın basqa algoritmlerge Prim algoritmi, Barovka algoritmi hám teris óshiriw algoritmi kiredi.
Prim algoritmi Algoritm ideyası. Graf ushlariniń qálegeni saylanadı. Keyin bul ushtan shiqqan barlıq qırlardan eń arzan bahalisi saylanadı. Solay etip eki ushlı bir qırlı terekti payda etemiz. Sodan keyin bir ushi usi terekke tiyisli bolǵan barlıq qırlardan eń arzan bahalisi saylanadı. Bul qır yamasa qırlar, eger eń arzan bahalisi bir neshe bolsa, terekke qosıladı. Qırlardı qosıw procesi bunday qosıwlar cikl payda etilgenshe dawam etedi. Bunday terek qurıw procesi áste aqırın grafti barlıq ushlarin óz ishine aladı
56. Sıqmar algoritmin túsindirip beriń
Bizge baylanısqan, jóneltirilmegen graf berilgen bolıp, onıń qırları málim salmaqlarǵa iye bolsın. Salmaqlar - bul sonday sanlar bolıp, olar berilgen qırlardıń shetki ushlari arasındaǵı aralıǵın ańlatadı, bul qır boylap háreketlaniwde transport ǵárejetlerin yamasa basqa ǵárejetlerdi ańlatadı. “Sıqmar algoritmler” atı menen birlestirilgen algoritmler graftiń sonday A hám D ushlari arasındaǵı marshrutni (jónelisti) tabıwǵa qaratılǵan bolıp, ol eń arzan (eń kem ǵárejetli) bolıwı kerek. Rasındada, bunday máselelerdi sheshiwde biz aldın A hám D ushlari arasındaǵı barlıq múmkin bolǵan jónelislerdi anıqlap, sonnan keyin bul jónelislerdi eń kem ǵárejetliligini tańlaymiz.
Sıqmar algoritmi - bul hár bir basqıshda jergilikli maqul túsetuǵın qararlar qabıllawdan ibarat bolǵan juwmaqlawshı sheshimi de maqul túsetuǵın dep shama etilgen algoritm bolıp tabıladı Eger mashqalanıń dúzilisi <> tárepinen ornatılsa, ashkóz algoritmnen paydalanıw global maqul túsetuǵınlıqqa alıp keliwi málim Sıqmar algoritmlerdi <>, sonıń menen birge, <> retinde xarakteristikalaw múmkin Olar tek " maqul túsetuǵın tómengi dúzılıwga" iye bolǵan máseleler ushın ideal bolıp tabıladı Soǵan qaramay, kóplegen ápiwayı máseleler ushın eń jaqsı sáykes keletuǵın algoritmler ashkóz algoritmler bolıp tabıladı Sonısı itibarǵa ılayıqki, ashkóz algoritmdi tańlaw algoritmi retinde qıdırıw yamasa tarmaq menen baylanısqan algoritmdiń ústin turatuǵınlıqların belgilew ushın paydalanıw múmkin Ashkóz algoritm ushın bir neshe ózgerisler ámeldegi: Sıqmar algoritmlerdi <>, sonıń menen birge, <> retinde xarakteristikalaw múmkin Olar tek " maqul túsetuǵın tómengi dúzılıwga" iye bolǵan máseleler ushın ideal bolıp tabıladı Soǵan qaramay, kóplegen ápiwayı máseleler ushın eń jaqsı sáykes keletuǵın algoritmler ashkóz algoritmler bolıp tabıladı Sonısı itibarǵa ılayıqki, ashkóz algoritmdi tańlaw algoritmi retinde qıdırıw yamasa tarmaq menen baylanısqan algoritmdiń ústin turatuǵınlıqların belgilew ushın paydalanıw múmkin Ashkóz algoritm ushın bir neshe ózgerisler ámeldegi: Sap ashkóz algoritmler Ortogonal ashkóz algoritmler Tınıshlantıratuǵın ashkóz algoritmler
57. Prim algoritmin túsindirip beriń
|
| |
