Rēzeknes Augstskola
Inženieru fakultāte
Datorzinātņu un matemātikas katedra
ALGORITMU TEORIJA
Referāts
Grafu algoritmi – dziļummeklēšana un plašummeklēšana, bināro koku apiešana
***************
RA Inženieru fakultātes
2. līmeņa profesionālās augstākās
izglītības bakalaura studiju programmas
“Programmēšanas inženieris”
pilna laika studiju 4.kursa studente
**************
…………………………………………
(paraksts)
Docētājs
lektors ************. ______________ *********
Rēzekne
2007
Attieksmju-grafu plašā pielietošana praktiski visās zinātnēs un inženierpielietojumos ir radījusi nepieciešamību sistematizēt un attīstīt to algoritmu teorijas daļu, kas apkalpo grafu teorijas uzdevumus. Šajā nodaļā mēs īsi apskatīsim plašāk pielietotos grafu uzdevumus un algoritmus to risināšanai.
PLAŠUMMEKLĒŠANA UN DZIĻUMMEKLĒŠANA
Bieži risinot teorētiskus vai praktiskus uzdevumus, ir nepieciešams apiet (pārmeklēt, pārlasīt, iezīmēt) grafa virsotnes noteiktā, algoritmiskā kārtībā, izmantojot grafa šķautnes. Ir skaidrs, ka algoritms ir vajadzīgs, lai apiešanu varētu realizēt ar datora palīdzību. Šāda algoritma efektivitātes dēļ ir lietderīgi minimizēt katras virsotnes iezīmēšanas reižu skaitu, piemēram, pieprasīt, ka katra virsotne tiek iezīmēta ne vairāk kā vienu reizi. Kāda varētu būt grafu virsotņu apiešanas dabiska kārtība? Šo uzdevumu var viegli atrisināt, ja grafs ir, piemēram, ķēde vai cikls, tad ir skaidrs, kā tas ir jāapiet:
1.att. – ķēdes un cikla apiešanas veidi.
Ko darīt patvaļīga sakarīga grafa gadījumā? Ir vismaz divi dabiski grafu apiešanas veidi – plašummeklēšana un dziļummeklēšana. Abos algoritmos tiek pakāpeniski konstruēts orientēts koks, kuram atbilstošais neorientētais koks ir dotā grafa skelets.
Plašuma meklēšana (pārlase plašumā, breadth-first search): sākam ar fiksētu virsotni , atzīmējam visas ar to saistītās virsotnes , pilnīgi sakārtojam tās veidā , konstruējam sakārtotu koku :
2.att. – pirmais solis plašuma meklēšanas algoritmā.
Nākošajā solī konstruējam sakārtotu koku šādā veidā: apejam pilnīgi sakārtoto virkni tās pieaugošajā kārtībā un katrai virsotnei atzīmējam un piekārtojam kā dēlu kopu visas virsotnes , kas ir saistītas ar un vēl nav atzīmētas:
3.att. – pirmie divi soļi plašuma meklēšanas algoritmā.
Turpinām šo procesu konstruējot sakārtotu koku virkni , kuras pēdējais loceklis tiek saukts par plašuma meklēšanas koku. Atzīmēsim, ka šis koks nav noteikts viennozīmīgi, tas ir atkarīgs no tā pirmās virsotnes un no katras iekšējās virsotnes dēlu sakārtojumu.
Novērtēsim operāciju skaitu, kas ir nepieciešams plašuma meklēšanai. Pieņemsim, ka ir dots grafs ar V virsotnēm un E šķautnēm, kas ir uzdots ar saistības sarakstu. Plašuma meklēšanas procesā katra virsotne tiek ievietota kokā vienu reizi, tātad summārais operāciju skaits ir . Katras virsotnes saistības saraksts tiek apskatīts vienu reizi, tātad summārais operāciju skaits šajā algoritma daļā ir . Papildus operāciju skaits grafa inicializācijai ir . Var redzēt, ka kopējais algoritma darba laiks ir .
Izmantojot plašummeklēšanu var atrisināt šādus uzdevumus:
a) noteikt, vai grafs ir saistīts un atrast grafa komponenšu skaitu – to var izdarīt, veicot meklēšanu plašumā no jebkuras virsotnes, grafs ir saistīts tad un tikai tad, ja tiek apietas visas grafa virsotnes, komponenšu skaits ir vienāds ar nepieciešamo meklēšanu skaitu, kas ir nepieciešamas, lai apietu visas virsotnes,
b) noteikt attālumu starp divām virsotnēm – to var izdarīt veicot meklēšana no vienas virsotnes, attālums starp virsotnēm ir vienāds ar attālumu no sākotnējās virsotnes līdz otrai virsotnei meklēšanas kokā,
c) nokrāsot grafa virsotnes divās krāsās, ja ir zināms, ka tas ir divdaļīgs.
Vēl viens efektīvs plašuma meklēšanas pielietošanas piemērs ir saistīts ar izklaidējošo matemātiku. Viens no pēdējo gadu aizraujošākajiem notikumiem matemātikā ir tā saucamās „Eternity Puzzle” spēles atrisināšana. 1999. gadā kāda britu rotaļlietu firma laida pārdošanā spēli, kuras uzdevums ir noteiktā veidā savietot 209 plakanas figūras. Par šī uzdevuma atrisināšanu gada laikā pirmā iesūtītā risinājuma autoram tika garantēta vienu miljonu britu mārciņu liela balva. Uzdevuma autori bija nepareizi novērtējuši šī uzdevuma grūtības pakāpi un acīmredzot bija pārliecināti, ka uzdevumu nav iespējams atrisināt gada laikā pat izmantojot jaudīgus datorus. Tas tomēr tika atrisināts septiņu mēnešu laikā veicot meklēšanu ar divu personālo datoru palīdzību un konkursa organizētājiem nācās izmaksāt apsolīto summu. Spriežot pēc risinājuma autoru publikācijām, uzdevums tika modelēts izmantojot grafus un meklēšana pamatojās uz bektrekingu, plašuma meklēšanas algoritmu un diskrēto varbūtību teoriju, kas tika izmantota nākošā elementa optimālai izvēlei. Pirmie uzdevumu atrisināja divi profesionāli matemātiķi.
Otrs grafu teorijā un grafu pielietojumos populārs meklēšanas veids ir dziļuma meklēšana (pārlase dziļumā, depth-first search): sākam ar fiksētu virsotni kā topošā meklēšanas koka sakni, atzīmējam jebkuru vēl neatzīmētu virsotni , meklēšanas kokā zīmējam šķautni un pārvietojamies uz virsotni , vispārīgā gadījumā rīkojamies šādi: ja mēs atrodamies virsotnē un eksistē vēl neatzīmēta virsotne , kas ir saistīta ar , tad 1) atzīmējam virsotni , 2) meklēšanas kokā zīmējam šķautni un 3) pārvietojamies uz virsotni , pretējā gadījumā (ja visas virsotnes, kas ir saistītas ar , jau ir atzīmētas) pārejam (atkāpjamies) uz virsotnes tēvu, turpinām šo algoritmu tik ilgi, kamēr atgriežamies atpakaļ virsotnē . Rezultātā iegūsim dziļuma meklēšana koku. Bieži vien ir lietderīgi papildus atzīmēt arī „atkāpšanās” šķautnes.
4.att. – dziļuma meklēšanas algoritma realizācijas piemērs.
Orientētiem grafiem var izmantot abas meklēšanas metodes ar to divām atšķirībām: 1) virzīšanās pa šķautni ir atļauta tikai tās norādītajā virzienā un 2) dziļuma meklēšana var tikt veikta vairākas reizes, kamēr tiek atzīmētas visas virsotnes.
Var pierādīt, ka dziļuma meklēšanas algoritma darba laiks ir , kur V ir grafa virsotņu skaits un E ir grafa šķautņu skaits.
Viens no neacīmredzamiem dziļuma meklēšanas pielietojumiem ir šarnīru noteikšana patērējot mazāk laika nekā tas ir iespējams ar kādu no naivajām metodēm.
Dziļuma meklēšanu tāpat kā plašuma meklēšanu pielieto grafa komponenšu un stipri sakarīgo komponenšu noteikšanā, metrisko invariantu (diametra, ekscentritātes, centra) noteikšanā, divdaļīga grafa sadalīšana daļās. Dziļuma meklēšanu pielieto arī algoritmos, kuros tiek risināti uzdevumi par augstāku kārtu sakarīgumu (šarnīru un bloki noteikšana, fiksētas kārtas sakarīgo komponenšu noteikšana) un planaritāti
BINĀRO KOKU ALGORITMI
Binārie koki ir tā grafu klase, kas relatīvi visbiežāk tiek izmantota pielietojumos un praktiskajā programmēšanā. Šajā nodaļā apskatīsim vienkāršākos bināro koku algoritmus un bināro koku pielietojumus.
Bināru koku virsotņu apiešanai var izmantot plašuma meklēšanu vai dziļuma meklēšanu tāpat kā vispārīgiem grafiem. Bieži vien ērtāk ir izmantot koku struktūras specifiku un apiet koka virsotnes citos veidos. Apskatīsim populārākos no tiem – preorder, postoder un inorder apiešanu.
Ja ir dots binārs koks , tad apzīmēsim ar tā sakni (domātu kā bināru koku ar vienu virsotni), ar tā kreisā dēla apakškoku un ar tā labā dēla apakškoku. Definēsim virsotņu virkni (virsotņu apiešanas kārtību) šādā rekursīvā veidā:
.
Citiem vārdiem sakot, no sākuma tiek apieta koka virsotne, pēc tam rekursīvā veidā kreisais un labais zars. Līdzīgi definē vēl divus apiešanas veidus un :
,
.
Papildus tam definēsim
,
ja satur vienu virsotni.
Zīmējumā ir parādīti trīs bināru koku apiešanas veidi vienam kokam:
5.att. – trīs bināra koka apiešanas veidi.
Šie koku virsotņu apiešanas veidi no programmēšanas viedokļa ir vieglāk realizējami nekā meklēšana plašumā un dziļumā. Tie arī ir dabiskāki darbā ar kokiem nekā vispārīgie meklēšanas veidi.
Apskatīsim divus bināros kokus pielietošanas gadījumus – šķirošanas un meklēšanas uzdevumos. Viens no „ātrajiem” ( ) šķirošanas algoritmiem ir tā saucamais „heapsort” algoritms. Šis algoritms sastāv no diviem soļiem. Pirmajā solī nesakārtotā virkne tiek pārveidota noteikta bināra koka – hīpa (heap) veidā. Hīps ir binārs koks ar virsotnēm piekārtotiem skaitliskiem indeksiem, kurā katras virsotnes indekss nav mazākas par tās dēlu indeksiem. Ja ir dota nesakārtota virkne, tad hīpu var konstruēt šādā veidā: pēctecīgi ņemam ārā no virknes elementus un definējam tās kā nākamās lapas kokā, ja tiek pārkāpts hīpa nosacījums, tad virsotnes tiek pārvietotas uz augšu, mainot virsotni vietām ar savu tēvu, tik ilgi, kamēr ir tiek apmierināts hīpa nosacījums. Otrajā algoritma solī hīps tiek pārveidots par sakārtotu virkni šādā veidā: pēctecīgi no hīpa izņem saknes, ievieto tās kā nākamos elementus sašķirotajā virknē un pārvieto nākamo lapu uz augšu līdz sakne mainot to vietā ar tās tēvu, kamēr nav apmierināt hīpa nosacījums, šo procedūru atkārto tik ilgi, kamēr hīps nav tukšs.
Populārs meklēšanas algoritms ir binārā koka meklēšanas algoritms. Šis algoritms tāpat kā hīpsorta algoritms arī sastāv no diviem soļiem: pirmajā solī kopa, kurā tiks veikta meklēšanas, tiek pārveidota noteikta bināra koka (meklēšanas koka) veidā, otrajā solī meklējamais objekts tiek meklēts binārajā kokā saskaņā ar noteiktu algoritmu. Par binārās meklēšanas koku sauksim bināru koku ar virsotnēm piekārtotiem skaitliskiem indeksiem, kurā katras virsotnes indekss nav mazākas par tās kreisā apakškoka virsotņu indeksiem un nav lielāks par tās labā apakškoka virsotņu indeksiem. Ja ir dots binārās meklēšanas koka, tad elementa meklēšanu var veikt salīdzinot meklējamo elementu no sākuma ar sakni un tālāk virzoties uz leju atkarībā no salīdzināšanas rezultātiem. Ja ir dots nesakārtots masīvs, tad no tā var inkrementāli izveidot binārās meklēšanas koku šādā veidā: kārtējais elements no masīva tiek meklēts jau konstruētajā kokā un pievienots kā lapa tajā vietā, kur tam ir jābūt, lai pēc pievienošanas atkal izveidotos binārās meklēšanas koks.