WisFaq!

Routes handelsreizigersprobleem

Als ik in een bepaalde woonplaats van 20 vierkante meter, 8 punten evenredig verdeeld heb, en ik moet deze met de auto allemaal bezoeken (kortste route), hoe lang wordt deze route dan?
- Is dat √(S/N) · (N-1), met S = opp, N = demand punten?
- En wat is de factor die ik moet gebruiken als het gaat om omrijden?

S.Meijer
13-7-2014

Antwoord

Hallo, Sanne!

Die formule ken ik niet, maar met acht punten kun je de kortste route nog wel vinden met een pascalprogramma waarvan de kern hierna schematisch wordt weergegeven:

minimum:=1000000;
for k1:=1 to 8 do
for k2:=1 to 8 do if not(k2=k1) then
for k3:=1 to 8 do if not((k3=k1) or (k3=k2)) then
for k4:=1 to 8 do if not(....
....
for k8:=1 to 8 do if not((k8=k1) or (k8=k2) or ... (k8=k7)) then
begin
som:=sqrt((x[k2]-x[k1])*(x[k2]-x[k1])+(y[k2]-y[k1])*(y[k2-y[k1]))+
sqrt((x[k3]-x[k2])*(x[k3]-x[k2])+(y[k3]-y[k2])*(y[k3]-y[k2]))+ .... +
sqrt((x[k8]-x[k7])*(x[k8]-x[k7])+(y[k8]-y[k7])*(y[k8]-y[k7]));
if som$<$minimum then begin minimum:=som; writeln(k1:2,k2:2,...,k8:2,minimum) end
end

Dan moet je de gebruiker of het programma wel nog eerst de coördinaten van de acht punten laten invoeren.

Succes ermee.

hr
18-7-2014