O que é uma maneira eficiente de ir além de um algoritmo guloso

votos
2

O domínio desta questão está programando operações em hardware restrito. A resolução do resultado é o número de ciclos de clock a programação se encaixa dentro. O espaço de busca cresce muito rapidamente, onde primeiras decisões restringir as decisões futuras e o número total de possíveis horários cresce rapidamente e de forma exponencial. Um monte de possíveis horários são equivalentes porque apenas trocando a ordem das duas instruções geralmente resultam na mesma restrição de tempo.

Basicamente, a questão é o que é uma boa estratégia para explorar o vasto espaço de busca sem gastar muito tempo. Espero para pesquisar somente uma fração pequena, mas gostaria de explorar diferentes partes do espaço de busca ao fazê-lo.

O algoritmo guloso atual tendem a tomar decisões estúpidas cedo, às vezes, e a tentativa de derivação e limitação foi além lento.

Edit: quero salientar que o resultado é muito binário com talvez o algoritmo guloso acabar usando 8 ciclos, enquanto existe uma solução usando apenas 7 ciclos usando derivação e limitação.

O segundo ponto é que existem restrições significativas no encaminhamento de dados entre as instruções e as dependências entre as instruções que limita a quantidade de semelhança entre as soluções. Olhe para ele como um problema da mochila com um monte de restrições de ordenação, bem como algumas soluções completamente falhando por causa de roteamento de congestionamento.

Esclarecimento: Em cada ciclo, há um limite para o número de operações de cada tipo e algumas operações têm dois tipos possíveis. Há um conjunto de restrições de roteamento que pode ser variado para ser bastante apertado ou muito indulgente eo limite depende de roteamento de congestionamento.

Publicado 19/05/2009 em 15:15
fonte usuário
Em outras línguas...                            


4 respostas

votos
3

otimização linear inteira para problemas NP-difíceis

Dependendo de suas limitações colaterais, você pode ser capaz de usar o método do caminho crítico ou (como sugerido em uma resposta anterior) programação dinâmica . Mas muitos problemas de agendamento são NP-hard apenas como o homem de vendas de viagem clássica --- uma solução precisa tem um pior caso de tempo de procura exponencial, assim como você descreve em seu problema.

É importante saber que, enquanto problemas NP-hard ainda tem um péssimo pior caso tempo de solução não é uma abordagem que muitas vezes produz respostas exatas com cálculos muito curtos (o caso médio é aceitável e que muitas vezes não ver o pior caso) .

Esta abordagem é converter o problema a um problema de otimização linear com variáveis ​​inteiras. Existem pacotes de software livre (como lp-resolver) que pode resolver esses problemas de forma eficiente.

A vantagem dessa abordagem é que ela pode lhe dar respostas exatas para problemas NP-difíceis em tempo aceitável. Eu usei essa abordagem em alguns projetos.

Como seu problema declaração não inclui mais detalhes sobre os constrangimentos do lado, eu não posso entrar em mais detalhes como aplicar o método.

Editar / adição: implementação Amostra

Aqui estão alguns detalhes sobre como implementar este método no seu caso (é claro, eu fazer algumas suposições que podem não se aplicar ao seu problema real --- Eu só sei os detalhes formar sua pergunta):

Vamos supor que você tem 50 instruções CMD (i) (i = 1..50) a ser programada no ciclo de 10 ou menos ciclos (t) (t = 1..10). Nós introduzimos 500 binário variáveis ​​v (i, t) (i = 1..50; t = 1..10) que indicam se cmd instrução (i) é executado no ciclo (t) ou não. Esta configuração básica dá as seguintes restrições lineares:

v_it integer variables
0<=v_it; v_it<=1;       # 1000 constraints: i=1..50; t=1..10
sum(v_it: t=1..10)==1   # 50 constraints:   i=1..50

Agora, temos de especificar as suas condições laterais. Vamos supor que operações cmd (1) ... cmd (5) são operações de multiplicação e que você tem exatamente dois multiplicadores --- em qualquer ciclo, você pode executar no máximo duas dessas operações em paralelo:

sum(v_it: i=1..5)<=2    # 10 constraints: t=1..10

Para cada um dos seus recursos, você precisa adicionar as restrições correspondentes.

Além disso, vamos supor que cmd operação (7) depende de cmd de operação (2) e precisa ser executado depois. Para tornar a equação um pouco mais interessante, também permite que requerem um intervalo de dois ciclo entre eles:

sum(t*v(2,t): t=1..10) + 3 <= sum(t*v(7,t): t=1..10)   # one constraint

Nota: soma (t * v (2, T): t = 1..10) é o ciclo de t onde v (2, t) é igual a um.

Finalmente, queremos minimizar o número de ciclos. Este é um pouco complicado, porque você começa bastante grandes números na maneira que eu proponho: Damos atribuir a cada v (i, t) um preço que cresce exponencialmente com o tempo: empurrando operações para o futuro é muito mais caro do que executá-las mais cedo:

sum (6 ^ t * v (i, t): i = 1..50; t = 1..10) -> mínimo. # Função de um alvo

Eu escolho 6 a ser maior do que 5 para garantir que a adição de um ciclo para o sistema faz com que seja mais caro do que espremer tudo em menos ciclos. Um efeito colateral é que o programa vai sair do seu caminho para agendar operações o mais cedo possível. Você pode evitar isso através da realização de uma otimização de duas etapas: primeiro, usar essa função de destino para encontrar o número mínimo de ciclos necessários. Então, pergunte o mesmo problema novamente com a função de destino diferente --- limitando o número de ciclos disponíveis no início e que imponha uma sanção preço mais moderado para operações posteriores. Você tem que jogar com isso, eu espero que você teve a idéia.

Felizmente, você pode expressar todos os seus requisitos que tais restrições lineares em suas variáveis ​​binárias. Claro, pode haver muitas oportunidades para explorar a sua visão sobre o seu problema específico para fazer com menos restrições ou menos variáveis.

Em seguida, entregar o seu problema fora de lp-resolver ou CPLEX e deixá-los a encontrar a melhor solução!

Respondeu 19/05/2009 em 15:44
fonte usuário

votos
1

Se você pode mapear o seu problema com o "caixeiro-viajante" (como: Encontrar a sequência ideal para executar todas as operações em tempo mínimo), então você tem um problema NP-completo.

Uma maneira muito rápida para resolver que é o algoritmo de formiga (ou otimização de colônia de formigas).

A idéia é que você envia uma formiga para baixo cada caminho. A formiga se espalha uma substância fedorenta no caminho que evapora ao longo do tempo. peças curtas significa que o caminho vai feder mais quando a próxima formiga vem. Formigas preferem mau cheiro em caminhos limpos. Executar milhares de formigas através da rede. O caminho mais degradado é o óptimo (ou pelo menos muito próxima).

Respondeu 19/05/2009 em 15:37
fonte usuário

votos
1

À primeira vista, parece que este problema pode caber em uma solução de programação dinâmica . Várias operações podem ter a mesma quantidade de tempo para que você pode acabar com subproblemas sobrepostas.

Respondeu 19/05/2009 em 15:25
fonte usuário

votos
0

Tente recozimento simulado, cfr. http://en.wikipedia.org/wiki/Simulated_annealing .

Respondeu 19/05/2009 em 15:19
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more