Grafo paieškos gilyn algoritmas

Programavimo technologijų praktika Laboratorinis darbas Nr. 2 Grafo paieškos gilyn algoritmas Atliko: IT -4 grupės studentas ...................................................... ŠIAULIAI, 2006 Užduotis Grafo paieškos gilyn algoritmas Aprašyme naudojamų sutrumpinimų sąrašas Sutrumpinimas Paaiškinimas Pav. paveikslėlis Pagr. Pagrindinis Sk. Skaičius Virš. Viršūnė I Įvadas 1. Užduotis Grafo paieškos gilyn algoritmas 2. Algoritmo tikslas Rasti kurioje iš grafo viršūnių yra duomenų lentelėje pateiktas skaičius 6. II Užduoties analizė 1. Matematinė analizė Duota: grafas G =(V, U) kur V – viršūnių skaičius, U – briaunų aibė Rasti: kurioje iš grafo viršūnių yra duomenų lentelėje pateiktas skaičius 6. Paieška į gylį - grafo paieškos būdas, kurio pagr. principas - pasirenkama pradinė viršūnė ir einama grafu kiek įmanoma giliau, tada grįžtama iki artimiausios neaplankytos viršūnės ir vėl ieškoma kuo giliau. T.y. pradžioje grafo viršūnės yra naujos (neaplankytos). Paieška gilyn iš 1-osios viršūnės: Paieškos gilyn metu pirmiausia einame iš 1-os viršūnės į 2-ąją. Kadangi 2-oji viršūnė yra nauja, t.y. neaplankyta tai toliau peržiūrą tęsiame iš 2-os viršūnės. (1-oji ir 2-oji viršūnės tampa aplankytomis). Iš 2-osios viršūnės einame į 1-ąją. Kadangi 1-oji viršūnė jau aplankyta, tai einame į kitą gretimą 2-ajai viršūnei 3-iąją viršūnę. 3-ioji viršūnė yra nauja t.y. neaplankyta, todėl ją aplankome ir peržiūrą tęsiame iš 3-iosios viršūnės. Iš 3-iosios viršūnės einame į pirmąją jai gretimą viršūnę, t.y. į 2-ąją. Ši viršūnė yra nenauja, t.y. jau buvo aplankyta, todėl einame į kitą 3-iajai viršūnei gretimą 4-tąją viršūnę. Matome, kad 4-oji viršūnė yra nauja, todėl peržiūrą tęsiame iš 4-os viršūnės. Iš 4-os viršūnės einame į 3-iąją, tačiau ši viršūnė jau aplankyta, todėl einame į kitą 4-ajai viršūnei gretimą 6-ąją viršūnę. 6-oji viršūnė yra nauja. Todėl peržiūrą tęsiame iš 6-os viršūnės. Iš 6-osios viršūnės po bandymų keliauti į 1-ąją ir 4-tąją viršūnes, ateisime į 5-tąją viršūnę.Kuri yra nauja ir peržiūrą tęsiame iš 5-osios viršūnės. Kadangi 5-os viršūnės visos gretimos viršūnės yra nenaujos, t.y. aplankytos, tai 5-oji viršūnė yra išsemta. Todėl paiešką bandome tęsti iš 6-osios viršūnės, nes į 5-tąją viršūnę atėjome iš 6-osios. 6-osios viršūnės visos gretimos viršūnės yra nenaujos, todėl 6-oji viršūnė yra išsemta ir paiešką tęsiame iš 4-os viršūnės. Matome, kad 4-oje viršūnėje yra dar neaplankyta 7-oji viršūnė, kurioje ir yra mūsų ieškomas skaičius 6. Pastaba: Ištisinėmis linijomis pavaizduotos briaunos (su nurodyta apėjimo kryptimi), kurios veda į naujas viršūnes, o punktyrais pažymėtos briaunos, kurios paieškos gilyn metu vedė į aplankytas (nenaujas) viršūnes. 2. Charakteristikos Įvestis: • įvedame grafo viršūnes • viršūnių semantiniai duomenys • briaunų matrica Išvestis: • nurodyta grafo viršūnė, ieškomo sk. vieta viršūnėje, ieškomas sk. Tarpiniai rezultatai: • bet kokiai viršūnei gretimos viršūnės gretimumo struktūroje išdėstytos jų numerių didėjimo tvarka • briaunų gretimumo matrica 1. Per kiek viršūnių reikia pereiti, norint rasti reikalingą skaičių? 2. Kiek užteko aplankyti viršūnių, norint patekti į 4-tąją viršūnę? 3. Kokie yra duomenys viršūnei? 2 pavyzdys: a) pav. pavaizduoto grafo viršūnės, jei paieška pradedama iš viršūnės , o bet kokiai viršūnei gretimos viršūnės gretimumo struktūroje išdėstytos jų numerių didėjimo tvarka: 1: 2, 3 2: 1, 3, 4, 5 3: 1, 2, 5 4: 2, 5 5: 2, 3, 4 Paieška gilyn iš 1-osios viršūnės: Paieškos gilyn metu pirmiausia iš 1-osios viršūnės einame į 2-ąją viršūnę. Kadangi 2-oji viršūnė yra nauja, tai toliau peržiūrą tęsiame iš 2-osios viršūnės. (Pirmoji ir antroji viršūnės tampa aplankytomis). Iš 2-osios viršūnės pirmiausia einame į 1-ąją viršūnę. Kadangi pirmoji viršūnė nenauja (aplankyta), tai iš 2-osios viršūnės bandome eiti į kitą jai gretimą 3-iąją viršūnę. Trečioji viršūnė nauja, todėl ją aplankome ir peržiūrą tęsiame iš 3-osios viršūnės. Iš 3-iosios viršūnės bandome eiti į pirmąją jai gretimą viršūnę, – į 1-ąją viršūnę. Ši viršūnė nenauja. Tada bandome eiti į kitą 3-ajai viršūnei gretimą 2-ąją viršūnę. Ši viršūnė taip pat aplankyta, todėl bandome eiti į paskutiniąją 3-iajai viršūnei gretimą 5-ąją viršūnę. Ši viršūnė yra nauja, todėl peržiūrą dabar tęsime iš 5-osios viršūnės. Iš 5-osios viršūnės, po bandymų keliauti į 2-ąją ir 3-iąją viršūnes, ateisime į 4-ąją viršūnę. Kadangi 4-osios viršūnės visos gretimos viršūnės nėra naujos, tai 4-oji viršūnė išsemta. Paiešką bandome tęsti iš 5-osios viršūnės, nes į 4-ąją viršūnę atėjome iš 5-osios viršūnės. 5-ąjąi viršūnei visos gretimos viršūnės yra nenaujos, todėl 5-oji viršūnė yra išsemta ir paiešką bandome tęsti iš 3-iosios viršūnės. 3-ioji viršūnė taip pat išsemta, todėl paiešką tęsime iš 2-osios viršūnės, nes į 3-iąją viršūnę atėjome iš 2-osios viršūnės. 2-ąjai viršūnei dar nenagrinėta gretima yra 5-toji viršūnė. Tačiau ši viršūnė nenauja, todėl 2-oji viršūnė tampa išsemta ir paiešką tęsiame iš 1-osios viršūnės. Iš 1-osios viršūnės bandome eiti į 3-iąją, tačiau ji jau aplankyta. Tuo būdu ir 1-oji viršūnė tampa išsemta, o tai yra paieškos gilyn algoritmo pabaiga. Pastaba: a) pav. romėniškais skaitmenimis pažymėti briaunų apėjimo eilės numeriai. b) pav. ištisinėmis linijomis pavaizduotos briaunos (su nurodyta apėjimo kryptimi), kurios veda į naujas viršūnes, o punktyrais pažymėtos briaunos, kurios paieškos gilyn metu vedė į aplankytas (nenaujas) viršūnes. III Užduoties sprendimo metodas 1. Algoritmo realizacijai reikalingos techninės ir programinės priemonės Borland C++ Builder 2. Duomenų struktūros Duomenys Duomenų struktūra Paskirtis Viršūnės Vienmatis masyvas Įvedamos grafo viršūnės Ryšiai Vienmačiai masyvai Apibrėžia sąveikas tarp viršūnių Duomenys Vienmatis masyvas Viršūnių duomenims įtalpinti 3. Blokinė algoritmo schema (su komentarais) NE TAIP TAIP NE TAIP NE 4. Blokinė vykdymo paieškos algoritmo schema NE TAIP TAIP NE TAIP NE NE TAIP NE TAIP 5. Duomenų įvesties apribojimai Duomenų laukas Duomenų tipas Apribojimas Viršūnių sk. Sveikas sk. 0 >= sk. = sk. = sk.

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!