TDDC30 Programmering i Java, datastrukturer och algoritmer

Laboration 4 - flytta lådor

Laboration 4 - flytta lådor

Syfte

Huvudsyftet med denna labb är att öva på problemlösning, att utifrån ett problem hitta en lämplig representation och lösning för problemet.

Vilka programkonstruktioner ni kommer att använda beror på flera faktorer, bland annat vilken representation av problemet man väljer. Men man bör få nytta av mycket av det vi gått igenom i kursen. Dessutom ingår läsning från fil och att göra ett tydligt gränssnitt för programmet, antingen grafiskt eller textuellt.

Lådproblemet är ett relativt komplext problem, och det är inte säkert att ni alltid kan hitta en helt optimal lösning. Det kan även vara så att ni hittar en optimal lösning, men att den blir för långsam för att använda på stora filer. Det ingår alltså i uppgiften att väga faktorer som lösningskvalité, tidsåtgång m.m. mot varandra. Lösningarna ska dock alltid vara korrekta. I steg 2 och 3 är det ett krav att någon sorts optimering utförs. De val ni har gjort avseende detta ska sedan tas upp i diskussionen.

Det är viktigt att ni tänker igenom problemen noga innan ni börjar koda så att ni har kommit på en lämplig algoritm och representation. Läs igenom hela labinstruktionen noga, så ni kan ta hänsyn till alla deluppgifter när ni funderar på lämplig representation av problemet. Tänk också på att er lösning blir olika beroende på vilken representation av problemet ni väljer. Representationen och lösningarna ska även beskrivas och diskuteras i en labrapport.

En annan viktig aspekt att tänka på när ni skriver ert program är den objektorienterade. Fundera noga igenom hur ni ska dela upp programmet i lämpliga klasser, och hur de ska hänga ihop på ett vettigt sätt.

Testfiler

Det finns ett antal färdiga lådkonfigurationsfiler för labben. Utöver dessa ska ni även göra egna konfigurationer att prova era lösningar på. Minst en egen konfigurationsfil ska lämnas in.

Problembeskrivning

På en arbetsplats finns ett antal lådor som ska flyttas. Dock går det inte att flytta lådorna hur som helst. En del är tunga, en del har lådor över sig som måste flyttas först.
Dessa lådor har följande egenskaper:

• Varje låda har en bokstav och en siffra associerad
  • Bokstaven är lådans "namn"
  • Siffran är lådans tyngd, mätt i antalet personer som krävs för att flytta den
• Varje låda kan stå ovanpå en eller flera andra lådor, som i sin tur kan stå ovanpå andra lådor
  • En låda kan bara flyttas om ingen annan låda står på den
  • Lådor kan ha därför implicit ha olika höjd och bredd, men det är oviktigt så länge du inte försöker rita lådorna
• En låda kan naturligtvis också stå för sig själv, utan några lådor under eller över sig

fig 1. Exempel på en lådkonfiguration

Syntax för en lådkonfigurationsfil

Varje lådkonfiguration sparas på en fil, enligt följande ordning

• På första raden finns ett tal som beskriver hur många lådor konfigurationen består av (heltal)
• Sedan följer en rad för varje låda
  • Varje låda beskrivs på en rad med dess bokstav följt av dess tyngd (tecken mellanslag heltal)
• Sedan följer ett tal som anger hur många lådor som står på någon annan låda (heltal)
  • Varje sådan lådrelation beskrivs sedan med varsin rad med två lådnamn, där den första står ovanpå den andra. (tecken mellanslag tecken)

Nedan är en lådkonfiguration som beskriver bilden ovan:

9
a 2
b 5
c 3
d 1
e 3
f 1
g 3
h 2
i 5
9
a b
b g
b e
e f
f h
e i
c e
c d
d i

Här finns fler färdiga lådkonfigurationer att testa på

Uppgift 1: Ge en lösning

Skapa och implementera en algoritm som ger (åtminstone) en möjlig ordning för att plocka ner lådorna, så att man aldrig lyfter en låda som står under en annan. Ignorera tyngden på lådorna i denna deluppgift. Ni kan än så länge räkna med att varje låda har vikt 1, alternativt att ni har oändligt många personer att flytta dem. Prova ert program såväl med de givna lådkonfigurationerna som på egna konfigurationer.

Handledning

För att kunna skapa och implementera algoritmen behöver man även fundera på vilken datastruktur som är lämplig att använda för att representera lådinformationen.

Krav:

• Krav på huvudprogrammet
• G: En algoritm som utför ovanstående

Uppgift 2: Minimera tiden

I denna uppgift måste ni ta med lådornas tyngd i beräkningen. Er algoritm får en lådkonfiguration och antalet personer tillgängliga som indata. Utdata ska vara en sekvens av lådförflyttningar för att flytta alla lådor. Sekvensen ska vara optimerad så att tiden det tar att flytta alla lådor är minimal.

Handledning

Antag att vi har X personer tillgängliga för att flytta lådorna. (X är större eller lika med antalet personer som krävs för att lyfta den tyngsta lådan). Alla lådor tar lika lång tid att flytta så varje tidsenhet kan man lyfta lådor som totalt kräver max X personer. Man kan bara lyfta lådor som inte har några andra lådor ovanpå sig. I bilden ovan kan man t.ex. inte börja med att lyfta låda A och B, eftersom B står under A, däremot kan man lyfta a och c i början om man har minst 5 personer tillgängliga (X >= 5).

Krav

• Krav på huvudprogrammet
• G: Designa en strategi som väljer lådor efter intelligenta kriterier. En bra lösning tittar på mer än bara lådorna som är högst upp. Implementera en algoritm som använder strategin.
• G: I presentationen av lösningen ska de tydligt gå att se vilka lådor som flyttas samtidigt resp efter varandra, samt den totala tiden.

Tips: Diskutera er lösningsidé med en labbassistent för att se om strategin verkar klok, om ni är osäkra.

Uppgift 3: Minimera kostnaden

I denna uppgift ska ni minimera både det antal personer och tiden det tar för att flytta lådorna, så att de totala lönekostnaderna blir så låga som möjligt. I denna uppgift är det alltså, till skillnad från den förra, inte givet hur många personer man har tillgång till utan både det och tiden kan variera.

Handledning

Antag att tidsenheten som behövs för att lyfta ner en låda är 15 minuter. Personerna som jobbar har 100 kronor i timlön. Skapa och implementera en algoritm som minimerar lönekostnaderna för att flytta en uppsättning lådor. Antag att alla personer måste jobba hela tiden det totalt tar att flytta alla lådorna. Alla personer får lön för varje påbörjad arbetstimme.

Krav:

• Krav på huvudprogrammet
• G: Designa en effektiv heuristik-strategi. Strategin behöver inte garantera optimal lösning, men ska hitta en lösning och sedan iterativt försöka förbättra den. Implementera en algoritm som använder strategin.
• G: I presentationen av lösningen ska de tydligt gå att se vilka lådor som flyttas samtidigt resp. efter varandra, samt den totala tiden, antal personer och kostnaden.

Huvudprogrammet

Utöver de tre lösningarna ska även ett huvudprogram skrivas. Detta huvudprogram ska kunna läsa in godtyckliga lådkonfigurationer från fil, det vill säga inte bara de fyra som är givna utan även konfigurationer ni skrivit själva eller någon labbassistenten vill testa med. Det ska innehålla ett gränssnitt där användaren kan välja en lådkonfigurationsfil, bestämma vilket av de tre problemen som ska lösas, mata in parametrar till problemet t.ex. antal personer tillgängliga och slutligen få en lösning presenterad på en lättförståelig och komplett form. Det räcker t.ex. inte att ge den minimala lönekostanden i uppgift 3, utan man ska även tydligt se hur många personer som behöver jobba hur lång tid och hur man ska flytta lådorna för att uppnå lösningen.

Efter att en lösning presenterats av programmet ska det gå att prova igen med en ny konfiguration eller ett nytt problem utan att behöva stänga av / starta om programmet. Programmet ska inte avslutas förrän man som användare väljer att avsluta.

• G: Gränssnittet kan vara textbaserat, men extra krav på tydlighet ställs då
• G: Programmet ska använda principer för objektorienterad design och vara vettigt strukturerad.
• G: Programmet ska vara uppdelat i väl valda klasser och paket.
• G: Man ska kunna välja om man testar uppgift 1, 2 eller 3.
• VG: Gränssnittet ska vara helt grafiskt baserat, man ska kunna utläsa och mata in allt som behövs via GUI't. Konsolen ska ej behövas användas alls.
• VG: Om det ligger en bild på samma plats som lådkonfigurationen, med samma filnamn(förutom 'efternamnet') ska den visas upp i programmet.

Examination

Labbrapport

Eftersom fokus i denna labb ligger lika mycket på problemlösning som på själva programmeringen ska ni utöver koden även lämna in en labbrapport som innehåller en beskrivning och reflektioner över vad ni gjort. En kortfattad beskrivning av den datastruktur ni valt i uppgiften, samt en motivering till varför ni valde just den, och en reflektion över hur lämplig den visade sig vara för att lösa problemet. För varje uppgift ska ni kortfattat beskriva algoritmen ni skapat, ge en uppskattning av dess tidskomplexitet och reflektera över hur bra er algoritm är (speciellt i förhållande till en tänkbar "optimal" algoritm). Om någon av era algoritmer har någon begränsning, t.ex. är väldigt långsam, bara klarar av konfigurationer av en viss storlek, eller ger en uppskattning av minimitid/lön snarare än absolut minimum, så beskriv begränsningen och varför ni valt att göra så. Har begränsningen gjort att ni istället vunnit på något annat område? Ifall en lösning gett väldigt olika resultat för olika lådkonfigurationsfiler kan ni ta med det. Bifoga i så fall de lådkonfigurationsfiler ni diskuterar (om de inte är någon av de givna). Inkludera även alternativa idéer för lösningar och datastrukturer ni haft. Använd vad ni lärt er om datastrukturer och algoritmanalys för att jämföra med den lösning ni valde att implementera.

• VG: Ett översiktligt klassdiagram över ert program. Diagrammet ska innehålla relationerna mellan era klasser samt de viktigaste metoderna och attributen. (Dia är ett bra verktyg för att rita klassdiagram)

Labbrapporten och klassdiagrammet kan lämnas in något senare än källkoden, se de generella labbinstruktionerna för specifika datum.

Rapporten bör omfatta 1-2 A4-sidor. Bifoga följande i ett mail till din labassistent:

• Källkoden för uppgiften
• Minst en egen lådkonfigurationsfil
• En labrapport enligt ovan
• En separat sida där ni anger ungefär hur mycket tid ni har använt för uppgiften, och några kortfattade reflektioner kring uppgiften. Det kan t.ex vara synpunkter på uppgiften och feedback till lärarna, vad som känns oklart, begrepp som är svåra, osv. (bedöms ej)
• Ange tydligt i mailet('VG' i ämnesraden) om ni satsar på VG.

Checklista för inlämnat material:

• Är materialet inlämnat i tid?
• Är alla delar inlämnade?
• Följer koden kodstandarden? Avvikelser ger rest.
• Är koden enhetligt indenterad? Slarvig indentering ger omedelbart rest.
• Är koden kommenterad enligt kodstandarden?
• Används inkapsling? Om det finns fall där instansvariabler accessas utanför klassen ger det omedelbart rest.
• Uppfyller programmet kravspecifikationen?
• Visar labrapporten på god förståelse av problemen och lösningarna?
• Är alla VG-delar gjorda? (Om ni valde att ge er på det)

---

Skapad av Sara Stymne 2005, modifierad 2006, 2011, 2012, 2013

Sidansvarig: Jonas Lindgren
Senast uppdaterad: 2013-02-27