Problem Fermat-Weber, jak rozwiązać ?

Tryllion · Post autor: **Tryllion** » 27 lut 2010, o 17:08

Witam

Mam pytanie, w internecie jest bardzo dobrze opracowany problem , punktu którego suma odległości od wierzchołków trójkąta jest najmniejsza z możliwych. Tzw. punkt Fermata.

Ja mam za zadanie rozwiązać ten problem dla wierzchołków>3 , ten problem wiem że można rozwiązać metodą iteracyjną i nie ma dla niego zwykłej algebraicznej metody tzn wzoru.
Jedyne opracowanie jest na wiki angielskiej, którego nie bardzo rozumiem.

Mam prośbę o rozjaśnienie, jak ten problem się rozwiązuje, co należy wykonać w kolejnych krokach ?

ar1 · Post autor: **ar1** » 27 lut 2010, o 18:47

w wikipedii jest przedstawiony Weiszfeld's algorytm który daje coraz to lepsze przybliżenia tego szukanego punktu

bierzemy dowolny punkt \(\displaystyle{ y_{0}}\)
i obliczamy kolejne iteracje \(\displaystyle{ y_{1}, y_{2}, ...}\)
otrzymujemy coraz lepsze przybliżenia

Tryllion · Post autor: **Tryllion** » 27 lut 2010, o 19:33

No tak, ale nie bardzo rozumiem wartości jakie tam są użyte:

\(\displaystyle{ y_{i+1} = \sum_{}^{} ( \frac{ x_{j} }{x_{j}-y_{i}} )/\sum_{}^{} ( \frac{1}{x_{j}-y_{i}} )}\)

Pytanie czym jest y, jaką ma początkową wartość ? Dowolną ? Rozumiem natomiast iż po itej iteracji będzie to odpowiedz. Ale także z tego wnioskuje iż jest to przypadek dla przestrzeni jednowymiarowej, jak zatem obliczyć taki punkt dla punktów w 2 wymiarach ?

I też ten wzór wydaje mi się dziwny, bo dla dużej ilości x ów, łatwo dobrać taki y który da 0 w mianowniku, i error.

ar1 · Post autor: **ar1** » 27 lut 2010, o 19:49

w przestrzeni n -wymiarowej można normalnie sumować wektory i mnożyć(dzielić) przez skalar tam w mianowniku jest norma z różnicy(liczba,skalar)
ten drugi czynnik(ta suma przez którą dzielimy ) to też skalar więc wzór jest poprawnie określony

\(\displaystyle{ y _{0}}\) wybierasz dowolne (i dobierasz tak żeby nie bylo 0 w mianowniku)

Tryllion · Post autor: **Tryllion** » 27 lut 2010, o 20:15

Hmm pomału łapię ale jest to nadal dla mnie czarna magia.
Skalar to wektor jak rozumiem ? "norma z różnicy" ?

Czu mógłbyś mi podstawić do tego wzoru np. punkty A(0,0), B(10,10) ? Tak abym zrozumiał przez analogię ? Naprawdę byłbym wielce wdzięczny, potrzebuję tego rozwiązania, a jestem z matematyki d*pa

ar1 · Post autor: **ar1** » 27 lut 2010, o 20:26

skalar to liczba a nie wektor
norma z wektora to nic innego jak jego długość(liczba)
różnica dwóch wektorów to wektor
A-B=(0-10,0-10)=(-10,-10)
||A-B||=\(\displaystyle{ \sqrt{(-10) ^{2} +(-10) ^{2} } = \sqrt{200} = 10 \sqrt{2}}\)

Tryllion · Post autor: **Tryllion** » 27 lut 2010, o 23:19

Dzięki bardzo , trochę to teraz się rozjaśniło, nie spotkałem się z oznaczeniem dwóch pionowych kresek, przez chwilę myślałem że to może wartość bezwzględna ale to by nie miało sensu, jeszcze raz dzięki, teraz zapis jest czytelny.

Nie jestem pewien czy algorytm działa, obliczyłem na szybko dla 2 punktów, ale jak wiadomo , punkt Fermata może znajdować się w dowolnym miejscu na odcinku który je łączy. Co ciekawe niezależnie od wartości początkowej Y, odpowiedz końcową otrzymywałem tą samą.

Jutro postaram się napisać jakiś sensowny program , zobaczę czy to faktycznie działa dla n>3 pkt.

Jeszcze raz dzięki.