Minimizar a variação total de uma sequência de escolhas discretas

Minha configuração é mais ou menos assim: eu tenho uma sequência de conjuntos de números inteiros , comrelativamente pequeno - na ordem de quatro ou cinco itens para todos . Quero escolher uma sequência com cada modo que a variação total ( ou , ou seja, ou ) é minimizado. Embora pareça que a escolha para cada seja 'local', o problema é que as escolhas podem se propagar e ter efeitos não locais e, portanto, o problema parece inerentemente global por natureza.$C_i (1\leq i\leq n)$$|C_i|$$i$$x_i (1\leq i\leq n)$$x_i\in C_i$$\ell_1$$\ell_2$$\sum_{i=1}^{n-1} |x_i-x_{i+1}|$$\sum_{i=1}^{n-1} \left(x_i-x_{i+1}\right)^2$$x_i$

Minha principal preocupação está em um algoritmo prático para o problema; No momento, estou usando métodos de recozimento baseados em mutações subseqüentes curtas e, embora devam estar bem, parece que eu deveria fazer melhor. Mas também estou interessado na complexidade abstrata - meu palpite seria que a versão padrão da consulta ('existe uma solução de variação total ?') Seria NP-completa através da redução de algum problema de restrição como 3 SAT, mas não consigo ver a redução. Qualquer sugestão para o estudo anterior seria bem-vinda - parece um problema tão natural que não posso acreditar que não tenha sido analisado antes, mas minhas pesquisas até agora não revelaram nada parecido.$\leq k$

Aqui está um programa dinâmico. Suponha que para todos os por uma questão de clareza; o seguinte pode ser adaptado para funcionar se o tiver cardinalidades diferentes. Seja o custo mínimo de uma sequência nos primeiros conjuntos , terminando com . A seguinte recursão descreve :$C_i = \{C_{i_1}, \ldots, C_{i_m}\}$$i \in [n]$$C_i$$\operatorname{Cost}(i, j)$$i$$C_{i_j}$$\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}$

O custo mínimo geral é ; a sequência real de escolhas pode ser determinada examinando os argumentos ao longo do caminho. O tempo de execução é .$\min_{j = 1}^m \text{Cost}(n, j)$$O(nm)$

Parece que isso pode ser resolvido simplesmente computando o caminho mais curto em um gráfico acíclico direcionado. O raciocínio é que sua função objetivo minimiza a distância total entre "vizinhos" selecionados em seus conjuntos .$\mathcal{C} = \{C_1, \dotsc, C_n\}$

Construa um gráfico em estágios onde cada corresponde a um elemento exclusivo . Para cada , adicione uma aresta direcionada cujo custo seja a ou .$n$$G = (\bigcup_{i=1}^n V_i, E)$$v \in V_i$$x \in C_i$$u \in V_i, v \in V_{i+1}$$(u, v)$$\ell_1$$\ell_2$

Agora adicione um vértice de origem com arestas de custo 0 a e um vértice de afundamento com arestas de custo 0 de . Como é um DAG e as duas funções de distância forçam os custos de borda a não serem negativos, é possível calcular o caminho mais curto em com classificação topológica e programação dinâmica (semelhante à descrição aqui ).$s$$V_1$$t$$V_n$$G$$O(V + E)$