Pratybos
Penkios užduotys.
1. Suderink abi DFS versijas
Šeštas žingsnis parodė, kad iteracinė ir rekursinė DFS grąžina skirtingus kelius 552 iš 554 krypčių, nes viena apeina kaimynus atbulai.
Pataisyk iteracinę neliesdamas rekursinės: dėk kaimynus į steką atvirkštine tvarka, kad išimant jie eitų pirmine.
reversed-push DFS vs recursive: agree 554, differ 0
Visos 554. Paaiškink, kodėl tvarkos apvertimas yra būtent tiek pakeitimo, kiek reikia — ir kodėl tai nepaverčia DFS trumpiausių kelių ieškotoju. (Pamatuok: ar perėjimų skaičius nors kiek sumažėjo?)
Tada sunkesnis klausimas: TestTheTwoDFSVersionsDisagreeOnPaths dabar kris. Jį
ištrinti ar palikti abi versijas greta? Pagrįsk tuo, ką tas testas saugojo.
2. Sulaužyk BFS subtiliai
Trečias žingsnis sakė, kad BFS turi žymėti viršūnę dedant į eilę, ne imant. Padaryk atvirkščiai tyčia.
mark-on-pop BFS: 230 of 554 destinations wrong, worst overshoot 3 hops
Visas kryptis vis tiek randa. Klysta 41.5 % atvejų, ir niekada daugiau nei 3 perėjimais.
Būtent šis derinys ir yra esmė: jokio lūžimo, jokio prarasto atsakymo, jokios akivaizdžiai kvailos išvesties — tik keliai, tyliai truputį per ilgi. Paaiškink mechanizmą (ko eilėje atsiranda, ko neturėtų būti) ir pasakyk, kaip tokį dalyką išvis pastebėtum veikiančioje sistemoje, jei testo nebūtų.
Ir pamatuok dar vieną dalyką: kiek labiau išsipučia eilė?
3. BFS matricoje
Septintas žingsnis pamatavo atmintį ir pilną peržiūrą. Dabar pamatuok pačią paiešką.
Parašyk BFS, naudojančią AdjMatrix vietoj gretimumo sąrašo — kiekvienai
viršūnei ji turi patikrinti visus V langelius, kad rastų kaimynus.
Palygink prie n = 1 000 ir 10 000: peržiūrėtų briaunų skaičius ir laikas.
Patvirtink savo skaičiais, kad viena yra O(V + E), o kita O(V²).
Tada atsakyk: abi paieškos grąžina vienodus kelius. Ką tiksliai pakeitė reprezentacija ir ko nepakeitė?
4. Bibliotekos skersmuo
Skersmuo — ilgiausias iš visų trumpiausių kelių, tai yra dvi knygos, labiausiai nutolusios skolinimosi prasme.
Apskaičiuok jį paleisdamas BFS iš kiekvienos viršūnės. Kiek tai kainuoja V ir
E terminais?
Tada pasidomėk „dvigubo perėjimo" euristika: BFS iš bet kurios viršūnės randa
tolimiausią a, tada BFS iš a. Palygink jos atsakymą su tikruoju skersmeniu
savo grafe ir jos kainą.
Ar ji atsako teisingai? Ar visada? Parašyk, ką iš tikrųjų patikrinai, ir neteigk daugiau.
5. Ką reiškia sluoksnis
BFS lanko sluoksniais. Iš to plaukia daugiau, nei „per kiek perėjimų".
Panaudok sluoksnius nustatyti, ar grafe yra nelyginio ilgio ciklas: BFS metu nuspalvink kiekvieną viršūnę pagal jos sluoksnio lyginumą. Jei kuri nors briauna sujungia dvi vienodos spalvos viršūnes — toks ciklas yra.
Realizuok, paleisk bibliotekos tinkle ir pateik atsakymą.
Tada pasakyk, į kuriuos tris klausimus atsakytų ir paprasta DFS, o į kuriuos ne: „ar pasiekiama", „per kiek perėjimų", „ar yra nelyginis ciklas".