Algoritmos para alocar N bolas em caixas M

5

Cada caixa tem pelo menos nenhuma bola e no máximo N bolas. É claro que o número total de bolas em caixas M deve ser igual a N

Para cada alocação, calculei um valor com base na alocação: V=f(n_1,n_2,...n_m) . Eu quero descobrir o máximo de V dado N, M e f. Preciso armazenar o V máximo e os resultados de alocação correspondentes.

Usando loops, a complexidade deve ser O (N ^ M), mas o loop não é o caminho a seguir neste caso.

Qualquer sugestão ou sugestão é muito apreciada. Tendo poucos algoritmos clássicos de DP à mão, mas sem sorte.

Nota: f = f1 + f2 + ... f_m , onde f (i) 's são polinômios. f (i) somente depende de n (i).

    
por Lovnlust 03.05.2015 / 15:18
fonte

2 respostas

2

Eu não sei quais algoritmos de DP você tentou, mas aqui está um que resolve seu problema em O (M * N²), que certamente é melhor que O (N ^ M).

O algoritmo funciona indutivamente aumentando o número de caixas. Em cada passo, você armazena o máximo de f1 + ... + f_m, onde m é o número de caixas no passo em particular (0 < = m < = M). Para um dado m, você resolve o problema para cada n entre 0 e N e usa as soluções para caixas m-1 para resolver o problema para m caixas (também para cada n entre 0 e N ).

Para m = 1, gerar as soluções para 0 < = n < = N - > O (N)

Para m = 2 e cada 0 < = n < = N, use ainda "força bruta" - > O (N²)

Para m = 3 e cada 0 = n = N e 0 = k = n, calcule f3 (k) + max ((f1 (x1) + f2 (x2)), onde x1 + x2 = nk (o termo máximo é o resultado do passo m = 2. Para cada n, mantenha o valor máximo sobre todos os k -> ainda O (N²) , que é o mesmo que O ((m-1) * N²)

Agora continue assim: cada etapa precisa apenas de N * (N + 1) / 2, assim O (N²), novos cálculos e você tem M-1 passos no total, então a complexidade geral é O (M * N²).

    
por 03.05.2015 / 17:33
fonte
3

Se você não precisa estritamente do máximo global, mas apenas de uma solução "razoavelmente boa", pode abordar esse tipo de problema usando uma técnica de aproximação conhecida como pesquisa local . A ideia é que você comece com uma determinada solução e tente melhorá-la fazendo “pequenos passos simples”.

No seu caso, tal passo poderia estar movendo uma bola de uma caixa para outra. Aqui está um algoritmo de busca local simplista:

  • um max ← ⊥
  • f max ← -1
  • Repetir k vezes:
    • Gere uma alocação aleatória a ← ( n 1 ,…, n m )
    • Embora você possa encontrar i e j de tal forma que n i & gt ; 0, n j < N e movendo uma bola da caixa i para caixa j aumenta f ( a ):
      • Defina a ← ( n 1 , n i i> - 1,…, n j + 1,… n < i> m )
    • Se f ( a ) > f max :
      • a max a
      • f max f ( a )
  • Saída da melhor alocação a max encontrada

Se você repetir apenas o loop principal uma vez ( k = 1), obterá o máximo local de um ponto de partida aleatório. Isso muitas vezes não será uma solução globalmente boa. Repetindo a pesquisa local algumas vezes a partir de diferentes pontos de partida aleatórios e finalmente obtendo o melhor máximo local, você aumenta suas chances de alcançar algo mais próximo do máximo global.

Se você sabe mais sobre o seu f , você pode ser capaz de criar um "pequeno passo" melhor do que simplesmente mover uma bola para outra caixa.

O tipo de algoritmo como a pesquisa local com várias reinicializações aleatórias é conhecido como uma meta-heurística porque é aplicável a um grande número de problemas sem saber muito sobre eles. (Essa forma em particular também é chamada de algoritmo hill climber .) Se você pesquisar por meta heurística, encontrará uma variedade de abordagens para escolher.

    
por 03.05.2015 / 16:36
fonte

Tags