Nome desse problema de reorganização / classificação?

10

Você recebe uma matriz de comprimento . Cada elemento da matriz pertence a uma das classes. Você deve reorganizar a matriz usando o número mínimo de operações de troca, para que todos os elementos da mesma classe sejam sempre agrupados, ou seja, eles formem uma sub- matriz contígua. Por exemplo: Três outros arranjos válidos permanecem. $n$ $K$

\begin{aligned} [2, 1, 3, 3, 2, 2] ⟶ [2, 2, 2, 1, 3, 3], or \\ [2, 1, 3, 3, 2, 2] ⟶ [1, 2, 2, 2, 3, 3], or \\ [2, 1, 3, 3, 2, 2] ⟶ [3, 3, 2, 2, 2, 1] . \end{aligned}

$\begin{align*} &[2, 1, 3, 3, 2, 2] \longrightarrow [2, 2, 2, 1, 3, 3], \text{ or} \\ &[2, 1, 3, 3, 2, 2] \longrightarrow [1, 2, 2, 2, 3, 3], \text{ or} \\ &[2, 1, 3, 3, 2, 2] \longrightarrow [3, 3, 2, 2, 2, 1]. \end{align*}$

Como é chamado esse problema na literatura? Existe um algoritmo eficiente para isso?

terminology reference-request sorting arrays Marko Bukal
fonte

11

Não tenho certeza se esse problema tem um nome, embora seja certamente possível. Nem todos os problemas concebíveis têm nomes.

Yuval Filmus 10/10

2

Na prática, isso seria chamado de agrupamento . Eu não estou ciente da terminologia na algorítmica clássica. (É certamente um problema interessante e potencialmente difícil! Minimizar o número de swaps tem a sensação de "encontrar a melhor permutação de grupos", o que, por sua vez, parece NP-difícil.)

Raphael

Bem pessoal, obrigado por enquanto. É claro que estou interessado em solucionar o problema, mas pensei que ele já havia sido estudado e estava pedindo uma referência.

Marko Bukal 10/10

6

Nota: É uma prova de dureza, e acho que existem algoritmos práticos como programação inteira, etc.

Dada uma instância BIN_PACKING em que você deseja compactar os números em compartimentos de tamanho , e é garantido que , podemos criar uma instância do seu problema da seguinte maneira: $K$ $n_1,\ldots,n_K$ $L$ $m_1,\ldots,m_L$ $\sum n_i=\sum m_j=N$

Existem classes ; $K+(N+1)(L-1)$
As primeiras classes têm tamanho respectivamente, e cada uma das classes restantes possui tamanho ;; $K$ $n_1,\ldots,n_K$ $N+1$
A matriz é particionada em slots de tamanho: que cada slot de tamanho é empacotado com classes, organizadas contiguamente, e o restante é organizado arbitrariamente. $m_{1}, (N + 1)^{2}, m_{2}, (N + 1)^{2}, m_{3}, \dots, (N + 1)^{2}, m_{L}$ $m_1,(N+1)^2,m_2,(N+1)^2,m_3,\ldots,(N+1)^2,m_L$ $(N+1)^2$ $N+1$

Agora, uma observação importante é que não faz sentido manter pelo menos uma classe em um slot e mover outras (porque isso não altera o tamanho de um 'bin'). Assim, a embalagem bin original está disponível, se e somente se o número mínimo de swaps não é maior que . Como o BIN-PACKING é conhecido por ser fortemente NP-completo , seu problema é NP-difícil. $(N+1)^2$ $N$

Willard Zhan
fonte

Isso é lindo! Caso outros também tenham dificuldades: (1) swaps são sempre suficientes para criar qualquer "empacotamento de lixeira" que desejamos nos slots de tamanho , pois uma única troca é suficiente para mover um elemento para sua localização final. sem perturbar os elementos já colocados. (2) Há apenas duas coisas possíveis que poderíamos tentar fazer com as "zonas de buffer" de comprimento- entre "compartimentos": mova uma classe inteira de comprimento- em uma das extremidades em outro lugar (mas isso custa swaps já, portanto, não podemos), ou "slide" toda a posição coisa que a esquerda ou direita (mas isso implica "correr" cada ...

N

$N$

m_{1}, \dots, m_{L}

$m_1, \dots, m_L$

(N + 1)^{2}

$(N+1)^2$

(N + 1)

$(N+1)$

N + 1

$N+1$

j_random_hacker

... classe na posição esquerda ou direita do buffer, e embora possamos fazer isso com uma única troca por classe, há classes na zona, portanto são necessários pelo menos swaps, então mais uma vez: impossível). Este ponto é necessário para argumentar que uma solução para o problema do OP com custo implica um empacotamento de caixa válido. (3) Como o empacotamento de lixeira é altamente completo em NP, o "não-não" usual de criar vários dispositivos (aqui, elementos de matriz) proporcionais aos números codificados na entrada não se aplica aqui :)

N + 1

$N+1$

N + 1

$N+1$

\leq N

$\le N$

j_random_hacker

1

Eu também suspeito que isso é difícil para o NP, mas, na ausência de uma idéia para uma prova, aqui estão alguns limites inferiores rapidamente computáveis que podem ser úteis para verificar a otimização de uma solução heurística ou remover uma pesquisa ramificada e vinculada .

Deixe a classe conter elementos. Em qualquer solução válida, a classe deve começar em alguma posição . Assim, podemos calcular um limite inferior no custo de "fixar" a classe tentando todas as posições iniciais possíveis , contando o número de elementos não- no bloco começando na posição (cada uma dessas posições exigirá troca) e levando o mínimo. Esse pode ser calculado para qualquer em usando uma abordagem de janela deslizante, para $i$ $n_i$ $i$ $j$ $L_i$ $i$ $j$ $i$ $n_i$ $j$ $L_i$ $i$ $O(n)$ $O(Kn)$ tempo total. Dois limites inferiores gerais são:

Leve o máximo de todos os . Apertado para , provavelmente muito fraco para grande . $L_i$ $K=2$ $K$
Soma todo e divida por 2, arredondando para cima. Isso é válido porque qualquer troca pode corrigir no máximo 2 posições incorretas. $L_i$

No seu exemplo, esses limites fornecem 1 (0,5 pode ser arredondado no último caso), o que é óbvio.

j_random_hacker
fonte

Nome desse problema de reorganização / classificação?

Respostas: