Pratybos
Penkios užduotys. Paskutinės kurse.
1. Dvikryptė paieška
A* pralaimėjo, nes jo euristika buvo akla. Štai būdas nukirsti šakas visai be euristikos: paleisti dvi paieškas — vieną pirmyn iš pradžios, kitą atgal iš tikslo — ir sustoti, kai jos susitinka.
Realizuok. Tada atsakyk į tai, ant ko dažniausiai užkliūvama: susitikimo vieta nėra atsakymas. Susitikimas reiškia, kad kelias per tą mazgą yra; jis nereiškia, kad tas kelias pigiausias. Kokios papildomos sąlygos reikia, kad atsakymas būtų teisingas?
Pamatuok apdorotus mazgus ir laiką prieš paprastą Dijkstrą visomis kryptimis. Pateik santykį — ir sąžiningai pasakyk, ar papildomas kodas atsipirko.
2. Raktų mažinimas ir jo kaina
Antras žingsnis pasirinko tinginį šalinimą ir pamatavo 1.12 įdėjimo apdorotam mazgui. Pastatyk kitą variantą.
Pridėk NodeHeap laukui pos []int, kuriame laikoma, kur kuris mazgas yra,
palaikyk jį teisingą per kiekvieną sukeitimą ir realizuok DecreaseKey.
Tada pamatuok tris dalykus: frontier darbą, laiką ir įrašų krūvoje skaičių. Įrašų turėtų sumažėti iki lygiai 1.00 mazgui.
Ar sumažėja ir laikas? Paaiškink rezultatą tryliktos pamokos skaičiais — kiek sukeitimų atlieka pastatymas ir ką ką tik pridėjai kiekvienam iš jų.
3. Kur dvi eilės susilygina
Penktas žingsnis pamatavo 72.7 karto darbo santykį grafe, kurio vidutinis laipsnis 1.49.
Didink briaunų skaičių ir kartok. Prie kokio tankio tiesinė peržiūra nustoja pralaimėti akivaizdžiai? Ar ji kada nors laimi?
Paaiškink dviem antrojo žingsnio kainomis: O((V + E) log V) prieš O(V² + E).
Rask popieriuje tankį, kuriame jos susilygina, ir patikrink, ar matavimas
sutinka. Jei ne — pasakyk, kokio efekto formulės nemato. Jį pamatavai penktame
žingsnyje.
4. Klausimas, į kurį CSA neatsako
Septintas žingsnis parodė CSA, grąžinančią 11 persėdimų ten, kur Dijkstra grąžino 6 — prie to paties atvykimo laiko.
Užrašyk tris realius reikalavimus, kuriuos maršrutų programa galėtų turėti. Kiekvienam pasakyk, ar CSA jį patenkina, o jei ne — ko tam reikėtų.
- „nuvežk kuo anksčiau"
- „turiu lagaminą — ne daugiau kaip vienas persėdimas"
- „sumokėsiu 10 minučių, kad išvengčiau persėdimo"
Tada atsakyk į projektavimo klausimą: transit laiko visus penkis algoritmus. Ar
tu laikytum? Ką darytum vietoj to ir kiek tai kainuotų?
5. Tavo paties 76 kartai
CSA laimėjo pakeitusi klausimą, ne algoritmą.
Paimk vieną operaciją savo algo programoje — bet kurią — ir rask apribojimą,
kuris ją padaro drastiškai pigesnę. Ne greitesnę realizaciją, o siauresnį
klausimą.
Kur ieškoti: algo top, kai k per visą programos gyvenimą nesikeičia;
algo find, kai biblioteka po įkėlimo nebekinta; algo route, kai klausiama tik
apie vieną pradžios tašką.
Realizuok, pamatuok abu ir tiksliai įvardyk, ko atsisakei. Jei negali įvardyti, ko atsisakei, radai ne siauresnį klausimą, o klaidą.