Stel, je woont in een dorp met een park, een kerk, een café, een supermarkt, een zwembad en een hotel. Sommige van deze punten zijn met elkaar verbonden, andere niet. Dit kunnen we uiteraard weergeven in een graaf.
<aside> 🛠 Opdracht 3.3.1 Is dit een gerichte of een ongerichte graaf?
</aside>
<aside> 🛠 Opdracht 3.3.2 Pas breedte-eerst zoeken toe om uit te zoeken wat het minste aantal straten is om van het park naar het hotel te komen. Welke route of routes kun je allemaal lopen?
</aside>
In het echt gaat het natuurlijk niet altijd om het kortste pad met het minste aantal straten dat je moet lopen, maar om de kortste afstand. Het doel in dit hoofdstuk is om de kortste afstand te vinden van het park naar het hotel.
Hieronder zie je een graaf van het dorp nog een keer. Nu is tussen iedere knoop de afstand weergegeven in meters. Het verschil met de grafen die we tot nu toe hebben gezien, is dat elke zijde voorzien is van een getal. We noemen dit het gewicht van een zijde.
<aside> 🛠 Opdracht 3.3.3 Pak de route(s) die je hebt gevonden met breedte-eerste zoeken er eens bij. Hoe lang is elke route? Kun je een kortere vinden?
</aside>
Er is nog een andere methoden om het kortste-pad te vinden. Naast breedte-eerst zoeken kun je ook vanuit een punt het pad kiezen met de kortste afstand tot het volgende punt. Hierbij moet je er wel op letten dat je niet terugloopt of in een kring loopt.
We noemen deze aanpak gretig (of greedy in het Engels). Dit komt omdat je bij elke stap gretig gebruik maakt van de kortste afstand, zonder vooruit te kijken naar de gevolgen van die beslissing.
<aside> 🛠 Opdracht 3.3.4 Gebruik het gretige algoritme om een route van het park naar het hotel te vinden. Is dit een andere route dan je had gevonden met breedte-eerst zoeken? Welke is beter? Is dit de kortste route die je kunt vinden?
</aside>