TDDD86 Datastrukturer, algoritmer och programmeringsparadigm

Labb 3 FAQ

Labb 3 FAQ

Q: Måste jag skriva en destruktor? Vad ska den göra i så fall? När ska jag anropa destruktorn?

A: Ja, i det behövs en destruktor. Den ska frigöra allt dynamiskt allokerat minne din lista använder (minne som initialiserats med new). Du ska inte anropa destruktorn explicit, klientprogrammet gör det automatiskt när en listvariabels definitionsområde tar slut.

Q: Jag har hört talas om något som kallas för "smarta pekare" som frigör sitt eget minne och inte kräver minneshantering med new/delete. Får jag använda smarta pekare?

A: Nej. Vi vill att du ska öva på att manuellt allokera och frigöra minne i den här uppgiften. Vi vill att du bygger upp vissa färdigheter innan du blir beroende av funktionalitet i bibliotek för att hjälpa dig.

Q: Vad ska programmet göra om turen har 0 punkter?

A: size() ska returnera 0, distance() ska returnera 0.0, show() ska inte skriva ut någonting och draw() ska inte rita någonting.

Q: Hur representerar jag oändligheten?

A: Använd std::numeric_limits::infinity() från limits.

Q: När ska jag skapa en ny länkad list-nod med new?

A: För att skapa en tur med N noder ska du använda new på Node exakt N gånger. Det är onödigt (och betraktat som dålig stil) att använda new med tillfälliga variabler som används för att traversera listan.

Q: Går det skapa en animation för att se hur heuristikerna beter sig?

A: Ja. Se instruktionerna i tsp.cpp.

Q: Mitt program tar väldigt lång tid på sig. Går det att fixa?

A: Detta beror vanligen på ett problem i smallest insertion-heuristiken. Du har antagligen en loop som undersöker vad som skulle hända vid insättning av den nya punkten vid varje möjligt insättningsställe. Det är helt ok. Om du däremot anropar distance()-metoden för att beräkna den nya turens längd vid varje möjlig insättningspunkt lägger du egentligen till en loop inuti din första loop, vilket blir för långsamt. Du behöver inte beräkna om hela turens längd för varje möjlig insättningspunkt; det räcker att beräkna förändringen i turlängd och hålla reda på vilken insättningspunkt som ger den minsta förändringen.

Q: Hur vet jag att mitt program gör rätt?

A: För usa13509.txt får vi längderna 77449.9794 och 45074.7769 för nearest insertion respektive smallest insertion. För circuit1290.txt får vi 25029.7905 respektive 14596.0971.

Q: Måste jag använda en länkad lista i E4 och E5?

A: Ja. Man får dock ändra på noderna (bara i E4 och E5), kanske lägga till data eller skapa dubbel länkade eller priotitet listor. Det ska dock alltid vara länkade listor som ni ska implementera själva. Man ska hantera minnet och inte skapa garbage. Programmet ska följa samma stil som för resten av labbarna (namn, referens, kommentarer etc).

Q: Hur bra måste min heuristik vara för att vinna E5?

A: Det är svårt att säga. Som riktmärke kan vi avslöja att vinnarna 2014, Simon Lindblad och Tomas Öhberg, hittade en tur av längd 15917.1171 runt tsp1000.txt och att vinnarna 2015, Viktor Holmgren och Yousif Touma, hittade en tur av längd 16377.0782 runt tsp1000.txt.

Sidansvarig: Ahmed Rezine
Senast uppdaterad: 2021-09-10