Sidst opdateret: 29. april, 15.17

Datalogisk Institut
Københavns Universitet

2A G2-opgave
2002-2003

Der er problemer med LEDA på de forskellige maskiner; det forlyder fra EDB-afdelingen, at det skulle virke på maskinen thokk.

Der er flere fejl i bbTSP.h: operator= skal returnere void
void operator= (const _1Tree& T) {...}

Der er fejl i bbTSP.h implementation af operatoren >=. Der skal returneres
return (length >= T.length);

Der hersker nogen tvivl om, hvorvidt LEDA opfatter grafen som orienteret eller ikke-orienteret. Grunden er formentlig, at erklæringen "graph G" initialiserer G til den tomme, orienterede graf. Den senere konstruktion "complete_ugraph" formår tilsyneladende ikke helt at ændre på dette. Skal man have fat i alle kanter incident med en given knude, skal man altså bede om "inout_edges"; "adj_edges" giver kun ud-kanterne. Det forlyder at initialiseringen "ugraph G" (include "LEDA/ugraph.h") skulle rette op på problemet!

Pas iøvrigt på med at ændre på den aktuelle liste/graf inde i iterationer af formen "forall..."; resultaterne er ikke veldefinerede! Opret i stedet en liste for sig, som med sikkerhed indeholder alle de ønskede elementer, og iterer over denne (ændringer i grafen vil jo ikke påvirke den allerede oprettede liste)

Vælger man i sin grænseværdi-beregning at skjule den aktuelle knude med "G.hide_node" anbefales det at bruge den version der tilføjer samtidigt skjulte kanter til en liste.

Bemærk, at begge implementationerne af Kruskal i det udleverede rammeprogram, bbTSP.cc, ikke opdaterer length (summen af kantvægtene). Ønskes en sådan opdatering, kan man tilføje "mst.length += W[e];" umiddelbart efter opdateringen af mst.E og mst.D.

Opgave 5: Med "øvre grænse i rodknuden" menes værdien af start-løsningen.

Opgave-formulering

g2.pdf

Ramme-program

bbTSP.h

bbTSP.cc

randSelRange.cc

makefile

kommentarer [dvi | ps | pdf ]

Instanser (m. optimal løsningsværdi)

bornholm8.tsp (100)

rand10.tsp (970)

rand15.tsp (1189)

rand20.tsp (1109)

rand25.tsp (1307)

rand30.tsp (758)

gr17.tsp (2085)

gr21.tsp (2707)

gr24.tsp (1272)

Øvelser i G2-opgaveperioden fordeler sig som følger: