# Greedy algoritme ## Routeplanner opdracht 2 Van **een algoritme volgen** naar **nadenken over efficiëntie**. --- ## Terug naar de vorige les Een goed algoritme bestaat uit **duidelijke stappen**. We kunnen een algoritme: - uitvoeren; - schematisch weergeven; - vergelijken op efficiëntie. > Vandaag: wat gebeurt er als je steeds de keuze maakt die nú het beste lijkt? --- ## Een bezorger moet kiezen !!!grafiek type: punten schaal: gelijk titel: Welke locatie bezoek je als eerste? xmax: 8 ymax: 8 xas: x yas: y Depot = 2 , 3 Fietsenmaker = 5 , 2 Supermarkt = 7 , 6 Buurthuis = 3 , 7 !!! > Je start bij het Depot. Welke locatie bezoek je als eerste? Waarom? --- ## Greedy: de lokale beste keuze Een **Greedy-algoritme** kiest bij iedere stap wat **op dat moment het beste lijkt**. Voor onze routeplanner: > Ga steeds naar de **dichtstbijzijnde nog niet bezochte locatie**. Daarna pas je dezelfde regel opnieuw toe. --- ## Greedy als flowchart !!!stroomschema start(Start) --> kies[Kies startlocatie] --> controle{Alle locaties bezocht?} controle -->|ja| stop(Stop) controle -->|nee| afstand[Bereken afstanden naar onbezochte locaties] afstand --> dichtst[Kies dichtstbijzijnde locatie] dichtst --> bezoek[Ga erheen en markeer bezocht] bezoek --> controle !!! --- <!-- .slide: class="columns" --> ## Voer het algoritme uit Vanaf **Depot (2,3)** zijn de afstanden ongeveer: - Fietsenmaker: **3,2** - Supermarkt: **5,8** - Buurthuis: **4,1** > Welke keuze maakt Greedy? ||| !!!grafiek type: punten schaal: gelijk titel: Locaties xmax: 8 ymax: 8 xas: x yas: y Depot = 2 , 3 Fietsenmaker = 5 , 2 Supermarkt = 7 , 6 Buurthuis = 3 , 7 !!! --- ## Beste stap = beste route? Stelling: > “Greedy vindt altijd de kortste totale route, want iedere stap is de kortste.” Denk na: - kijkt Greedy vooruit? - kan een goede keuze nu later ongunstig zijn? > **Lokaal optimaal** is niet automatisch **globaal optimaal**. --- ## Waarom dan toch Greedy? Stel: er zijn **5, 50 of 500 locaties**. Greedy hoeft niet alle mogelijke complete routes te proberen. Daarom kan het aantrekkelijk zijn als: - snel een oplossing nodig is; - een goede route voldoende is; - de allerbeste route niet gegarandeerd hoeft te zijn. --- ## Best, worst en average case Denk aan de **kwaliteit van de gevonden route**. - **Best case:** de lokale keuzes leveren ook een zeer goede of optimale route. - **Worst case:** een vroege keuze veroorzaakt later een grote omweg. - **Average case:** hangt af van de verdeling van de locaties. > Wanneer noem je een algoritme efficiënt? --- ## Terug naar de leerdoelen Kun je nu uitleggen: 1. waarom Greedy een **algoritme** is? 2. hoe je het algoritme uit een **flowchart** leest? 3. waarom Greedy **efficiënt** kan zijn? 4. waarom efficiënt niet hetzelfde is als **altijd optimaal**? > Werk dit verder uit op het werkblad.