Routes in een rooster

Stel dat de punten niet op de kruispunten staan, maar in het midden van de vakjes. De kruispunten krijgen dan coordinaten (1:1 voor het eerste vakje etc). Stel dat je ook diagonaal mag lopen. Welke formule kan ik loslaten op een reeks om de kortste afstand te berekenen?

Ik ben al weken aan het puzzelen, natuurlijk snap ik het principe van de stelling van Pythagoras om de afstand te berekenen, en ik weet ook dat ik met 4! het aantal mogelije routes uitreken als ik maar 4 coordinaten heb, maar ik kom niet tot een formule voor de kortste route

Klein stukje van mijn coordinatenreeks:

101:43,103:42,102:44,101:45,102:46,103:46,103:47

Sonja
Iets anders - zondag 3 juni 2018

Antwoord

Je maakt niet echt duidelijk wat nu het probleem is; het volgende is gebaseerd op raadwerk. Uit je bijlage denk ik te begrijpen dat je een route langs alle A-tjes in de tabel moet plannen die zo kort mogelijk is. Wat niet duidelijk wordt, ook niet uit de vraag zelf is of er beperkingen aan de manier van reizen zijn opgelegd. Uit "Stel dat je ook diagonaal mag lopen." maak ik op dat niet alles mag, maar wat dan wel mag staat er niet.

Hoe dan ook, dit klinkt als het Handelsreizigerprobleem (de Engelstalige versie is uitgebreider).

Dat probleem is, zoals je zult lezen, niet met een eenvoudige formule op te lossen; het is zelfs zo dat men nog niet weet of er een efficiënt algoritme voor is (je kunt er een miljoen dollar mee verdienen).

Op de wikipediapagina staan wel wat algoritmen genoemd, die zou je eens kunnen bekijken.

kphart
vrijdag 20 juli 2018

©2001-2024 WisFaq