Namų darbas

Ką pateikti

algo su route ir frontier, praeinantis go test ./..., plius ataskaita. Tai paskutinis kurso namų darbas; kursinio darbo užduotis yra atskirai.

1. Visa lentelė

Viena lentelė, tavo paties matavimai, n = 1 000 ir 10 000:

	perėjimai	dienos	frontier darbas	laikas
BFS (14 pamoka)
Dijkstra, tiesinė peržiūra
Dijkstra, krūva

Vidurkink per visas pasiekiamas kryptis, ne per vieną porą.

Tada pateik du santykius — darbo ir laiko — ir pasakyk, kurį iš jų rašytum ataskaitoje žmogui, sprendžiančiam, ar verta keisti. Pagrįsk pasirinkimą.

2. Prielaida po kiekvienu algoritmu

Kiekvienas šio kurso algoritmas remiasi sąlyga, kurią sulaužius jis ne sulėtėja, o tampa neteisingas.

Įvardyk sąlygą kiekvienam, po vieną eilutę:

• dvejetainė paieška (6 pamoka)
• maišos indeksas (10 pamoka)
• Dijkstra (15 pamoka)
• CSA (15 pamoka)

Tada kiekvienam pasakyk, kas nutinka ją sulaužius: klaida, sulėtėjimas ar užtikrintai neteisingas atsakymas. Vienas iš keturių skiriasi nuo kitų — pasakyk, kuris ir kodėl būtent tai daro jį pavojingiausią.

3. Kada statytum A*

Šeštas žingsnis pamatavo, kad A* pralaimi, ir paaiškino kodėl: euristika matė 4.1 % kainos.

Aprašyk grafų uždavinį, kuriame geometrinė euristika matytų didžiąją dalį kainos, ir įvertink, kiek A* ten nukirstų. Tada aprašyk tokį, kuriame ji nematytų nieko.

Nė vienas negali būti viešasis transportas ar automobilių maršrutai — šie du yra žingsnyje.

4. Kainos modelis yra sprendimas

Svoriai buvo laukimas 2.0 ir 5 minučių persėdimo bausmė, abu iš literatūros, o matavimas parodė, kad 149 maršrutai iš 200 gavo mažiau persėdimų, o 10 atvyko vėliau.

Parink kitokius svorius keleiviui, kurį įvardysi — tėvams su vežimėliu, naktinės pamainos darbuotojui, turistui su lagaminu — ir pagrįsk kiekvieną skaičių.

Tada pasakyk, ką reikėtų pamatuoti, norint sužinoti, ar tavo svoriai geresni už numatytuosius. „Atrodo teisingiau" nėra matavimas, ir „maršrutai gražesni" irgi ne.

5. Paskutinis klausimas

Vienas puslapis, savais žodžiais.

Pamatavai tiesinę paiešką, dvejetainę paiešką, keturis rikiavimus, du rikiavimus be palyginimų, maišos indeksą, du medžius, krūvą, dvi grafų paieškas ir tris trumpiausio kelio algoritmus.

Aprašyk uždavinį, su kuriuo iš tikrųjų susidūrei — darbe, kitame kurse, savo projekte — ir pasakyk, ką dabar darytum kitaip. Ne kurią struktūrą rinktumeisi: ką pirmiausia PAMATUOTUM ir kokį klausimą užduotum prieš matuodamas.

Jei tavo atsakymas yra struktūros pavadinimas, perskaityk aštuntą žingsnį dar kartą.