Računalništvo 2

Na vajah se boste razdelili v skupine po 3 do 4 članov.

Naloga vsake skupine bo, da implementira enega izmed algoritmov za minimalno vpeto drevo, ki ste jih spoznali na predavanjih.

Nato boste skupine med seboj tekmovale. Med datotekami najdete dve .txt datoteki vsaka pa vsebuje nekaj točk v ravnini. Za vsakega izmed primerov mora skupina:

• Najti ceno minimalnega vpetega drevesa (drevo, ki povezuje vse točke)
• Dovolimo dodatek ene točke. Poiščite točko s katero čim bolj znižate ceno MVD.
• Dovolimo dodatek 5 točk. Poiščite take točke, ki čim bolj znižajo ceno MVD.
• Dodajte do največ n točk, ki čim bolj znižajo ceno.

Ko dobite odgovor za vsako izmed "kategorij" napišite rezultat za vašo skupino na tablo. Še vedno vas lahko skupina premaga, če dobi boljši rezultat.

V poročilo vključite katerega izmed algoritmov za MVD ste implementirali in rezultat za minimalno vpeto drevo za oba primera.

Za naslednje probleme ne rabite oddajat kode v poročilo. Na kratko komentirajte kakšno strategijo ste uporabili, kakšni so možni problemi, itd.