Esponenziazione catena minima aggiunta

Question

So che è stato provato NP-completo, e va bene. Attualmente sto risolvendolo con branch e bound dove imposto il limite superiore iniziale al numero di moltiplicazioni che richiederebbe il normale algoritmo binario quadratico/multiplo, e dà le risposte giuste, ma non sono soddisfatto del funzionamento tempo (possono essere necessari diversi secondi per i numeri intorno ai 200). Essendo un problema NP-completo, non mi aspetto nulla di spettacolare; ma ci sono spesso trucchi per tenere un po 'il tempo reale sotto controllo.

Ci sono metodi più veloci per farlo in pratica? Se sì, quali sono?

Answer 1

Questo è simile alla sezione 4.6.3 "Valutazione dei poteri" in Algoritmi seminali di Knuth Vol 2. Questo va in notevole dettaglio per dare vari approcci, che sembrano molto più veloci di quelli derivati ​​e non offrono la soluzione migliore.

Knuth afferma nella discussione dopo il Teorema F che usa la ricerca di ritorno per dimostrare che l (191) = 11, quindi dubito che per questo troverai una risposta di taglio. Egli rinvia la spiegazione della ricerca di ritorno alla sezione 7.2.2, che a mio avviso non è ancora stata pubblicata, anche se su questo ci sono tracce di lavoro allo http://www-cs-faculty.stanford.edu/~uno/programs.html.

Answer 2

Metaheuristics Gli algoritmi si ridimensionano molto meglio. Essi comprendono Tabu ricerca, algoritmi genetici, simulato ricottura, ...

Ci sono un paio di freebooks e la connessione software là fuori.