[Esercizio] Insieme numerico e somme vincolate

[imported_BlackLight]

Vi propongo un esercizio che mi è venuto in mente oggi, che implementa un problema NP-completo nella sua forma originaria ma che, usando per bene ricorsione ed esplorazione di alberi, diventa risolvibile con una sorta di brute force. Il problema è il seguente:

Dato un insieme numerico (ad esempio {1,2,3,4,5,6}) trovare un sottoinsieme la cui somma degli elementi fornisca un certo valore prefissato (ad esempio, 6).

Non è necessario trovare tutti i sottoinsiemi che soddisfino questa condizione, l'algoritmo si può anche fermare una volta trovato il primo.

Vi lascio questo stimolo e l'augurio di buon lavoro. Se proprio non doveste trovare niente, vi posterò la mia soluzione.

 

[Whivel]

è un problema risolvibile con il metodo del branch and bound.
se non fosse per il vincolo che non si possono prendere più elementi nello stesso sottoinsieme potrebbe essere considerato un problema di programmazione lineare intera (nel caso della presenza del vincolo non so):

max x1+x2+.....+xn
x1+x2+......+xn = numero_scelto
xi € {0} U {insieme_scelto}

dove n è la cardinalità dell'insieme (tranne in casi particolari)


:EDIT:

nel caso della presenza del vincolo, si può fare una semplice modifica al modello (non inserire lo 0 nell'insieme e impostare xi!=xj per ogni i) e al branch and bound: considera valida una soluzione anche se non ha dato un valore a tutte le variabile.

Cioò se il branch and bound trova una sequenza che da come risultato 6, allora ritiene la soluzione valida (e ottima), nonostante non ci siano variabili xj....xn non ancora inizializzate

 

[imported_BlackLight]

In effetti è anche risolvibile come problema di programmazione lineare (e in quanto tale è possibile applicare il metodo del simplesso o qualsiasi altro metodo per la risoluzione di un problema di programmazione lineare).

Personalmente però la soluzione che vedo più immediata è quella di vedere il problema come un un problema di backtracking. Ovvero, ho un nodo radice contenente l'elemento neutro (0 in questo caso) e voglio ad esempio che la somma faccia 6. Per ogni elemento nel mio insieme, provo a piazzarlo come elemento successivo del nodo corrente, andando avanti finché la somma degli elementi in quel ramo è, per dire, minore di 6. Se a un certo punto la somma dovesse diventare maggiore di 6, torno al nodo padre e provo a piazzare come figlio l'elemento successivo nell'insieme, e così via. Ad esempio, per n=6 esploro nell'ordine {0,1,2,3} e trovo subito una soluzione. A questo punto l'algoritmo va avanti considerando il sottoinsieme {0,1,2,3,4}, vede che sfora, allora va con {0,1,2,3,5}, poi con {0,1,2,3,6} e così via fino a {0,1,2,3,m} (in realtà questa parte si potrebbe evitare considerando un'euristica secondo cui l'insieme di partenza è già ordinato, quindi se a un certo punto un nodo figlio dà una "somma di ramo" > n allora effettuo una specie di alpha pruning e non proseguo quel ramo con gli elementi successivi). Una volta esaurito il ramo proverà con {0,1,2,4}, poi {0,1,2,5} e così via, fino a quando non tornerà al secondo nodo ed esplorerà il ramo {0,2,4} trovando un'altra soluzione, e si continua così.

Soluzione in Python:
http://goo.gl/hkLF8

 

[Whivel]

a parte il fatto che è programmazione lineare INTERA (e quindi non si può usare il simplesso, a meno di non usarla per le regole di valutazione), il metodo da te proposto è sicuramente efficace e, se non sbaglio, assomiglia molto (se non sono la stessa cosa ^^) al branch and bound, che funziona anche lui creando l'abero e tagliando i rami (non attraversa i rami) che danno soluzioni iimpossibile (somma maggiore di 6 per esempio)