Plan van aanpak Snelste-pad-algoritmen
Studenten Clermond de Hullu Wiebren Wolthuis Simon Wels Maik Gosenshuis
MDL-referentie D01
Versiebeheer Versie 0.1 0.2
Datum 09-09-2009 18-09-2009
0.2
25-09-2009
Wijzigingen Eerste opzet voor het document. De aanpassingen naar aanleiding van de notulen verwerkt De aanpassingen naar aanleiding van het DSO gesprek van 25-09-09 verwerkt
Door wie Team Wiebren Wiebren
2
Inhoudsopgave Inleiding................................................................................................................................................... 4 Context ................................................................................................................................................ 4 Probleemstelling ................................................................................................................................. 4 De opdracht ........................................................................................................................................ 4 Organisatie .............................................................................................................................................. 5 Ontwikkelmethode ............................................................................................................................. 5 Rollen .................................................................................................................................................. 6 Globale planning ..................................................................................................................................... 7 Increment 1 ......................................................................................................................................... 7 Increment 2 ......................................................................................................................................... 8 Increment 3 ......................................................................................................................................... 8 Kwaliteit .................................................................................................................................................. 9 Reviews ............................................................................................................................................... 9 Code standaard en werkomgeving ..................................................................................................... 9 Definition of Done............................................................................................................................... 9 Producten.............................................................................................................................................. 10 Prototypes......................................................................................................................................... 10 Subsystemen ..................................................................................................................................... 10 Presentatie ........................................................................................................................................ 10 Documentatie ................................................................................................................................... 10 Risico’s................................................................................................................................................... 11 Bijlagen.................................................................................................................................................. 13 Bijlage I – Contactgegevens .............................................................................................................. 13 Bijlage II – Globale Planning .............................................................................................................. 13 Bijlage III - Bronnen ........................................................................................................................... 13
3
Inleiding Dit plan van aanpak is opgesteld om duidelijkheid te verschaffen over de doelstellingen, de aanpak en de aanleiding van het project van groep B binnen de specialisatie Advanced Algorithms. In dit document zullen de opdracht en de projectorganisatie worden toegelicht. Ook zal er een globale planning worden opgesteld inclusief op te leveren producten, zullen projectrisico’s worden uitgewerkt en wordt er uitgediept hoe de kwaliteit binnen het project zo goed mogelijk kan worden gewaarborgd.
Context Manhattan is één van de vijf stadsdelen van New York. In dit stadsdeel, net zoals in de rest van New York, brengen koeriersdiensten pakketjes rond bij bedrijven. Om tussen deze bedrijven te bezorgen is het handig om te weten wat de kortste route is en dus tijd kunt besparen. In dit project zal deze context centraal staan. De straten van Manhattan zijn opgedeeld in streets die horizontaal liggen en avenues die verticaal liggen. Het is dus mogelijk om elk kruispunt in de straat een coördinaat te geven om de straat te indexeren. Op deze manier zullen de verschillende punten die van belang zijn binnen deze context aangeduid worden. Een voorbeeld van zo’n coördinaat 71 horizontaal en 33 verticaal.
Probleemstelling De koeriersdienst wil om zo efficiënt mogelijk te werken weten wat de kortste routes zijn tussen de bedrijven waaraan zij hun bezorgdienst leveren zodat hun koeriers zo min mogelijk tijd kwijt zijn om pakketten te bezorgen. Je moet hierbij rekening houden dat er meerde koeriers tegelijk aan een ronde kunnen werken. Je moet er dus voor zorgen dat koeriers niet meerdere malen langs dezelfde punten gaan aangezien dit een verspilling van tijd zou zijn.
De opdracht Zorg voor een algoritme dat voor dat het kortste pad berekend tussen verschillende bedrijven. Houd hierbij rekening dat het algoritme binnen redelijke tijd klaar moet zijn met het bereken van een ronde. Bij grotere datastructuren zou dit eventueel een probleem kunnen gaan vormen. Zoek hier dan ook een acceptabele oplossing in de vorm van een benaderingsalgoritme voor. Het is de bedoeling dat een koerier die een ronde maakt langs meerdere bedrijven dit zo efficiënt mogelijk kan doen dankzij ons algoritme. Deze route is dan ook de oplossing voor het probleem. Bij een gevonden route moet het volgende worden vermeld: De tijd die nodig was voor het berekenen van de route De totale afstand van de route Welke bedrijven de in de route zaten De volgorde waarop de bedrijven bezocht zijn De lengte van de langste route
4
Organisatie Ontwikkelmethode Scrum zal gebruikt worden als software ontwikkelmethode voor dit project. De keuze hiervoor is gemaakt omdat Scrum flexibeler is dan TSP. Omdat de projectgrenzen gedurende de looptijd waarschijnlijk nog zullen wijzigen, sluit Scrum hier beter bij aan. Ook is Scrum een ontwikkelmethode die weinig overhead heeft. Dit maakt het een goede ontwikkelmethode om binnen een kleinere projectgroep toe te passen. We zullen gebruik maken van een product backlog. In dit product backlog zullen de features die het eindproduct moet bevatten op waarde gerangschikt worden. Een feature wordt gerepresenteerd door een user story. Bij elke user story zullen de kosten geschat worden zodat de product owner de taken die een gelijke waarde hebben maar lagere kosten makkelijk kan onderscheiden, en zo een hogere prioriteit kan geven. De kosten worden geschat op basis van planning poker. Nadat er een product backlog opgesteld is zal er een sprint backlog gemaakt worden. Hierin zal staan hoe het team de komende sprint succesvol denkt door te komen. In de sprint backlog staan de user stories die het eindproduct moet bevatten onderverdeeld in work items. Planningpoker wordt gebruikt voor het inschatten van de uren die nodig zijn voor de work items op basis van de user stories. Denk hierbij ook aan de classificatie in small, medium, large en YMBK (You Must Be Kidding). Het Scrumboard zal ingedeeld worden in de volgende kolommen: Sprint backlog, In progress, To do, Done. Taken die voltooid zijn mogen alleen in de kolom Done worden geplaatst als deze voldoen aan de Definition of Done. Binnen een sprint zal aan het begin van elke dag een daily standup meeting gehouden worden die ongeveer 15 minuten duurt . Binnen deze daily standup meeting zal de voortgang, of het gebrek daaraan besproken worden. Sprints hebben idealiter een lengte van 2 weken. Als gevolg van de lengte van de vooraf bepaalde iteraties is het soms niet mogelijk om aan deze wens te voldoen. In dat geval wordt een langere sprint verkozen boven een kortere. Aan het eind van elke sprint zullen we werkend stuk software hebben die aan de Definition of Done voldoet. Tevens zullen we aan het eind van elke sprint een demo geven van de afgeronde user stories aan de product owner. Aanvullend: Van TSP wordt een beknopte versie van het review proces overgenomen waarbij elke feature gereviewd wordt door een ander teamlid. Een checklist hiervoor wordt beschikbaar gesteld op de wiki. Op momenten waar dat zinvol wordt geacht, zal pair programming toegepast worden. De andere aspecten van XP worden niet direct gebruikt. 5
Definition of Done wordt gedefinieerd. Burndown chart zal digitaal worden bijgehouden. We maken hierbij gebruik van een spreadsheet programma als Excel. We zullen gebruik maken van user stories om eenduidigheid over de requirements met de product owner te creëren. De prioriteit van de requirements zal door de product owner bepaald worden Retrospective aan het eind van elke sprint. (Wat ging goed?, Wat kan beter?) Peer review aan het einde van elke iteratie. (Wat vonden we van elkaar? Waar kunnen we aan werken?)
Rollen Om allemaal wat meer ervaring op te doen met Scrum als projectmethodiek hebben we in overleg besloten de rol van Scrum Master te rouleren per iteratie. Dit betekent dat ons project in totaal drie Scrum Masters zal hebben. Omdat een teamlid hierdoor nooit de rol van Scrum Master op zich zal nemen, zal dit vierde teamlid gedurende het hele project notuleren. Rol
Wie
Taken
Scrum Master
Incr. 1: Clermond Incr. 2: Simon Incr. 3: Wiebren
Zit de vergadering voor. Bewaakt het Scrumproces.
Notulist
Maik
Notuleert belangrijke vergadering en besluiten.
Product owner
Willem Prakken / Jan Stroet
Vervulling van de rol van product owner binnen het Scrumproces.
6
Globale planning Het project duurt circa 18 weken. De aanvangsdatum van het project is woensdag 2 september, de oplevering zal in week 4 van 2010 plaatsvinden. Het project bestaat uit een voorbereidingsfase en drie incrementen. Tijdens de voorbereidingsfase in de eerste vijf weken wordt voornamelijk tijd gestoken in het technisch vooronderzoek, ondersteunend onderwijs en het opzetten van de projectomgeving. Deze fase zal, net als de drie incrementen, worden afgesloten met een assessment. Tevens zal er tijdens het gehele project een urenverantwoording bijgehouden worden die elke maandag voor twaalf uur naar de belanghebbenden gestuurd zal worden. Het eerste increment zal beginnen in week 41. Vanaf dan wordt het project in twee iteraties van 4 weken, en een iteratie van 5 weken afgerond. De inhoud van de verschillende incrementen wordt hieronder kort toegelicht.
Increment 1 In increment 1 zullen we ons voornamelijk bezighouden met het opzetten van een datastructuur met een minimalistische dataset waarop we het algoritme verzinnen dat het probleem oplost. We zullen beginnen met het maken datastructuur. Hieronder wordt het volgende verstaan. Een document met daarin informatie over het ontwerp en hoe het de datastructuur gebruikt dient te worden. Een UML diagram dat het ontwerp van de datastructuur beschrijft. Een implementatie van de datastructuur. Unit tests voor de datastructuur. Een testrapport met daarin de uitslagen van de unit tests. Een onderzoek naar eventuele optimalisaties voor de datastructuur. Binnen deze iteratie zullen we een exacte oplossing voor het probleem zoeken en implementeren. Hier horen de volgende producten bij. We zullen ons eerst richten op een kleine dataset. We verwachten dat een grote dataset de snelheid van het algoritme aanzienlijk zal beïnvloeden. Dit probleem zullen we in de volgende iteratie aanpakken. Een document met een analyse van het gekozen algoritme. Ook wordt er onderbouwd waarom nou juist dit algoritme is gekozen ten opzichte van andere algoritmen. Een implementatie van het algoritme. Unit tests die de correctheid van het algoritme aantonen. Een document met daarin de uitslagen van de testresultaten. Aan het eind van iteratie 1 zullen we een presentatie houden waarin we de voorgang die we deze iteratie hebben geboekt zullen presenteren.
7
Increment 2 In increment 2 zullen we een benaderingsalgoritme verzinnen omdat we er van uit gaan dat de oplossing verzonnen in increment 1 niet in staat is om binnen aanzienlijke tijd het probleem op te lossen. Aan het eind van iteratie 2 zullen we een presentatie houden waarin we de voorgang die we deze iteratie hebben geboekt zullen presenteren.
Increment 3 In increment 3 zullen we een analyse van de complexiteit van ons algoritme uitvoeren. Hierbij zal de kennis van wiskundige methoden en ADC aan bod komen. Aan het eind van iteratie 3 zullen we een presentatie houden waarin we de voorgang die we deze iteratie hebben geboekt zullen presenteren.
8
Kwaliteit Reviews We zullen code en documentatie reviewen om er zo voor te zorgen dat het eindproduct van kwaliteit is. Voor het reviewen van de documentatie en de code maken we gebruik van een checklist die op project-wiki te vinden zal zijn. Een reviewer zal aan de hand van deze checklist kijken of het product aan de kwaliteitsstandaard voldoet. Als een product fouten bevat dan zullen deze in overleg met de auteur verbeterd worden.
Code standaard en werkomgeving We maken gebruik van de Java programmeertaal omdat iedereen hier binnen het team het meeste ervaring mee heeft. Alle ontwikkelaars binnen het team zullen de Java code standaard hanteren te vinden op http://java.sun.com/docs/codeconv/html/CodeConventions.doc10.html. Dit zorgt voor uniforme en leesbare code. We zullen onze code documenteren doormiddel van Javadoc. Getters en Setters zullen niet gedocumenteerd worden omdat aan de hand van de naam te zien is wat de functie doet. Daarnaast wordt verwacht dat Javadoc meer toevoegt dan de naam van de functie en de bijbehorende argumenten al duidelijk maken. Al het Java programmeerwerk zal plaats vinden in de Eclipse IDE. Binnen de Eclipse IDE maken we gebruik van de Subclipse plugin om zo de SVN bij te werken. De SVN die we gebruiken voor versiebeheer wordt gehost op code.google.com dit neemt automatisch de noodzaak voor back-ups uit onze handen. Ook houden we een Wiki bij waarop het alle projectinformatie te vinden is. Hieronder verstaan we: Een todo lijst Een master document list De sprints De handleidingen De tests en testscenario’s De notulen De definition of done De user stories Een agenda De reviews
Definition of Done Broncode omvat: Een werkende applicatie Broncode die compileert De broncode hanteert de afgesproken requirements. De code is gedocumenteerd De code is opgenomen in het klasse diagram Unit tests 9
Documenten/rapporten: Het document heeft: o Een voorblad o Een titel o Pagina nummering o Een inhoudsopgave o Bronvermelding indien nodig o Het voldoet aan de template Een review moet door minstens een persoon worden gedaan en er wordt speciaal gelet op: o Inhoud o Zakelijk taalgebruik o Spelfouten o De minimale eisen waaraan het document moet voldoen, zoals hierboven genoemd.
Producten In dit hoofdstuk is de lijst van de op te leveren producten dit project uitgewerkt. Dit hoofdstuk zal naar mate het project vordert beter en verder worden uitgewerkt.
Prototypes Een prototype waarin het probleem wordt opgelost en aantoont dat JGraphT de aan de juiste voorwaarden voldoet. Een prototype met verschillende oplossingen voor het probleem zodat het snelste algoritme bepaald kan worden. Een prototype met een grafische weergave.
Subsystemen Presentatie Iteratie 0 (PVA) Iteratie 1 Iteratie 2 Iteratie 3
Documentatie Plan van Aanpak Ontwerpdocument Testrapport Handleiding
10
Risico’s In dit hoofdstuk worden de risico's beschreven die wij denken tegen te kunnen komen en hoe we hier als team op zullen reageren. Risico: Interpretatie SCRUM Impact: Klein Beschrijving: SCRUM wordt door een aantal leden niet gesnapt/verkeerd toegepast. Meetpunten: 1. Er treden conflicten op die betrekking hebben op het projectmanagement. Dit risico is te herkennen aan SCRUM taken die door teamleden verschillend worden geïnterpreteerd. Preventief: 1. Alle leden worden geacht zich vanaf het begin te verdiepen in SCRUM. Als er onduidelijkheid bestaat tussen teamleden dan worden deze door middel van overleg opgelost. Correctief:
1. De onduidelijkheden worden vastgesteld en verholpen
Risico: Technische problemen met betrekking tot JGraphT Impact: Zeer groot Beschrijving: JGraphT werkt niet zoals verwacht of zoals gedocumenteerd is. Meetpunten: 1. Een teamlid boekt langere tijd geen progressie. Preventief: 1. Er moet zo snel mogelijk een prototype gemaakt worden van het eindproduct om zo grote technische problemen uit te stellen. Correctief:
1. Het zoeken van een omweg die het probleem oplost. 2. Een nieuwe datastructuur kiezen.
Risico: Afwezigheid Impact: Klein - Zeer groot Beschrijving: Afwezigheid door individuele taken/vakken of ziekte. Meetpunten: 1. Teamleden werken het minder dan het afgesproken aantal uren. Preventief: 1. Er moet zo goed mogelijk van tevoren worden aangegeven hoeveel tijd teamleden kwijt zijn buiten het project. 2. Er moet goed worden afgesproken hoeveel tijd men geacht wordt in het project te steken Correctief: 1. Teamleden worden aangesproken op hun gedrag. 2. Als een teamlid veelvuldig in de fout gaat, dan zal er de hulp van een leraar ingeschakeld worden.
Risico: Planning Impact: Groot – Zeer groot Beschrijving: De tijdsduur van de geplande taken komen niet overeen met de daadwerkelijk tijd. Meetpunten:
1. De planning komt niet overeen waardoor de burn down chart een lijn creëert die naar het horizontale neigt. 11
Preventief: Correctief:
1. Het inschatten van de features op een correcte manier doen, door bijvoorbeeld gebruik te maken van planning poker. 1. De product owner en belanghebbenden moet gealarmeerd worden over het feit dat het project hoogstwaarschijnlijk uitloop zal kennen.
Risico: Wiskundige aspecten worden onvoldoende begrepen Impact: Middel Beschrijving: Het team heeft onvoldoende wiskundige kennis om een analyse binnen de afgesproken tijd uit te voeren. Meetpunten: 1. Teamleden zijn lang bezig met het de wiskundige analyse en maken geen vordering. Preventief: 1. De teamleden moeten zoveel mogelijk aanwezig zijn bij de colleges die als ondersteuning aangeboden worden tijdens de minor. Correctief: 1. Hulp vragen bij een van de ondersteunende leerkrachten.
Risico: Onvoldoende kennis algoritmen. Impact: Middel Beschrijving: Het team heeft onvoldoende verstand van de specifieke algoritmen die nodig zijn binnen het project. Meetpunten: 1. Taken die betrekking hebben op het algoritmisch oplossen van het probleem duren te lang. Preventief: 1. De taken uit het blokboek maken om zo voor de specifieke kennis te zorgen. Correctief: 1. Alsnog, in overleg met elkaar, de specifieke kennis vergaren.
12
Bijlagen Bijlage I – Contactgegevens Naam Maik Gosenshuis Simon Wels Clermond de Hulu Wiebren Wolthuis
Telefoon 0612413098 004915208708687 0615149168 0657671070
Email
[email protected] [email protected] [email protected] [email protected]
Bijlage II – Globale Planning Bijlage III - Bronnen http://java.sun.com/docs/codeconv/html/CodeConventions.doc10.html
13
