Pembulatan untuk meminimalkan jumlah kesalahan dalam jarak berpasangan

Apa yang diketahui tentang kompleksitas masalah berikut:

Diberikan: bilangan rasional . $x_1 < x_2 < \dotso < x_n$
Output: bilangan bulat . $y_1 \le y_2 \le \dotso \le y_n$
Tujuan: kecilkan mana $\sum_{1 \leq i < j \leq n} e (i, j),$ $\sum_{1 \le i < j \le n} e(i,j),$ $e (i, j) = | (y_{j} - y_{i}) - (x_{j} - x_{i}) | .$ $e(i,j) = | (y_j-y_i) - (x_j-x_i)|.$

Yaitu, kami ingin membulatkan bilangan rasional ke bilangan bulat sehingga kami meminimalkan jumlah kesalahan dalam jarak berpasangan. Untuk setiap pasangan kami ingin memiliki jarak bulat sedekat mungkin dengan jarak sebenarnya . $i, j$ $y_j-y_i$ $x_j-x_i$

Motivasi: perjalanan metro yang membosankan, dan poster yang menunjukkan "lokasi" stasiun dengan resolusi satu menit waktu perjalanan. Di sini kita meminimalkan kesalahan yang dilakukan orang jika mereka menggunakan poster untuk mencari waktu perjalanan antara stasiun dan , rata-rata untuk semua pasangan . $i$ $j$ $i<j$

peta rute

(sumber)

Sebagai contoh, di sini kita dapat membaca perkiraan jarak berpasangan berikut ini antara empat stasiun (menggunakan A, B, C, D untuk singkatnya):

A – B ≈ 1 menit, B – C ≈ 2 menit, C – D ≈ 2 menit
A – C ≈ 3 menit, B – D ≈ 4 menit
A – D ≈ 5 menit

Apakah ini perkiraan terbaik? Jika Anda tahu waktu perjalanan yang sebenarnya, dapatkah Anda menemukan solusi yang lebih baik?

Pada awalnya, ini terdengar seperti latihan sederhana dalam pemrograman dinamis, tetapi sekarang tampaknya diperlukan sejumlah pemikiran aktual.

Adakah yang mengenali masalah ini? Atau lihat algoritma pintar untuk menyelesaikannya?

Sunting: Ada beberapa varian alami dari pertanyaan yang telah disebutkan dalam komentar; mari beri mereka beberapa nama:

versi floor / ceil : diperlukan bahwa untuk semua . $y_i \in \{ \lfloor x_i \rfloor, \lceil x_i \rceil \}$ $i$
versi integer : cukup untuk semua . $y_i \in \mathbb{Z}$ $i$
versi monoton : diperlukan . $y_1 \le y_2 \le \dotso \le y_n$
versi non-monoton : kita dapat memiliki untuk . $y_i > y_j$ $i < j$

Pertanyaan awal mempertimbangkan versi bilangan bulat monotonik, tetapi jawaban yang terkait dengan salah satu dari versi ini diterima.

ds.algorithms reference-request optimization Jukka Suomela
sumber

Apakah DP berfungsi untuk kasing saat Anda hanya peduli dengan pengukuran yang berdekatan?

Suresh Venkat

@ SureshVenkat: Sebenarnya, dalam hal ini masalahnya menjadi sangat sederhana: Anda tinggal memilih jarak integral terbaik

untuk setiap

. Artinya, Anda dapat meminimalkan setiap

secara independen.

y_{i} - y_{i - 1}

$y_i - y_{i-1}$

i

$i$

e (i - 1, i)

$e(i-1,i)$

Jukka Suomela

Laporan oleh Estie Arkin ini tampaknya terkait: ams.sunysb.edu/~estie/papers/beautification.pdf Terbukti bahwa meminimalkan jumlah jarak antar-titik yang berbeda dalam output adalah NP-hard. Ini bukan jumlah total dari pergeseran, seperti dalam pertanyaan ini, tetapi mungkin gadget kekerasan dalam laporan dapat menyarankan bukti kekerasan untuk masalah ini.

val

Saya merasa bahwa masalah ini harus dipecahkan dengan menggunakan teknik-teknik terkenal. Mari kita lihat apakah hadiah itu cukup untuk memotivasi orang untuk menyelesaikan ini. :)

Jukka Suomela

@ vzn: Saya tertarik pada kompleksitas komputasi masalah ini. Jika Anda dapat membuktikan bahwa ada pendekatan pencarian lokal polinomial waktu yang dijamin untuk menemukan global optimal, hadiahnya adalah milik Anda.

Jukka Suomela

Jawaban:

BAIK. Algoritma DP tampaknya tidak perlu rumit. Setelah membaca komentar saya pikir ini mungkin menyelesaikan masalah versi Monoton (tapi saya belum memeriksa setiap detail).

Pertama, anggap setiap , di mana adalah bagian integral, adalah bagian fraksional. Asumsikan dibulatkan menjadi , di mana adalah integer nonnegatif (tentu saja secara umum bisa negatif, tetapi kita selalu dapat bergeser sehingga terkecil adalah 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$

Sekarang, pertimbangkan biaya untuk pasangan , saat melakukan pembulatan ini. Biaya seharusnya $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||$

Ungkapannya rumit karena nilai absolutnya. Namun, perhatikan bahwa kita memiliki sifat monoton, sehingga hal-hal di dalam dua nilai absolut batin harus memiliki tanda SAMA. Karena kita memiliki nilai absolut terluar, tidak peduli apa tanda itu, ungkapan yang disederhanakan

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

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

Mulai sekarang kami tidak menganggap solusinya monoton, tetapi sebaliknya, kami mengubah tujuan untuk meminimalkan jumlah istilah di atas untuk semua pasangan. Jika solusi untuk masalah ini adalah monotonik, maka tentu saja itu juga solusi optimal untuk versi monotonik. (Anggap ini sebagai: masalah asli memiliki penalti tak terbatas ketika solusinya tidak monoton, masalah baru memiliki penalti lebih kecil, jika solusi monoton menang bahkan dalam versi baru, itu harus menjadi solusi untuk versi monoton)

Sekarang kita ingin membuktikan, jika , dalam solusi optimal kita harus memiliki . $\{x_i\} > \{x_j\}$ $v_i \ge v_j$

Asumsikan ini tidak benar, bahwa kita memiliki pasangan tetapi . Kami akan menunjukkan bahwa jika kami menukar solusinya menjadi sangat baik. $\{x_i\} > \{x_j\}$ $v_i < v_j$ $v_i$ $v_j$

Pertama kita membandingkan istilah antara dan , di sini sangat jelas bahwa swapping benar-benar lebih baik karena dalam versi non-swap, dan memiliki tanda yang sama, absolut nilai akan menjadi jumlah dari dua nilai absolut. $i$ $j$ $v_i-v_j$ $\{x_j\}-\{x_i\}$

Sekarang untuk apa pun , kami membandingkan jumlah pasangan dan . Artinya, kita perlu membandingkan $k$ $(i,k)$ $(j,k)$

dan $|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\})|$

Gunakan , , , untuk menunjukkan empat hal dalam nilai absolut, jelas bahwa . Juga jelas bahwa . Dengan cembungnya nilai absolut, kita tahu . Ambil jumlah atas semua $A$ $B$ $C$ $D$ $A+B = C+D$ $|A-B| \ge |C-D|$ $|A|+|B| \ge |C|+|D|$ $x_k$ Kita tahu bertukar hanya bisa lebih baik.

Perhatikan bahwa sekarang kita sudah memiliki solusi untuk versi lantai / langit-langit Monoton: harus ada ambang, ketika lebih besar selalu dibulatkan, ketika lebih kecil selalu dibulatkan ke bawah, ketika itu adalah putaran yang sama beberapa ke atas dan beberapa turun, sedangkan kualitas solusi hanya tergantung pada jumlahnya. Kami menghitung semua solusi ini dan memilih yang memiliki fungsi objektif terkecil. (Semua solusi ini harus monoton). $\{x_i\}$

Akhirnya kami ingin pergi ke versi integer monoton masalah. Kami benar-benar dapat membuktikan solusi optimal sama dengan versi lantai / langit-langit Monoton.

Seperti kita mengasumsikan, yang terkecil adalah 0. Grup semua 's menurut mereka ' s, dan memanggil mereka kelompok . Pertama-tama kita harus membuktikan bahwa tidak ada grup kosong, tetapi ini sederhana, jika grup -th kosong, untuk biarkan saja $v_i$ $x_i$ $v_i$ $0,1,2,...,\max\{v_i\}$ $k$ $v_i > k$ $v_i = v_i-1$ . Mudah untuk melihat fungsi objektif selalu membaik (pada dasarnya karena ). $|\{x_i\}-\{x_j\}| < 1$

Sekarang kita akan membuktikan, rata-rata dalam kelompok adalah setidaknya rata-rata dalam kelompok ditambah . Jika ini tidak benar, cukup biarkan untuk semua , perhitungan lagi menunjukkan fungsi objektif membaik. $\{x_i\}$ $k+1$ $\{x_i\}$ $k$ $1/2$ $v_i = v_i-1$ $v_i > k$

Karena rata-rata dalam kisaran , sebenarnya ada paling banyak dua kelompok, yang sesuai dengan versi lantai / ceil. $\{x_i\}$ $[0,1)$

Rong Ge
sumber

Hanya komentar yang panjang ... (mungkin sepele dan / atau salah :)

Jika dan adalah kelipatan persekutuan terkecil dari s, maka kita dapat menyingkirkan rasional: . $x_i = a_i / b_i$ $M$ $b_i$ $x'_i = M*x_i$

If $y_i \in \{ \lceil x_i \rceil, \lfloor x_i \rfloor \}$ (floor,ceil restriction) then we can use binary variables $v_i$ to express $y'_i$ using its distance from $x'_i$ ( $L_i = x'_i - M*\lfloor x_i \rfloor$ or $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$

And the original problem should (?!?) be equivalent to finding the $v_i$ that minimize:

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

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

Marzio De Biasi
sumber

expanding your last summation using the

e^{'} (i, j)

$e'(i,j)$ error fn idea above, could it be shown the optimum is actually just the choice where each binary variable floor/ceil is closer to

x_{n}

$x_n$ ? so that leaves only the case of how to round for

x_{n}

$x_n$ in the form

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

$m_n + {1 \over 2}$ where

m

$m$ is an integer.

vzn

@vzn: I think this is a counterexample. If we round

(0, 1.4, 8.7)

$(0, 1.4, 8.7)$ using rounding

x_{i}

$x_i$ criteria we get

(0, 1, 9)

$(0, 1, 9)$ that has an error of

1.4

$1.4$ , but

(0, 2, 9)

$(0,2,9)$ has an error of

1.2

$1.2$ (the result is the same if we eliminate the rationals multiplying by the LCM).

Marzio De Biasi

ok nevertheless new idea. consider

e^{'} (i, j)

$e'(i,j)$ again. expand the summation. it will reduce to many terms with

v_{i}

$v_i$ and also

v_{i}^{2}

$v_i^2$ . but the latter is equal to

v_{i}

$v_i$ ! therefore it reduces to a problem in the form of minimizing

X * D

$X*D$ where

X

$X$ is a 0/1 row vector and

D

$D$ is a constant column vector. true? then that is trivial, and just select the

X

$X$ such that it is 1 if the corresponding element in

D

$D$ is negative and 0 if it is positive.... QED?

vzn

@vzn: if you use the

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

$((y'_i - y'_j) - (x'_i - x'_j))^2$ error to eliminate the absolute value function, then you get terms like

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

$- 2*D_i * D_j * v_i * v_j$ ; how do you handle them in the minimization?

Marzio De Biasi

oops! you answered before I had a chance to delete that comment after realizing that.. anyway it still seems to reduce to some almost linear matrix optimization problem? also with a term

V * V^{T}

$V * V^T$ where

V

$V$ is a column vector...?

vzn

Another extended comment... Could be wrong.

I'm also considering the case with floor/ceil restrictions, and I'm trying to solve it using dynamic programming (I can't, but maybe it works when the common divisor is small).

Let $\{x_i\}$ be the fractional part of $x_i$ , we consider things from the smallest $\{x_i\}$ to the largest. Suppose the largest is $\{x_k\}$ , and because we are doing dynamic programming we already know "something" (I will explain what this something is) about optimal solution for everything else except $x_k$ .

Now consider the difference in objective function when we round $x_k$ up or down. If originally some $x_i$ is rounded up, then the difference is simply 1 (haven't really checked very carefully but seems like this is the case, it is really important that no matter whether $x_i$ is to the left or right of $x_k$ , the difference is always the same); if originally some $x_i$ is rounded down, then the difference is $2\{x_k\}-2\{x_i\}-1$ . So: we know what decision we should make if the following three quantities are known:

how many things are rounded up
how many things are rounded down
what is the sum of $\{x_i\}$ among those $x_i$ 's that are rounded down

OK, 1 and 2 are essentially the same, we can let f[N, Ndown, Sdown] be the optimal solution for the first N points (when the points are sorted in ascending order of $\{x_i\}$ ), the number of $x_i$ 's rounded down is Ndown, and the sum of $\{x_i\}$ for those that are rounded down is Sdown. Then it is not hard to write out how to go from f[N-1] to f[N].

The problem is of course, Sdown can have exponentially many values. But it works when either the common divisor is small, or we can round everything to a grid point first and get a FPTAS (if the above dynamic program is correct...)

Rong Ge
sumber

Just noticed @Marzio De Biasi 's comment. It is much easier to think about this Dynamic programming using that objective function. Since we are essentially sorting according to

D_{i}

$D_i$ , when we try to consider the final one, all the absolute value disappears. The additional cost is either

\sum D_{i} v_{i}

$\sum D_iv_i$ or

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

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

Rong Ge

D_{i}

$D_i$ 's does not have to be positive. But that can also be handled. We only need to tell the difference between

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

$\sum |D_i v_i|$ and

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$ . Ndown is the number of previous

v_{j}

$v_j$ 's that are equal to 0, Nup is the number of previous

v_{j}

$v_j$ 's equal to 1.

Rong Ge

This looks promising, but I think there are some further difficulties if the input values are too close to each other. Consider e.g.

x_{i} = 1.1

$x_i = 1.1$ and

x_{k} = 1.9

$x_k = 1.9$ . Now if we could have

x_{i}

$x_i$ rounded up and

x_{k}

$x_k$ rounded down, we would no longer have the nice property that the error changes by precisely 1 depending on whether

x_{k}

$x_k$ is rounded up or down. On the other hand, if we forbid a rounding that changes the order of the points (as I have in the original question), then it seems that we need to keep track of possible roundings that are still available in the dynamic program; can we do that?

Jukka Suomela

@Jukka Suomela, After I saw your comment, I realized that we should never let something with larger

{x_{i}}

$\{x_i\}$ be rounded down while something with smaller

{x_{i}}

$\{x_i\}$ be rounded up. This can be proved if you examine all the cases. Then the answer to the problem (with round restrictions) is clear: there must be a threshold, above the threshold you should round up, below you should round down, at the threshold maybe some should be round up and some down but the quality only depend on the number. These solutions can be easily enumerated.

Rong Ge

By examine all the cases I mean, suppose

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

$\{x_i\} < \{x_j\}$ , think of another

{x_{k}}

$\{x_k\}$ in one of the three regions split by

{x_{i}}

$\{x_i\}$ and

{x_{j}}

$\{x_j\}$ , and

{x_{k}}

$\{x_k\}$ is either rounded up or down. In all of the 6 cases rounding

x_{i}

$x_i$ down and

x_{j}

$x_j$ up is never worse than rounding

x_{j}

$x_j$ down and

x_{i}

$x_i$ up.

Rong Ge