Najbardziej optymalne położenie punktu

[adambak]

Mamy dane \(\displaystyle{ n}\) punktów, które rozmieszczamy wzdłuż prostej \(\displaystyle{ OX}\), czyli współrzędna rzędna każdego z nich wynosi \(\displaystyle{ 0}\). Powiedzmy, że znamy współrzędne odcięte każdego z tych punktów, wynoszą one kolejno: \(\displaystyle{ x _{1}, \ x _{2}, \ x _{3}, \ ... \ , x _{n}}\). Problem polega na znalezieniu takiego punktu \(\displaystyle{ x _{0}}\) na osi \(\displaystyle{ OX}\), aby suma odległości od niego do każdego z wyżej wymienionych \(\displaystyle{ n}\) punktów była najmniejsza.. Jak to zrobić? Optymalizujemy więc taką wartość:

\(\displaystyle{ \sum_{i=1}^{n} \left|x _{0}-x _{i} \right|}\)

Czy oczywistym jest fakt że \(\displaystyle{ x _{0}}\) będzie równe któremuś z tych punktów? Intuicja mi podpowiada że tak jest, ale nie potrafię tego udowodnić..

Od razu nasuwa się algorytm o złożoności \(\displaystyle{ O(n^2)}\) jednak to mi nie wystarcza. Jak obciążając pamięć zejść niżej ze złożonością? Jakiś zarys algorytmu?

[abc666]

Można zapuścić wyszukiwanie binarne. Jak już znajdziemy najlepszy punkt to poprawić tylko trochę (bo punkt między tymi danymi może być najlepszy).

[adambak]

nie wydaje mi się żeby to zdało egzamin.. być może po prostu nie rozumiem w jaki sposób dzielić przedział przy binarnym w tej sytuacji..

wiem że rozwiązanie o złożoności \(\displaystyle{ O(n \log n)}\) jest w miarę łatwe (jednak ja nie jestem póki co w stanie go wymyślić, ciągle mi głowę zaśmieca kwadratówka) i daje bardzo dobry czas w tym zadaniu..

[Xitami]

posortować, wybrać środkowy
dla parzystej liczby jest odcinek

[abc666]

Xitami, no właśnie nie bo punkty nie są rozłożone równomiernie. Np. takie

Kod: Zaznacz cały

1 2 3 4 5 6 20

w jaki sposób dzielić przedział przy binarnym w tej sytuacji..

Zaczynasz tak jak napisał Xitami, sortujesz, wybierasz któryś liczysz sumy, potem wybierasz środkowy tam gdzie większa suma itd. działasz cały czas na indeksach. Sumy nie licz za każdym razem od nowa tylko aktualizują wraz z przesuwaniem punktu podziału.

[Zordon]

Da się liniowo, można bez sortowania mieć medianę

[adambak]

Zrobiłem tak jak powiedział Xitami i przeszło z bardzo dobrym czasem. Oczywiście brałem środkowy wyraz za pomocą indeksu. Czyli jednak zawsze to był jeden z tych punktów. Ktoś ma pomysł na wytłumaczenie dlaczego? Strasznie mnie to trapi..

abc666, zaczynam się przekonywać do Twojego rozwiązania, brzmi ciekawie i bardzo mądrze. Nie poprzestanę na tym i spróbuję Twoim sposobem, jednak widzę że trochę pogłówkować będę musiał z tą aktualizacją..

Zordon, brzmi ciekawie, mediana bez sortowania? Jakaś abstrakcja dla mnie ale pomyślę

-- 25 maja 2011, o 13:14 --

ok, znalazłem że do mediany liniowo przyda mi się słynny już problem zwany algorytmem magicznych piątek, zabieram się za lekturę

-- 25 maja 2011, o 13:35 --

po zastanowieniu stwierdzam, że to że szukany punkt jest jednym z danych punktów jest jednak oczywiste - wynika to wprost z definicji mediany, głupio że wcześniej tego nie doczytałem..

[Zordon]

Jak dla mnie to nie jest takie oczywiste, ja sobie to zawsze uzasadniam tak, np. załóżmy że jest nieparzyście wiele elementów: (w kolejności rosnącej)
\(\displaystyle{ a_0,...,a_{2n}}\), środkowy czyli \(\displaystyle{ a_{n}}\) to mediana.
Teraz łączę sobie elementy w pary: pierwszy z ostatnim, drugi z przedostatnim itd. Formalnie: \(\displaystyle{ a_i}\) z \(\displaystyle{ a_{2n-i}}\), mediana jest w parze ze sobą.
Niech koszt elementu \(\displaystyle{ x}\) to suma odleglosci od wszystkich elementów naszego ciągu. Wtedy cały koszt to suma kosztów po wszystkich parach, czyli \(\displaystyle{ |a_i-x|+|a_{2n-i}-x|}\). Zauważmy, że koszt pochodzący od jednej pary jest zawsze \(\displaystyle{ \geq}\) niż \(\displaystyle{ |a_{2n-i}-a_i|}\) i jest równy tyle dokładnie wtedy gdy \(\displaystyle{ x \in [a_i,a_{2n-i}]}\). Zatem optymalnie jest ustawić \(\displaystyle{ x}\) tak, żeby zawsze to było spełnione. I widać, że w nieparzystym przypadku musi być \(\displaystyle{ x=a_n}\). W parzystym to będzie cały przedział pomiędzy dwoma środkowymi.

[adambak]

elegancko.. dziękuję

[Xitami]