/ / Najkrótsza odległość - wspólny punkt spotkania - algorytm, wykres, macierz

Najkrótsza odległość - wspólny punkt spotkania - algorytm, wykres, macierz

Natknąłem się na ten problem, w którym jestliczba domów na siatce 2-D (podane są współrzędne) i zasadniczo musimy ustalić, który dom może zostać wykorzystany jako miejsce spotkań, tak aby odległość przebyta przez wszystkich zminimalizowała się. Załóżmy, że odległość wzdłuż osi X lub Y przyjmuje 1 jednostkę, a odległość do diagonalnych sąsiadów wynosi (na przykład) 1,2 jednostki.

Nie mogę tak naprawdę wymyślić dobrego algorytmu optymalizacji.

P.S: Nie jest to zadanie domowe. I szukam tylko algorytmu (nie kodu) i jeśli to możliwe, jego dowodu.

P.S # 2: Nie szukam Wyczerpującego rozwiązania. Wierzcie lub nie, to mnie uderzyło :)

Odpowiedzi:

7 dla odpowiedzi № 1

Jak już wskazano, w przypadku odległości Manhattanu mediana daje rozwiązanie. Jest to oczywisty wniosek z dobrze znanego faktu, że mediana minimalizuje średnią bezwzględnego odchylenia:

E|X-c| >= E|X-median(X)| dla każdej stałej c.

I tutaj możesz znaleźć przykład dowodu na dyskretny przypadek:
https://stats.stackexchange.com/questions/7307/mean-and-median-properties/7315#7315


3 dla odpowiedzi № 2

Prawdopodobnie jest to naprawdę nieefektywne, ale przeprowadź pętlę przez wszystkie domy, a następnie przeprowadź pętlę przez wszystkie pozostałe domy. (zagnieżdżone dla pętli) Użyj formuła odległości znaleźć odległość między 2 domami. Wtedy masz odległość między każdym domem. Jednym z szybkich i łatwych sposobów znalezienia najbliższego domu jest dodanie odległości dla każdego domu, a najmniejszy dystans to powierzchnia spotkania.


3 dla odpowiedzi nr 3

Twój metryczny dystans jest dziwny. Spodziewałbyś się, że podróż po przekątnej powinna zająć co najmniej sqrt (2) ~ = 1,41 razy odległość podróży wzdłuż kierunku komponentu, ponieważ jest to o ile dalej, jeśli podróżujesz w linii prostej wzdłuż przekątnej przez Twierdzenie Pitagorasa.

Jeśli nalegałeś na odległości w kierunku manhattanu (bez dozwolonych przekątnych), to chcesz wybrać dom najbliższy medianie (x) + medianę (y) domów.

Rozważ przypadek 1D, masz kilka punktów na linii i chcesz wybrać miejsce spotkania. Dla konkretności / prostoty, powiedzmy, że jest 5 domów, żadnych duplikatów.

Zastanów się, co się dzieje, gdy spotkanie się przesypujez medianą w prawo. Za każdą jednostkę, dopóki nie przejdziecie od czwartej kolejności od lewej do prawej, 3 osoby muszą wykonać dodatkowy krok w prawo, a 2 osoby muszą wykonać jeden krok mniej w lewo, aby koszt wzrósł o 1. przejść przez czwarty dom, a następnie 4 osoby muszą wykonać dodatkowy krok w prawo, a jedna osoba musi wykonać jeden krok mniej w lewo, aby koszt wzrósł o 3. Identyczna argumentacja dotyczy przeniesienia miejsca spotkania do lewo od mediany. Odejście od mediany zawsze zwiększa koszty.

Argument uogólnia się na dowolną liczbę osób, z duplikatami lub bez, a nawet na dowolną liczbę wymiarów, o ile nie można używać przekątnej.


3 dla odpowiedzi № 4

Dla niektórych mnie problem dotyczył tego samego problemujuż czas. Rozwiązaniem jest oczywisty konsensus podany we wcześniejszych postach: znajdź medianę (mx, moje) niezależnie, a następnie znajdź punkt najbliższy w podanych N punktach i to jest miejsce spotkania. Aby zobaczyć, dlaczego tak naprawdę jest to rozwiązanie, powinieneś najpierw rozważyć odległość.

d = suma (| xi-x |) + suma (| yi-y |) nad wszystkimi 1 <= i <= N,

który jest niezależny wx i y. Dlatego możemy rozwiązać przypadek 1-D dla x i y. Pominę wyjaśnienie podane ^^ i stąd wywnioskuję, że (mx, my) jest najlepszym rozwiązaniem gdyby rozważamy wszystkie możliwe punkty.Największym wyzwaniem jest udowodnienie, że możemy przejść od (mx, my) do najbliższego (xi, yi) takiego, że (xi, yi) jest jednym z podanych punktów, bez zmiany (zwiększenia) odległości. Dowód idzie:

Pomyśl, że posortowaliśmy współrzędne x (dla sake do dowodu) i że X1<X2<...<Xn. Również Xj<mx<X(j+1) gdzie j = N/2, teraz ruszajmy mx od jednego do drugiego mx" <- mx-1. Stąd d" = |X1-mx+1| + .. + |Xj-mx+1| + |X(j+1)-mx+1| + .. + |Xn-mx+1| Wiemy, że mx-1 zwiększy wartości N / 2 (dla k> = j + 1 i zmniejszy dla <= j) stąd efekt jest taki sam. Tak więc (mx-1, mój) daje to samo rozwiązanie. Oznacza to, że jest spacja od Xj<mx<X(j+1) i Yj<my<Y(j+1) gdzie odległość się nie zmienia. W ten sposób możemy znaleźć Najbliższy taki punkt, który jest odpowiedzią.

Zignorowałem subtelny przypadek węzłów parzystych / nieparzystych, ale mam nadzieję, że matematyka wykaże się sama, gdy zdasz sobie sprawę z podstawowego dowodu.

To jest mój pierwszy post, pomóż mi poprawić umiejętności pisania.


1 dla odpowiedzi nr 5

Twój problem nazywa się optymalnym znalezieniem punktu spotkania. Poniższy artykuł podaje skuteczny algorytm przybliżania http://www.cse.ust.hk/~wilfred/paper/vldb11.pdf


0 dla odpowiedzi № 6

Cóż, mógłbyś to brutalnie zmusić. Weź każdy dom i obliczyć odległość do siebie nawzajem. Zsumuj odległości dla każdego domu. Potem złap dom, który ma najniższą sumę.