Algoritmi per l'assegnazione di palle N in scatole M

Non so quali algoritmi DP hai provato, ma qui è uno che risolve il tuo problema in O (M * N²), che è sicuramente migliore di O (N ^ M).

L'algoritmo funziona induttivamente aumentando il numero di caselle. In ogni fase, memorizzi il massimo di f1 + ... + f_m, dove m è il numero di caselle nel particolare passo (0 < = m < = M). Per un dato m, risolvi il problema per ogni n tra 0 e N , e usi le soluzioni per le scatole m-1 per risolvere il problema per i box m (anche per ogni n tra 0 e N ).

Per m = 1, genera le soluzioni per 0 < = n < = N - > O (N)

Per m = 2 e ogni 0 < = n < = N, usa ancora "forza bruta" - > O (n²)

Per m = 3 e ogni 0 < = n < = N e 0 < = k < = n, calcola f3 (k) + max ((f1 (x1) + f2 (x2)), dove x1 + x2 = nk (il termine massimo è il risultato del passo m = 2. Per ogni n, mantieni il valore massimo su tutto k. - > ancora O (N²) , che è lo stesso di O ((m-1) * n²)

Ora continua così: ogni passo ha bisogno solo di N * (N + 1) / 2, quindi O (N²), nuovi calcoli, e hai passaggi M-1 in totale, quindi la complessità complessiva è O (M * n²).

Se non hai bisogno del massimo globale ma solo di una soluzione "abbastanza buona", puoi affrontare questo tipo di problema con una tecnica di approssimazione conosciuta come ricerca locale . L'idea è che inizi con una determinata soluzione e provi a migliorarla facendo "semplici piccoli passi".

Nel tuo caso, un tale passaggio potrebbe spostare una palla da una scatola all'altra. Ecco allora un semplicistico algoritmo di ricerca locale:

• a _max ← ⊥
• f _max ← -1
• Ripeti k volte:
  • Genera un'allocazione casuale a ← ( n ₁ , ..., n _m )
  • Mentre puoi trovare i e j in modo che n _i & gt ; 0, n _j < N e spostando una pallina dalla casella i alla casella j aumenta f ( a ):
    • Imposta a ← ( n ₁ , ..., n _i - 1, ..., n _j + 1, ... n _{< i> m} )
  • Se f ( a ) > f _max :
    • a _max ← a
    • f _max ← f ( a )
• Emette la migliore allocazione a _max trovata

Se ripeti il ciclo principale una sola volta ( k = 1), otterrai il massimo locale da un punto di partenza casuale. Questo spesso non sarà una soluzione valida a livello globale. Ripetendo la ricerca locale alcune volte da diversi punti di partenza casuali e infine prendendo il massimo locale, aumenti le possibilità di raggiungere qualcosa di più vicino al massimo globale.

Se sai di più sul tuo f , potresti essere in grado di progettare un "piccolo passo" migliore del semplice spostamento di una pallina in un'altra casella.

Il tipo di algoritmo come la ricerca locale con più riavvii casuali è noto come meta euristico poiché è applicabile a un gran numero di problemi senza conoscerne molto. (Questa particolare forma è anche a volte indicata come algoritmo di alpinismo .) Se cerchi la meta euristica, troverai una vasta gamma di approcci tra cui scegliere.