Minimiser la variation totale d'une séquence de choix discrets

Ma configuration est quelque chose comme ceci: j'ai une séquence d'ensembles d'entiers $C_i (1\leq i\leq n)$, avec $|C_i|$ relativement petit - de l'ordre de quatre ou cinq articles pour tous $i$. Je veux choisir une séquence$x_i (1\leq i\leq n)$ avec chaque $x_i\in C_i$ de telle sorte que la variation totale (soit $\ell_1$ ou $\ell_2$, c'est à dire $\sum_{i=1}^{n-1} |x_i-x_{i+1}|$ ou $\sum_{i=1}^{n-1} \left(x_i-x_{i+1}\right)^2$) est minimisé. Bien qu'il semble que le choix pour chaque$x_i$ est «local», le problème est que les choix peuvent se propager et avoir des effets non locaux et donc le problème semble intrinsèquement mondial par nature.

Ma principale préoccupation est dans un algorithme pratique pour le problème; en ce moment, j'utilise des méthodes de recuit basées sur la mutation de courtes sous-séquences, et bien qu'elles devraient être correctes, il semble que je devrais pouvoir faire mieux. Mais je suis également intéressé par la complexité abstraite - mon intuition serait que la version de requête standard ('existe-t-il une solution de variation totale$\leq k$? ') serait NP-complet via une réduction d'un problème de contrainte comme 3-SAT mais je ne vois pas vraiment la réduction. Tout pointeur sur une étude précédente serait le bienvenu - cela semble être un problème si naturel que je ne peux pas croire qu'il n'ait pas été examiné auparavant, mais mes recherches n'ont jusqu'à présent rien trouvé de tel.

Voici un programme dynamique. Suppose que$C_i = \{C_{i_1}, \ldots, C_{i_m}\}$ pour tous $i \in [n]$pour plus de clarté; ce qui suit peut être adapté au travail si le$C_i$ont des cardinalités différentes. Laisser$\operatorname{Cost}(i, j)$ être le coût minimum d'une séquence sur le premier $i$ ensembles, se terminant par $C_{i_j}$. La récursivité suivante décrit$\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}$

Le coût minimum global est $\min_{j = 1}^m \text{Cost}(n, j)$; l'ordre réel des choix peut être déterminé en examinant les argmins en cours de route. Le runtime est$O(nm)$.

Il semble que cela puisse être résolu en calculant simplement le chemin le plus court dans un graphique acyclique dirigé. Le raisonnement est que votre fonction objectif minimise la distance totale entre les "voisins" sélectionnés dans vos ensembles$\mathcal{C} = \{C_1, \dotsc, C_n\}$.

Construire un $n$graphique en plusieurs étapes $G = (\bigcup_{i=1}^n V_i, E)$ où chacun $v \in V_i$ correspond à un élément unique $x \in C_i$. Pour chaque$u \in V_i, v \in V_{i+1}$, ajoutez un bord dirigé $(u, v)$ le coût étant soit le $\ell_1$ ou $\ell_2$ distance.

Ajoutez maintenant un sommet source $s$ avec des bords à 0 $V_1$ et un sommet d'évier $t$ avec des bords à 0 coût de $V_n$. Étant donné que$G$ est un DAG et les deux fonctions de distance forcent les coûts de bord à être non négatifs, vous pouvez calculer le chemin le plus court dans $O(V + E)$avec tri topologique et programmation dynamique (similaire à la description ici ).