Zaokrąglanie w celu zminimalizowania sumy błędów w odległościach parami

Co wiadomo na temat złożoności następującego problemu:

Biorąc pod uwagę: liczby wymierne $x_1 < x_2 < \dotso < x_n$ .
Wyjście: liczby całkowite $y_1 \le y_2 \le \dotso \le y_n$ .
Cel: zminimalizować $\sum_{1 \leq i < j \leq n} e (i, j),$ $\sum_{1 \le i < j \le n} e(i,j),$ gdzie $e (i, j) = | (y_{j} - y_{i}) - (x_{j} - x_{i}) | .$ $e(i,j) = | (y_j-y_i) - (x_j-x_i)|.$

Oznacza to, że chcielibyśmy zaokrąglić liczby wymierne do liczb całkowitych, aby zminimalizować sumę błędów w odległościach parowych. Dla każdej pary $i, j$ chcielibyśmy mieć zaokrągloną odległość $y_j-y_i$ możliwie najbliższą rzeczywistej odległości $x_j-x_i$ .

Motywacja: nudna podróż metrem i plakat przedstawiający „lokalizacje” stacji w rozdzielczości jednej minuty podróży. Tutaj minimalizujemy błąd popełniany przez ludzi, którzy używają plakatu do wyszukiwania czasu podróży między stacjami $i$ i $j$ , uśredniając dla wszystkich par $i<j$ .

Mapa trasy

(źródło)

Na przykład tutaj możemy odczytać następujące przybliżenia odległości parami między czterema stacjami (używając zwięzłości A, B, C, D):

A – B ≈ 1 minuta, B – C ≈ 2 minuty, C – D ≈ 2 minuty
A – C ≈ 3 minuty, B – D ≈ 4 minuty
A – D ≈ 5 minut

Czy to najlepsze możliwe przybliżenie? Jeśli znasz rzeczywisty czas podróży, czy możesz znaleźć lepsze rozwiązanie?

Na początku wydawało się to prostym ćwiczeniem w programowaniu dynamicznym, ale teraz wydaje się, że potrzebne jest trochę myślenia.

Czy ktoś rozpoznaje ten problem? Lub zobaczyć sprytny algorytm do jego rozwiązania?

Edycja: Istnieje kilka naturalnych wariantów pytania, które zostały wspomniane w komentarzach; nadajmy im kilka nazw:

wersja podłogowa / sufitowa : wymagane jest, aby dla wszystkich . $y_i \in \{ \lfloor x_i \rfloor, \lceil x_i \rceil \}$ $i$
wersja całkowita : wystarczy, że dla wszystkich . $y_i \in \mathbb{Z}$ $i$
wersja monotoniczna : wymagane jest, aby . $y_1 \le y_2 \le \dotso \le y_n$
wersja niemonotoniczna : możemy mieć dla . $y_i > y_j$ $i < j$

Oryginalne pytanie dotyczy monotonicznej liczby całkowitej, ale mile widziane są odpowiedzi dotyczące dowolnej z tych wersji.

ds.algorithms reference-request optimization

— Jukka Suomela
źródło

Czy DP działa w przypadku, gdy zależy Ci tylko na sąsiednich pomiarach?

— Suresh Venkat

@SureshVenkat: Właściwie w takim przypadku problem staje się bardzo prosty: wystarczy wybrać najlepszą całkowitą odległość

dla każdego

. Oznacza to, że można zminimalizować każdy

niezależnie.

y_{i} - y_{i - 1}

$y_i - y_{i-1}$

i

$i$

e (i - 1, i)

$e(i-1,i)$

— Jukka Suomela,

Ten raport Estie Arkin wydaje się powiązany: ams.sunysb.edu/~estie/papers/beautification.pdf Udowodniono, że minimalizowanie liczby wyraźnych odległości między punktami na wyjściu jest trudne dla NP. To nie jest całkowita suma przesunięć, jak w tych pytaniach, ale może gadżety twardości w raporcie mogą sugerować dowód twardości dla tego problemu.

— val

Mam wrażenie, że ten problem z pewnością można rozwiązać za pomocą dobrze znanych technik. Zobaczmy, czy nagroda wystarcza, aby zmotywować ludzi do rozwiązania tego problemu. :)

— Jukka Suomela

@vzn: Interesuje mnie złożoność obliczeniowa tego problemu. Jeśli możesz udowodnić, że istnieje metoda wyszukiwania lokalnego w czasie wielomianowym, która gwarantuje znalezienie globalnego optimum, nagroda jest twoja.

— Jukka Suomela

Odpowiedzi:

DOBRZE. Algorytm DP wydaje się niepotrzebnie skomplikowany. Po przeczytaniu komentarzy myślę, że może to rozwiązać monotoniczną wersję problemu (ale nie sprawdziłem każdego szczegółu).

Najpierw załóżmy, że każdy , gdzie jest częścią integralną, jest częścią ułamkową. Załóżmy, że jest zaokrąglone do , gdzie jest nieujemną liczbą całkowitą (oczywiście ogólnie może być ujemna, ale zawsze możemy przesunąć tak, aby najmniejsza wynosiła 0). $x_i = \lfloor x_i\rfloor +\{x_i\}$ $\lfloor x_i\rfloor$ $\{x_i\}$ $x_i$ $\lfloor x_i \rfloor + v_i$ $v_i$ $v_i$ $v_i$

Teraz weź pod uwagę koszt pary , podczas wykonywania tego zaokrąglania. Koszt powinien wynosić $x_i$ $x_j$

| | v_{i} - v_{j} + ⌊ x_{i} ⌋ - ⌊ x_{j} ⌋ | - | {x_{i}} - {x_{j}} + ⌊ x_{i} ⌋ - ⌊ x_{j} ⌋ | |

$||v_i-v_j+ \lfloor x_i\rfloor - \lfloor x_j\rfloor| - |\{x_i\}-\{x_j\} + \lfloor x_i\rfloor - \lfloor x_j\rfloor||$

Wyrażenie jest skomplikowane ze względu na wartości bezwzględne. Zauważ jednak, że mamy monotoniczność, więc rzeczy wewnątrz dwóch wewnętrznych wartości bezwzględnych powinny mieć znak SAM. Ponieważ mamy zewnętrzną wartość bezwzględną, tak naprawdę nie ma znaczenia, czym jest ten znak, wyrażenie to po prostu upraszcza

| v_{i} - v_{j} - ({x_{i}} - {x_{j}}) |

$|v_i-v_j - (\{x_i\} - \{x_j\})|$

Odtąd nie zakładamy, że rozwiązanie jest monotoniczne, ale zamiast tego zmieniamy cel, aby zminimalizować sumę powyższego terminu dla wszystkich par. Jeśli rozwiązanie tego problemu okaże się monotoniczne, to oczywiście jest to również optymalne rozwiązanie dla wersji monotonicznej. (Pomyśl o tym jako: oryginalny problem ma nieskończoną karę, gdy rozwiązanie nie jest monotoniczne, nowy problem ma mniejszą karę, jeśli rozwiązanie monotoniczne wygrywa nawet w nowej wersji, musi to być rozwiązanie monotonicznej wersji)

Teraz chcielibyśmy udowodnić, że jeśli , w optymalnym rozwiązaniu musimy mieć . $\{x_i\} > \{x_j\}$ $v_i \ge v_j$

Załóżmy, że to nieprawda, że mamy parę ale . Pokażemy, że jeśli zamienimy rozwiązanie stanie się zdecydowanie lepsze. $\{x_i\} > \{x_j\}$ $v_i < v_j$ $v_i$ $v_j$

Najpierw porównujemy termin między i , tutaj jest naprawdę jasne, że zamiana jest zdecydowanie lepsza, ponieważ w wersji bez zamiany, i ma ten sam znak, absolut wartość będzie sumą dwóch wartości bezwzględnych. $i$ $j$ $v_i-v_j$ $\{x_j\}-\{x_i\}$

Teraz dla dowolnego porównujemy sumę par i . Oznacza to, że musimy porównać $k$ $(i,k)$ $(j,k)$

i $|v_i-v_k-(\{x_i\}-\{x_k\})|+|v_j-v_k-(\{x_j\}-\{x_k\})|$ . $|v_j-v_k-(\{x_i\}-\{x_k\})|+|v_i-v_k-(\{x_j\}-\{x_k\})|$

Zastosowanie , , , , oznaczające cztery warunki wewnątrz wartości bezwzględnej, to jest oczywiste, że . Jest również jasne, że . Dzięki wypukłości wartości bezwzględnej wiemy . Weź sumę nad wszystkimi $A$ $B$ $C$ $D$ $A+B = C+D$ $|A-B| \ge |C-D|$ $|A|+|B| \ge |C|+|D|$ $x_k$ Wiemy, że zamiana może być tylko lepsza.

Zauważ, że teraz mamy już rozwiązanie dla monotonicznej wersji podłogi / sufitu: musi istnieć próg, gdy jest większy zawsze zaokrągla w górę, gdy jest mniejszy zawsze zaokrągla w dół, gdy jest równy zaokrągla w górę, a niektóre w dół, podczas gdy jakość rozwiązania zależy tylko od liczby. Wymieniamy wszystkie te rozwiązania i wybieramy jedno z najmniejszą funkcją celu. (Wszystkie te rozwiązania są z konieczności monotoniczne). $\{x_i\}$

Na koniec chcielibyśmy przejść do monotonicznej liczby całkowitej problemu. Możemy faktycznie udowodnić, że optymalne rozwiązanie jest takie samo jak wersja monotoniczna podłogi / sufitu.

Ponieważ zakładamy, najmniejsza 0. Grupa wszystkich jest zgodnie z ich 's, które nazywają grupę . Najpierw udowodnimy, że nie ma pustych grup, ale jest to proste, jeśli grupa jest pusta, dla dowolnego po prostu pozwól $v_i$ $x_i$ $v_i$ $0,1,2,...,\max\{v_i\}$ $k$ $v_i > k$ $v_i = v_i-1$ . Łatwo jest zauważyć, że funkcja celu zawsze się poprawia (zasadniczo dlatego, że ). $|\{x_i\}-\{x_j\}| < 1$

Teraz udowodnimy, średnia w grupie jest co najmniej średnią w grupie powiększonej o . Jeśli nie jest to prawdą, po prostu pozwól dla wszystkich , obliczenia ponownie pokazują poprawę funkcji celu. $\{x_i\}$ $k+1$ $\{x_i\}$ $k$ $1/2$ $v_i = v_i-1$ $v_i > k$

Ponieważ średnia mieści się w przedziale , tak naprawdę istnieją co najwyżej dwie grupy, co odpowiada wersji podłoga / sufit. $\{x_i\}$ $[0,1)$

— Rong Ge
źródło

Tylko rozszerzony komentarz ... (może trywialny i / lub zły :)

Jeśli i jest najmniejszą wspólną wielokrotnością S, to możemy pozbyć się rationals: . $x_i = a_i / b_i$ $M$ $b_i$ $x'_i = M*x_i$

Jeżeli (podłoga, ograniczenie ceil), następnie można użyć zmiennych binarnych wyrazić za pomocą jego odległości od ( lub $y_i \in \{ \lceil x_i \rceil, \lfloor x_i \rfloor \}$ $v_i$ $y'_i$ $x'_i$ $L_i = x'_i - M*\lfloor x_i \rfloor$ $R_i = x'_i - M*\lceil x_i \rceil$ ):

$y'_i = x'_i + L_i * v_i + R_i * (1 - v_i) = x'_i + (L_i - R_i)*v_i + R_i = x'_i + D_i *v_i + R_i$

Pierwotny problem powinien (?!?) Być równoważny ze znalezieniem minimalizujących: $v_i$

$\sum_{1 \le i < j \leq n} | D_i * v_i - D_j * v_j |$

z $v_i \in \{0,1\}, D_i \in \mathbb{Z}$

— Marzio De Biasi
źródło

rozszerzając swoje ostatnie podsumowanie za pomocą powyższego pomysłu błędu

, czy można wykazać, że optymalne jest właściwie tylko wyborem, w którym każda zmienna binarna podłoga / sufit jest bliższa

? tak więc pozostawia jedynie przypadek zaokrąglenia dla

w postaci

e^{'} (i, j)

$e'(i,j)$

x_{n}

$x_n$

x_{n}

$x_n$

gdzie

jest liczbą całkowitą.

m_{n} + \frac{1}{2}

$m_n + {1 \over 2}$

m

$m$

— vzn

@vzn: Myślę, że to kontrprzykład. Jeśli zaokrąglimy

za pomocą kryteriów zaokrąglania

otrzymamy

który ma błąd

, ale

ma błąd

(wynik jest taki sam jeśli wyeliminujemy mnożniki racjonalne przez LCM).

(0, 1.4, 8.7)

$(0, 1.4, 8.7)$

x_{i}

$x_i$

(0, 1, 9)

$(0, 1, 9)$

1.4

$1.4$

(0, 2, 9)

$(0,2,9)$

1.2

$1.2$

— Marzio De Biasi,

ok, jednak nowy pomysł. ponownie rozważ

. rozwiń podsumowanie. zmniejszy się do wielu warunków z

a także

. ale ten ostatni jest równy

! dlatego sprowadza się do problemu w postaci minimalizacji

gdzie

jest wektorem wiersza 0/1, a

jest wektorem stałej kolumny . prawdziwe? to jest trywialne i po prostu wybierz

tak, aby wynosił 1, jeśli odpowiedni element w

e^{'} (i, j)

$e'(i,j)$

v_{i}

$v_i$

v_{i}^{2}

$v_i^2$

v_{i}

$v_i$

X * D

$X*D$

X

$X$

D

$D$

X

$X$

D

$D$ jest ujemny i 0, jeśli jest dodatni .... QED?

— vzn

@vzn: jeśli użyjesz błędu

aby wyeliminować funkcję wartości bezwzględnej, otrzymasz wyrażenia takie jak

; jak sobie z nimi radzić w minimalizacji?

((y_{i}^{'} - y_{j}^{'}) - (x_{i}^{'} - x_{j}^{'}))^{2}

$((y'_i - y'_j) - (x'_i - x'_j))^2$

- 2 * D_{i} * D_{j} * v_{i} * v_{j}

$- 2*D_i * D_j * v_i * v_j$

— Marzio De Biasi

ups! odpowiedziałeś, zanim zdążyłem usunąć ten komentarz, gdy zdałem sobie sprawę, że… w każdym razie nadal wydaje się, że sprowadza się on do prawie liniowego problemu optymalizacji macierzy? również z terminem

gdzie

jest wektorem kolumny ...?

V * V^{T}

$V * V^T$

V

$V$

— vzn

Kolejny rozszerzony komentarz ... Może się mylić.

Rozważam również przypadek z ograniczeniami podłogi / sufitu i próbuję go rozwiązać za pomocą programowania dynamicznego (nie mogę, ale może to działa, gdy wspólny dzielnik jest mały).

Niech będzie ułamkową częścią , rozważamy rzeczy od najmniejszej do największej. Załóżmy, że największy jest , a ponieważ robimy programowania dynamicznego wiemy już „coś” (I wyjaśni, co to coś jest) o optymalnych rozwiązań dla wszystkiego z wyjątkiem . $\{x_i\}$ $x_i$ $\{x_i\}$ $\{x_k\}$ $x_k$

$x_k$ $x_i$ $x_i$ $x_k$ $x_i$ $2\{x_k\}-2\{x_i\}-1$ . Tak więc: wiemy, jaką decyzję powinniśmy podjąć, jeśli znane są następujące trzy ilości:

ile rzeczy jest zaokrąglonych w górę
ile rzeczy jest zaokrąglonych w dół
$\{x_i\}$ $x_i$

$\{x_i\}$ $x_i$ $\{x_i\}$

Problem polega oczywiście na tym, że Sdown może mieć wykładniczo wiele wartości. Ale działa, gdy wspólny dzielnik jest mały, lub możemy najpierw zaokrąglić wszystko do punktu siatki i uzyskać FPTAS (jeśli powyższy program dynamiczny jest poprawny ...)

— Rong Ge
źródło

D_{i}

$D_i$

\sum D_{i} v_{i}

$\sum D_iv_i$

(N - 1) D_{k} - \sum D_{i} v_{i}

$(N-1) D_k - \sum D_iv_i$

D_{i}

$D_i$

\sum | D_{i} v_{i} |

$\sum |D_i v_i|$

N d o w n | D_{k} | + N u p D_{k} - \sum D_{i} v_{i}

$Ndown|D_k| + Nup D_k - \sum D_iv_i$

v_{j}

$v_j$

v_{j}

$v_j$

x_{i} = 1.1

$x_i = 1.1$

x_{k} = 1.9

$x_k = 1.9$

x_{i}

$x_i$

x_{k}

$x_k$

x_{k}

$x_k$

— Jukka Suomela

{x_{i}}

$\{x_i\}$

{x_{i}}

$\{x_i\}$

{x_{i}} < {x_{j}}

$\{x_i\} < \{x_j\}$

{x_{k}}

$\{x_k\}$

{x_{i}}

$\{x_i\}$

{x_{j}}

$\{x_j\}$

{x_{k}}

$\{x_k\}$

x_{i}

$x_i$

x_{j}

$x_j$

x_{j}

$x_j$

x_{i}

$x_i$

— Rong Ge