Datalogisk Institut
Københavns Universitet
Projektopgave 2, Videregående Algoritmik, blok 2, 2006
Uklarheder, hints og tips
- Opgaven er lidt uklar hvad angår konstanten i (10).
UNCAPACITATED-PROJECT-SELECTION er defineret uden konstant.
Derimod skal konstanten medtages for at få en løsning til
RELAXED-PROJECT-SELECTION.
- Opgave 6 er excl. konstant
- Opgave 7,8,9 er incl. konstant
- I rammeprogrammet er programmeringssproget C benyttet, da dette
harmonerer med pseudokoden i Cormen. Man må godt blande C og C++ så
længe det er læseligt for instruktoren.
- Proceduren "solve_relaxed" løser det relaxerede problem (7).
Resultatet afrundes nedad til nærmeste heltal (overvej hvorfor dette giver
en lovlig øvre grænseværdi). Ved tegning af figuren i opgave
7 kan det være hensigtsmæssigt at benytte den ikke-afrundede værdi.
Tilsvarende kan avancerede søgemetoder i opgave 8 benytte den ikke-afrundede
værdi.
- I proceduren "branch-and-bound" kan det være hensigtsmæssigt at
kopiere matricerne til lokale tabeller, hvor nogle rækker og søjler er
slettet (for variable som allerede er blevet tildelt en værdi). Det er
dog vigtigt at kopieringen af matricerne sker i en separat procedure som
udregner grænseværdien. Ellers vil der ligge mange kopier af matricerne
på stakken, og programmet risikerer at gå ned grundet pladsmangel
på stakken.
- Man kan evt. benytte konstanterne TRUE, FALSE, FREE til at angive
om en variabel er blevet tildelt værdien 1, 0 eller om der endnu ikke
er blevet forgrenet på den.
Konkurrence
Der udloves en øl/sodavand til det hold som får de bedste køretider
for instanserne
- randm140.txt
- randm160.txt
- randm180.txt
- randm200.txt
Send dine bedste køretider til pisinger@diku.dk senest onsdag 10. januar
sammen med en kort beskrivelse af de anvendte metoder.
Det er tilladt at implementere hurtigere versioner af maximum-flow algoritmen.
| Gruppe |
randm140 |
randm160 |
randm180 |
randm200 |
kommentar |
| DP |
2.50 s |
6.72 s |
3.27 s |
7.31 s |
(*) |
| Lasse Reinhold m.fl. |
2.52 s |
2.07 s |
10.94 s |
2.96 s |
(**) |
- (*) Simplest mulige implementering. Lineær søgning efter lambda.
(3GHz pentium)
- (**)
Vi brancher på den første FREE knude i x, først med FALSE dernæst med TRUE.
Bedste lambda findes med binær søgning. Der branches dog aldrig på en
ulovlig løsning (en TRUE afhænger af en FALSE) eller på en løsning hvis TRUE
knuder har overskredet. (1 GHz Celeron, compileret med -O3)