Esse é um problema conhecido de otimização / programação combinatória?

Recebemos pilhas que contêm "itens" de cores diferentes e uma máquina que pode processar vários itens da mesma cor de uma só vez. Em cada etapa, podemos remover um item da parte superior de cada pilha e colocá-lo em nossa máquina (para que a máquina possa processar no máximo itens em uma única etapa - para que isso aconteça, todas as pilhas devem ter itens da mesma cor em cima). O objetivo é processar todos os itens em um tempo mínimo. $n$ $n$

Exemplo de entrada:

Uma solução possível é um algoritmo ganancioso: em cada etapa, pegue o máximo de itens possível e coloque-os na máquina. Infelizmente, o algoritmo ganancioso não é o ideal - ele produz o seguinte cronograma para a entrada de exemplo:

O cronograma ideal é o seguinte:

Eu pretendo usar alguma forma de pesquisa de espaço de estado, mas talvez haja uma abordagem mais específica e eficiente do problema? Links para a literatura relevante apreciada.

ds.algorithms reference-request scheduling Mikhail Glushenkov
fonte

Em cada etapa, você pode retirar apenas um item do topo de cada pilha (e todos os itens que você coloca na máquina devem ser da mesma cor). Portanto, o algoritmo ganancioso produz um cronograma não ideal (veja a fig. 2).

Mikhail Glushenkov

E você deve processar todos os itens em ordem, ou seja, levá-los apenas de cima.

Mikhail Glushenkov

Ahh Entendi. Problema interessante. Eu faria uma tabela de pesquisa ideal para decidir as primeiras linhas se esse fosse um sistema em tempo real. Quanto à complexidade exata ... prove o ideal para o caso de duas colunas primeiro.

Chad Brewbaker

O quiestion seria ainda mais interessante, se estiver operando em um conjunto de listas FIFO, nas quais você só pode ver elementos até uma profundidade específica para o cálculo.

George Polevoy

Respostas:

$[1]$ $O(n^2)$ $[2]$

O que diz respeito à proximidade de uma boa fonte é um compêndio de problemas de otimização de NP .

$[3,4]$

$[5]$ $[6]$

Brauner N., Naves G. Agendando cadeias de operações em uma máquina de tratamento por lotes com conjuntos de compatibilidade de operações separados .
Brucker P. Algoritmos de agendamento (capítulo 8. Problemas de lote).
Timkovsky VG: Algumas Aproximações para as Não Subsequências e Superssequências Comuns Mais Curtas .
Gotthilf Z. e Lewenstein M. Resultados Aproximados Aprimorados no Menor Problema de Supersequência Comum .
Kubalik J. Algoritmo estocástico eficiente de busca local para resolver o menor problema de superssequência comum .
Blum, C., Cotta, C., Fernandez, AJ, Gallardo, JE A probabilística Beam Search Abordagem ao Supersequência Problema Shortest comum .

Oleksandr Bondarenko
fonte

k

$k$

n

$n$

O (n^{k})

$O(n^k)$

$\Omega(\log^\delta n)$

$k$ $k$ $X$ $|X| = x$ $X$ $x$ $x$ $X$ $x/k$

Sasho Nikolov
fonte