Kortste weg langs alle stripmuren

Om de kortste weg te berekenen langs alle stripmuren van Brussel, heb ik een programma ontwikkeld dat algemeen bruikbaar is om de kortste weg te zoeken langs alle klanten van een handelsreiziger, of langs alle bezienswaardigheden van een stad of land. Begin- en eindpunt van de weg zijn zelf te kiezen, en mogen eventueel samenvallen.

Het programma rekent met ingegeven (werkelijke) afstanden, maar toch heeft het geen volledige afstandentabel nodig. Om te beginnen heeft het genoeg aan de geografische coördinaten van elk punt: het rekent dan met afstanden in vogelvlucht, en zegt één na één welke werkelijke afstanden het nodig heeft. Dit is telkens een afstand tussen opeenvolgende punten van de voorlopig kortste weg. Een ingegeven afstand mag nooit korter zijn dan de overeenkomstige afstand in vogelvlucht: dit garandeert dat het ingeven van een afstand geen enkele weg korter kan maken.

De berekening zelf is darwinistisch. Ze volgt de evolutie van een populatie wegen, waarvan de kortste de grootste overlevingskans hebben. Vrij vlug komt het zo tot een weg die waarschijnlijk, hoewel niet gegarandeerd, de allerkortste is.

Hoewel dit niet uitgetest is, zou het programma ook overweg moeten kunnen met asymetrische afstanden (eenrichtingsstraten).

Het programma (in javascript, dat ook de gegevens bevat) wordt opgeroepen door deze pagina:

 


Datum waarop deze pagina laatst werd bijgewerkt: 2016-09-09