Izpitno vprašanje RAČ2PRA 14900

Iz MaFiRaWiki

Vprašanje:

Mehanik mora popraviti n avtomobilov. Za i-tega potrebuje d_i dni. V kakšnem vrstnem redu naj jih popravlja, da bo skupna čakalna doba najkrajša? Dokaži pravilnost svoje strategije!

Odgovor:

Nalogo lahko rešimo na več načinov, s pomočjo iskanja Hamiltonovega cikla (Trgovski potnik), s Problemom 0/1 nahrbtnika, itd. Najlažje pa se je lotiti reševanja s Požrešno metodo. Pred seboj imamo n avtomobilov, ki so jih lastniki v delavnico pripeljali hkrati. Za vsak avtomobil vemo, koliko dni bo trajalo popravilo. Denimo, da je avtomobilov šest: Za popravljanje prvega bomo potrebovali 3 dni, za drugega 2 dni, za tretjega 7 dni, za četrtega 10 dni, za petega 5 dni in za šestega prav tako 5 dni. Predstavljajmo si tabelo, v kateri so indeksi (od 0 naprej) avtomobili, elemnti tabele pa dnevi, potrebni za popravilo posameznega avtomobila. Sprehodimo se čez tabelo. Zamislimo si prazno množico (ta je zagotovo dopustna). Dodamo ji avto iz tabele, ki zahteva najmanj časa (ki minimizira kriterij). Na vsakem koraku izberemo "najboljši" avto ta hip (takega, ki za popravilo zahteva najmanj dela). Ko pridemo do konca (ko ni več kandidatov za dodajanje k dopustni množici), smo zgradili optimalno rešitev. (Dobimo urejeno zaporedje)

1.avto  2.avto  3.avto  4.avto  5.avto  6.avto
3dni    2dni    7dni    10dni  5dni     5dni

Rešitev:

2.avto  1.avto  5.avto  6.avto  3.avto  4.avto
2dni    3dni    5dni    5dni    7dni    10dni

Čakalni čas lastnika je čas popravila vseh pred njim + čas popravila njegovega avtomobila.

Lastnik 5.avtomobila bo tako čakal 2 + 3 + 5 = 10 dni na popravilo svojega avtomobila.

Povprečni čakalni čas pa je: Vsota čakalnih časov vseh lastnikov / Število lastnikov. Povprečno čakalno dobo za zgornji primer bi dobili takole:

Vsota čakalnih časov vseh lastnikov = 2+2+3+2+3+5+2+3+5+7+2+3+5+7+10 = 61  
Število lastnikov = 6
Povprečni čakalni čas = 61/6 = 10.17 dni

Če bi avtomobile popravljali v začetnem vrstnem redu bi bil povprečni čakalni čas enak 128/6 = 21.33 dni, kar je enkrat več kot, če bi jih prej uredili kot smo naredili zgoraj.

Osebna orodja