Najkrótsza droga przebicia - wspólne miejsce zbiórki

Question

Natknąłem się na ten problem, w którym liczba domów na siatce 2-D (ich współrzędne są podane) i zasadniczo musimy znaleźć dom, który można wykorzystać jako miejsce spotkań, odległość przebyta przez wszystkich zminimalizuje 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ę 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 :)

Answer 1

To chyba naprawdę mało wydajne, ale przechodzimy przez wszystkie domy, a następnie przechodzimy przez wszystkie pozostałe domy. (zagnieżdżone dla pętli) Użyj numeru distance formula, aby znaleźć odległość między dwoma domami. Wtedy masz odległość między każdym domem. Jednym szybkim i łatwym sposobem znalezienia domu, który znajduje się najbliżej, jest dodanie do danego domu odległości dla wszystkich osób. Dom o najmniejszej odległości do pokonania to wybrany obszar spotkań.

Answer 2

Cóż, możesz go 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ę.

Answer 3

Dane dotyczące odległości są dziwne. Można się spodziewać, że podróż po przekątnej powinna zająć co najmniej sqrt (2) ~ = 1,41 razy odległość podróżowania wzdłuż kierunku komponentu, ponieważ o tyle dalej, jeśli podróżujemy w linii prostej wzdłuż przekątnej według twierdzenia Pitagorasa .

Jeśli nalegali Państwo na odległość w kierunku Manhattanu (bez dozwolonych przekątnych), chcielibyście wybrać dom najbliższy medianie (x) + mediana (y) domów.

Weź pod uwagę 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 miejsce spotkania przesuwa się z mediany 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 nich, a nawet na dowolną liczbę wymiarów, o ile nie można używać przekątnej.

Answer 4

Jak już wskazano, w przypadku odległości Manhattan 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 dowolnej stałej c.

i tutaj można znaleźć przykład dowód na dyskretną przypadku:
https://stats.stackexchange.com/questions/7307/mean-and-median-properties/7315#7315

Answer 5

I zostały podsłuchu przez ten sam problem już od jakiegoś czasu. 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 |) 1 w stosunku do wszystkich < < = i = N

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

Weź pod uwagę, że mamy posortowane współrzędne x (dla sake do dowodu) i , że X1<X2<...<Xn. Również , gdzie j = N/2, teraz przesuńmy się o jeden krok w lewo, czyli mx , czyli 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), dlatego efekt jest taki sam. Tak więc (mx-1, mój) daje to samo rozwiązanie . Oznacza to, że istnieje przestrzeń od Xj<mx<X(j+1) i Yj<my<Y(j+1), w której odległość się nie zmienia. W ten sposób możemy znaleźć najbliższy taki punkt, który jest odpowiedzią.

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

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

Answer 6

Twój problem nazywa się optymalnym znalezieniem punktu spotkania. Następujący artykuł podaje efektywny algorytm przybliżony. http://www.cse.ust.hk/~wilfred/paper/vldb11.pdf