Meminimalkan variasi total dari urutan pilihan diskrit

Setup saya adalah sesuatu seperti ini: Saya memiliki serangkaian set integer $C_i (1\leq i\leq n)$, dengan $|C_i|$ relatif kecil - pada urutan empat atau lima item untuk semua $i$. Saya ingin memilih urutan$x_i (1\leq i\leq n)$ dengan masing-masing $x_i\in C_i$ sedemikian rupa sehingga total variasi (baik $\ell_1$ atau $\ell_2$yaitu $\sum_{i=1}^{n-1} |x_i-x_{i+1}|$ atau $\sum_{i=1}^{n-1} \left(x_i-x_{i+1}\right)^2$) diminimalkan. Sementara sepertinya pilihan untuk masing-masing$x_i$ bersifat 'lokal', masalahnya adalah bahwa pilihan dapat menyebar dan memiliki efek non-lokal sehingga masalah tersebut tampaknya bersifat global.

Perhatian utama saya adalah algoritma praktis untuk masalah ini; saat ini saya menggunakan metode anil berdasarkan mutasi singkat, dan sementara mereka seharusnya baik-baik saja sepertinya saya harus dapat melakukan lebih baik. Tapi saya juga tertarik pada kompleksitas abstrak - firasat saya adalah bahwa versi permintaan standar ('apakah ada solusi variasi total$\leq k$? ') akan menjadi NP-lengkap melalui pengurangan dari beberapa masalah kendala seperti 3-SAT tapi saya tidak bisa melihat pengurangannya. Petunjuk apa pun untuk studi sebelumnya akan disambut baik - sepertinya masalah alami yang saya tidak percaya itu belum pernah dilihat sebelumnya, tetapi pencarian saya sejauh ini belum menemukan sesuatu yang seperti itu.

Ini adalah program yang dinamis. Asumsikan bahwa$C_i = \{C_{i_1}, \ldots, C_{i_m}\}$ untuk semua $i \in [n]$demi kejelasan; berikut ini dapat disesuaikan untuk bekerja jika$C_i$memiliki kardinalitas yang berbeda. Membiarkan$\operatorname{Cost}(i, j)$ menjadi biaya minimum dari urutan di atas yang pertama $i$ set, diakhiri dengan $C_{i_j}$. Rekursi berikut menjelaskan$\operatorname{Cost}$:

$\qquad \displaystyle \begin{align} \operatorname{Cost}(1,j) &= 0 \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad, 1\leq j \leq m \\ \operatorname{Cost}(i,j) &= \min_{k = 1}^m \left(\operatorname{Cost}(i - 1, k) + \lvert C_{(i-1)_k} - C_{i_j} \rvert\right) \ , 2 \leq i \leq n, 1 \leq j \leq m. \end{align}$

Biaya minimum keseluruhan adalah $\min_{j = 1}^m \text{Cost}(n, j)$; urutan pilihan yang sebenarnya dapat ditentukan dengan memeriksa argumen di sepanjang jalan. Runtime adalah$O(nm)$.

Tampaknya ini dapat diselesaikan dengan hanya menghitung jalur terpendek dalam grafik asiklik terarah. Alasannya adalah bahwa fungsi tujuan Anda meminimalkan jarak total antara "tetangga" yang dipilih dalam set Anda$\mathcal{C} = \{C_1, \dotsc, C_n\}$.

Bangun sebuah $n$Grafik -tahap $G = (\bigcup_{i=1}^n V_i, E)$ dimana masing-masing $v \in V_i$ sesuai dengan elemen unik $x \in C_i$. Untuk setiap$u \in V_i, v \in V_{i+1}$, tambahkan tepi terarah $(u, v)$ biaya menjadi $\ell_1$ atau $\ell_2$ jarak.

Sekarang tambahkan sumber simpul $s$ dengan tepi 0-biaya untuk $V_1$ dan simpul wastafel $t$ dengan tepi 0-biaya dari $V_n$. Mengingat bahwa$G$ adalah DAG dan kedua fungsi jarak memaksa biaya ujung menjadi non-negatif, Anda dapat menghitung jalur terpendek dalam $O(V + E)$dengan pengurutan topologi dan pemrograman dinamis (mirip dengan uraian di sini ).