Archief - [ALG]Math Minimaliseren afstand tussen twee punten

.Acku. · 21 mei 2006

Naar een vraag van MilM, die eerder wiskundig was als Java-gericht. Hij heeft ze gweist, ofzo, maar ik verspil iet graag mijn tijd voor niets dus ZOZO:

Het gaat er hem blijkbaar om om een combinaie van Steiner-punten te vinden, volgens http://www.maa.org/mathland/mathland_4_8.html

In mathematical terms, the problem comes down to finding a new point P such that the total length of the straight lines joining P to each one of three given points, A, B, and C, on a plane has the least possible value. P is known as the "Steiner point."

For the case in which the three cities form a triangle (that is, they're not all in a straight line), the solution involves finding a point inside the triangle toward which straight roads can be built from each city. Using elementary geometry, one can show that the angles between the lines AP, BP, and CP in this simple network all turn out to be 120 degrees.

The Steiner problem can be extended to any number of cities (or points) on a plane and even to situations involving obstacles. In general, given n points, the problem is to find a network of lines that connects all the points and has the shortest total length. For four cities, the solution involves locating two Steiner points, but the angles between the roads arriving at these points remain 120 degrees.

Dat komt voor vier punten neer op het vinden van twee punten waar alle hoeken naar drie punten (twee en een ander Steiner) 120 graden zijn: http://www.maa.org/mathland/4_8_figure.gif
Jammer genoeg blijkt dat complexer als het lijkt:

Chang discovered that the optimal solution to the Steiner problem typically no longer involves just a single point. That happens only under exceptional circumstances for certain grids. Instead, the Steiner "point" is an entire line segment or a polygon. Thus, the choice of any point within such a polygon or along such a line segment results in the same total distance.

Als ge daar een goede oplossing voor vindt, vertel het ons

MilM · 21 mei 2006

Het steiner principe had ik ook al opgemerkt.

Ik had mijn vraag gewist omdat ze idd eerder wiskundig gericht is. (en bepaalde delen zitten al ver in mijn achterhoofd

)

Het probleem was voor mensen die niet mee zijn:

je hebt allemaal punten met een gegeven dimensie (bv 2 dimensionaal, dus elk punt heeft dan een x en y waarde)

je hebt een methode om de afstand tussen twee punten te meten (bv de euclidische afstand tussen twee punten)

Nu zou ik in java het punt moeten vinden zodat de som van de afstanden tot dit punt minimaal is.

Dus het minimaliseren van E d(xi,m)

d = teken voor afstand
xi = één van de n punten
m = te zoeken punt

Merci voor uw antwoord trouwens

wlibaers · 21 mei 2006

.Acku. zei:
Dat komt voor vier punten neer op het vinden van twee punten waar alle hoeken naar drie punten (twee en een ander Steiner) 120 graden zijn: http://www.maa.org/mathland/4_8_figure.gif
Jammer genoeg blijkt dat complexer als het lijkt:

Niet noodzakelijk. Wel voor die configuratie van punten natuurlijk, maar de regel is dat de hoek gelijk aan of groter dan 120 graden is. Als die vier punten op eenzelfde lijn liggen bijvoorbeeld zijn de hoeken allemaal 180 graden.

Zoek via Google op "Steiner tree problem" of "Steiner minimal tree problem" en je vindt wel wat artikels. Er zijn blijkbaar programma's die de perfecte oplossing kunnen vinden, maar dan wel door alle combinaties te proberen, en met exponentieel toenemende tijd met het aantal punten.

BuiZe · 21 mei 2006

Het is een NP-compleet probleem, dus al te performant kan de oplossing niet worden.
leuke voorbeeldapplet: http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/SteinerTree/msteinercli.htm

den Acid Burn · 22 mei 2006

een rechte is de kortste afstand tussen 2 punten.
tot zover rijkt mijn wiskunde kennis :unsure:

Archief - [ALG]Math Minimaliseren afstand tussen twee punten

.Acku.

Legacy Member

MilM

Legacy Member

wlibaers

Legacy Member

BuiZe

Legacy Member

den Acid Burn

Legacy Member