naastebuurprincipe =>wiskunde A1 PO

[joosjuhhh]

Hai!
voor wiskunde moeten wij een praktische opdracht maken over het handelsreizigersprobleem. Daarbij moeten we ook weten wat het naastebuurprincipe is. Daarover is alleen heel weinig te vinden op het internet. Ik hoop dat iemand me kan vertellen wat dit principe inhoud.
thnxxx anyway. kus, jose
meel me maar : prettiggestoordt@hotmail.com

[*maai*]

Het naastebuurprincipe: een stuk gebied behoort tot dat punt waar hij het dichtste bij ligt. De grenslijnen tussen de stukken worden conflictlijnen genoemd. De figuur die ontstaat door een vlak te verdelen volgens het naastebuurprincipe heet een Voronoi-diagram. De gegeven punten heten centra, en hun gebieden zijn de Voronoi-cellen.

[Joostx]

joosjuhhh schreef op 23-05-2003 @ 20:47:
Hai!
voor wiskunde moeten wij een praktische opdracht maken over het handelsreizigersprobleem. Daarbij moeten we ook weten wat het naastebuurprincipe is. Daarover is alleen heel weinig te vinden op het internet. Ik hoop dat iemand me kan vertellen wat dit principe inhoud.
thnxxx anyway. kus, jose
meel me maar : prettiggestoordt@hotmail.com

Naaste buur of "nearest neighbour" betekent dat je vanuit een bepaalde plaats gaat rezien naar de plaats die het dichtste bij ligt. Dit is een principe dat je kunt gebruiken om een tour te maken langs alle steden en weer te eindigen bij je beginpunt.

Dit principe levert overigens niet automatisch de kortste route op, want door keuzes in het begin kunnen latere keuzes wel eens gedwongen voor grote af te leggen afstanden zorgen.

Je kunt hierop allerlei varianten bedenken, die mogelijk zelfs een beter resultaat opleveren. De enige variant die echt de kortste route geeft is alle verschillende mogelijkheden uit proberen.
Een voorbeeldje: Stel je hebt 3 plaatsen, A,B, en C dan bereken je:

ABCA
ACBA
BACB
BCAB
CABC
CBAC

3 plaatsen levert 6 mogelijke routes ( 3! )
Heb je dus 25 plaatsen dan heb je 25! = 1.551121004...x 10^25 mogelijkheden.
Je begrijpt het al, voor ieder realistisch probleem is het niet reeel om dit te onderzoeken, vandaar dat er allemaal zogenaamde principes en heuristieken (gezond verstand methodes) worden gebruikt.

Succes,

Joostx