Inleiding

Download hier de praktische opdracht in PDF

Voorbeelduitwerking

Praktische Opdracht Informatica Leerjaar 5

Routeplanner voor een Bezorgservice

Introductie

Stel je voor: je werkt bij een klein bezorgbedrijf dat pakketten aflevert in een stad. Je bouwt een systeem dat helpt om de beste route te plannen voor de bezorger. Hoe bepaal je de aflever-volgorde? Hoe sla je locaties en bestellingen op? En kun je met een algoritme een efficiëntere route vinden dan “de volgorde van binnenkomst”?
In deze opdracht bouw je een eenvoudige webapplicatie met PHP, SQL/phpMyAdmin en algoritmiek (o.a. brute-force en greedy). Je sluit af met een werkend prototype met helder commentaar bij de gebruikte algoritmes.

Euclidische afstand

We werken met de euclidische afstand. Voor twee punten ((x_1, y_1)) en ((x_2, y_2)) geldt:

afstand = √((x2 − x1)² + (y2 − y1)²)

Dit volgt uit de stelling van Pythagoras. Tip: als je alleen afstanden wilt vergelijken, mag je de wortel weglaten (het ordeverschil blijft gelijk).

Leerdoelen

Na deze opdracht kun je:

  • Een eenvoudige database opzetten met twee gekoppelde tabellen
  • Gegevens ophalen en verwerken met PHP en SQL
  • Een route-algoritme schrijven en efficiëntie vergelijken
  • Inzien hoe algoritmes in realistische situaties worden toegepast

✏️ Opdracht 1: De database opzetten

Doel

Maak in phpMyAdmin een database voor adressen en bestellingen.

Wat je leert

  • Een database aanmaken in phpMyAdmin
  • Tabellen maken met passende kolommen en typen
  • Een eenvoudige relatie leggen via een foreign key

Stap 1: Maak de database aan

  • Naam: routeplanner

Stap 2: Maak de tabellen aan

We gebruiken x, y-coördinaten (geen GPS).

Tabel adressen

Veldnaam Type Extra

Tabel bestellingen

Veldnaam Type Extra
  • Relatie: leg een foreign key tussen bestellingen en adressen.

Stap 3: Voeg testdata toe

Voeg in phpMyAdmin logische testdata in beide tabellen toe.

Theorie: Wat is het Greedy-algoritme?

Het greedy (gulzige) algoritme kiest bij elke stap de lokaal beste optie (de dichtstbijzijnde volgende locatie), zonder vooruit te kijken. Het is eenvoudig en snel, maar niet altijd optimaal.

Greedy in de routeplanner

  1. Begin bij de startlocatie (bijv. (x=2, y=3)).
  2. Kies van alle onbezochte locaties de dichtstbijzijnde.
  3. Ga daarheen.
  4. Herhaal stap 2–3 tot alles bezocht is.

Voorbeeldpunten:

  • Start: (2, 3)
  • Station: (5, 2)
  • Winkelgebied: (7, 6)

Afstanden (voorbeeld):

  • Naar Station: √((5−2)² + (2−3)²) ≈ 3,2
  • Naar Winkelgebied: √((7−2)² + (6−3)²) ≈ 5,8

Je gaat dus eerst naar Station, daarna opnieuw kiezen, etc.
Voordelen: simpel, snel. Nadelen: geen garantie op de kortste totale route.

✏️ Opdracht 2: Greedy-algoritme

Situatie
Start: Centrum (2, 3). Afleverpunten:

  • Station (5, 2)
  • Winkelgebied (7, 6)
  • Park (3, 7)

Stap 1. Teken alle punten in een assenstelsel en label ze.
Stap 2. Pas greedy toe: telkens de dichtstbijzijnde volgende locatie.
Stap 3. PHP-implementatie met data in variabelen (geen database nodig).
Stap 4. Hergebruik je code met data uit de database.

Theorie: Brute force

Brute force probeert alle mogelijke volgordes en kiest de kortste route. Altijd optimaal, maar groeit factorieel met het aantal punten en wordt snel onpraktisch.
Voor 3 punten: 3! = 6 routes; voor 6 punten: 720 routes; voor 10 punten: > 3,5 miljoen routes.

Voorbeeld (zelfde dataset)

Start: Centrum (2, 3); afleveren op Station (5, 2), Winkelgebied (7, 6), Park (3, 7).

Permutaties (6 routes):

  1. Centrum → Station → Winkelgebied → Park
  2. Centrum → Station → Park → Winkelgebied
  3. Centrum → Winkelgebied → Station → Park
  4. Centrum → Winkelgebied → Park → Station
  5. Centrum → Park → Station → Winkelgebied
  6. Centrum → Park → Winkelgebied → Station

Afstanden (afgerond op 2 decimalen):

  • Route 1: 3,16 + 4,47 + 4,12 = 11,75
  • Route 2: 3,16 + 5,39 + 4,12 = 12,67
  • Route 3: 5,83 + 4,47 + 5,39 = 15,69
  • Route 4: 5,83 + 4,12 + 5,39 = 15,34
  • Route 5: 4,12 + 5,39 + 4,47 = 13,98
  • Route 6: 4,12 + 4,12 + 4,47 = 12,71

Conclusie: de kortste route is Centrum → Station → Winkelgebied → Park met totale afstand 11,75.

✏️ Opdracht 3: Brute-force-algoritme

Gebruik dezelfde data als bij Opdracht 2.

Stap 1. Implementeer brute force in PHP met data in variabelen.
Stap 2. Gebruik vervolgens de database voor dezelfde berekening.
Vergelijk de uitkomsten en rekentijden met Greedy.

✏️ Opdracht 4: Applicatie afmaken

De applicatie voldoet minimaal aan:

  • Overzicht van alle adressen
  • Overzicht van alle bestellingen, met filter op dag
  • Valide invoer van nieuwe adressen
  • Valide invoer van nieuwe bestellingen
  • Uitvoeren Greedy voor een dag
  • Uitvoeren Brute Force voor een dag
  • Eenvoudige maar bruikbare UI
  • Query’s beveiligd tegen SQL-injectie (bijv. prepare()/bind_param)

Nice to have

  • Bewerken/verwijderen van adressen en bestellingen
  • Verbeterde usability
  • Inzicht in efficiëntie en effectiviteit van beide algoritmes

Uitgangspunten

  • Je werkt in tweetallen en kunt individueel het product toelichten.
  • De routeplanner heeft een vast startpunt (ook eindpunt). De route mag stoppen op het laatste adres.
  • We gebruiken x, y-coördinaten (geen GPS).
  • Houd je aan de PO-regels van informatica

Reflectievragen (kort, individueel inleveren)

  1. Waar faalt Greedy in jullie data en waarom?
  2. Hoe schaalbaar is Brute Force? Zou je dit in productie willen gebruiken?
  3. Welke ontwerpkeuze in de database bleek later handig of onhandig?
  4. Wat zou je als volgende stap verbeteren en waarom?

Praktische opdracht Uitleg PHP en MySQL