problema NP complesso

volevo sapere se qualche programmatore si fosse mai cimentato con questo vecchio problema

il problema è molto semplice (da presentare)

dati n pesi (pere mele sassi) trovare la distribuzione di essi su due piatti della bilancia in modo che la differenza di peso complessivo dei due piatti tra di loro, sia minimizzata. E di farlo col minore numero di passaggi totali.

La difficoltà è quella di trovare un algoritomo che sia in grado di farlo attraverso una riduzione delle combinazioni possibili all'aumentare del numeri dei pesi, evitando cosi un aumento esponenziale e ingestibile dei tempi di elaborazione .

è piu tosto connesso con la programmazione tout court, ma potrebbe essere utile con arduino e in applicaizoni di robotica

E’ un banale quick sort dove una volta terminato cominci a sommare tra loro gli elementi in ordine ascendente e discendente.
Quando arrivi al punto in cui la somma ascendente è maggiore di quella discendente devi solo provare a spostare l’elemento più leggero dalla parte degli elementi più pesanti e verificare se il risultato migliora, in questo caso procedi col secondo elemento più leggero e riverifichi, così via fino a che il risultato non peggiora, a questo punto fai un step indietro e hai il risultato finale.

Fantastico il video!

cyberhs: Fantastico il video!

E' una sofisticatissima rappresentazione di quello che fanno gli elettroni dento la mcu. :grin:

un algoritmo veloce veloce : 11 minuti per mettere in fila 10 numeri? :-D

domanda seria: come faccio a sapere che non esistono soluzioni piu veloci di questo?

dr_vagus: domanda seria: come faccio a sapere che non esistono soluzioni piu veloci di questo?

Forse esiste un metodo che richiede meno passaggi, però ho seri dubbi in merito visto che parliamo di n elementi con pesi variabili senza nessuna regola a governarli.

Di algoritmi di ordinamento (sort) ce ne sono tantissimi, ognuno con le sue peculiarità (velocità, quantità di memoria aggiuntiva, numero di confronti, numero di scambi, ecc.)

Il QuickSort è uno dei più usati.

astrobeed: E' un banale quick sort dove una volta terminato cominci a sommare tra loro gli elementi in ordine ascendente e discendente. Quando arrivi al punto in cui la somma ascendente è maggiore di quella discendente devi solo provare a spostare l'elemento più leggero dalla parte degli elementi più pesanti e verificare se il risultato migliora, in questo caso procedi col secondo elemento più leggero e riverifichi, così via fino a che il risultato non peggiora, a questo punto fai un step indietro e hai il risultato finale.

ripensandoci bene pero' non mi pare convincente il tuo metodo. E soprattutto spiegato in modo un po' "vagus" :-)

Innanzitutto mi pare che il problema non sia riducibile a un algoritmo di ordinamento. Infatti tu esponi una tecnica di distribuzione, DOPO che li hai ordinati. L'ordinamento lo puoi fare appunto in tanti modi, non mi pare una cosa fondamentale, ne dispendiosa. Poniamo che te li fornisca già ordinati.

il problema è proprio dopo: come fai a ridurre l'insieme fattoriale delle combinazioni senza perderti quella con il differenziale minore?

col metodo che dici, non è assicurato che il risultato è la differenza minore tra le due distribuzioni. Infatti potrebbe esserci una combinazione tra elementi leggeri e pesanti migliore ma che il tuo metodo non riesce a sondare perché parti da due insiemi di cui uno ne ha una parte che rimane invariabile. (quella dei pesi piu grandi raccolti dopo il primo confronto).

poniamo che io abbia i seguenti pesi già ordinati

50 38 22 21 11 4 2 1

comincio a sommare dall'alto e dal basso?

e poi?

non è chiaro da quello che hai scritto. puoi precisare?

dr_vagus: non è chiaro da quello che hai scritto. puoi precisare?

Tenuto conto che stiamo parlando di una cosa totalmente ot, che ti ho già fornito una possibile soluzione, sicuramente non l'unica e probabilmente nemmeno la più efficiente, però è quella più semplice da implementare, non mi pare proprio il caso di perdere altro tempo in questo topic.

ok, cmq il problema della complessità NP è uno dei piu difficili della teoria della complessità computazionale, non credo si possa bollare con un banale "quick-sort".

Anche perchè è tutt'ora un problema irrisolto (ci sono in palio 1 milione di dollari a chi lo risolve!!!) :-D

https://it.wikipedia.org/wiki/Classi_di_complessit%C3%A0_P_e_NP

https://en.wikipedia.org/wiki/P_versus_NP_problem

grazie cmq per l'attenzione e scusa sesono andato leggermente OT.

dr_vagus: ok, cmq il problema della complessità NP è uno dei piu difficili della teoria della complessità computazionale, non credo si possa bollare con un banale "quick-sort".

Peccato che il problema che hai presentato non rientra in questa categoria, inoltre quando si parla della complessita NP non è un semplice algoritmo, si parla di un sistema in grado di trovare da solo l'algoritmo migliore per ogni singolo caso, perché la complessità NP non è riferibile ad un singolo caso/esempio, cosa che rende il problema molto, ma molto complesso. Per tua informazione con questo genere di problemi mi ci sono scontrato diverse volte per questioni di lavoro, ogni volta è toccato trovare soluzioni molto verticalizzate ottimizzate sul caso specifico, purtroppo non applicabili in generale per la natura stessa della questione.

Anche perchè è tutt'ora un problema irrisolto (ci sono in palio 1 milione di dollari a chi lo risolve!!!) :-D

E tu arrivi qui a chiedere aiuto per vincere dei soldi senza nemmeno offrire un compenso ? Comportamento decisamente scorretto, oltre che totalmente OT con questo forum, sicuramente il primo mod che passa da queste parti provvederà a chiudere, o cancellare, questo topic.

astrobeed: Peccato che il problema che hai presentato non rientra in questa categoria,

Io invece ritengo rientri a pieno titolo in quanto il problema deve ridurre il numero di combinazioni, garantendo la certezza del risultato. E' un caso riferibile alla classe degli NP completi. Per altro non di mia invenzione, ma riferitomi da un ingegnere che si occupava di IA.

E tu arrivi qui a chiedere aiuto per vincere dei soldi senza nemmeno offrire un compenso ? Comportamento decisamente scorretto, oltre che totalmente OT con questo forum, sicuramente il primo mod che passa da queste parti provvederà a chiudere, o cancellare, questo topic.

Io non ho chiesto nessun aiuto, solo mi interessava sapere se qualcuno avesse affrontato problemi simili di programmazione in qualche applicazione arduino e robotica. Perchè se anche irrisolto, vi sono pur sempre delle soluzioni provvisorie utilizzabili, come dici. mi sembra un problema sw non totalmente OT , ma che potrebbe interessare.

Mi spiace che tu tela sia presa tanto, solo perchè ho osato contraddirti, da invocare addirittura la censura del thread, ma non era mica obbligatorio rispondere.

bye

Invece... a me interessa come discussione :D Se proprio non è adatta in questo luogo, c'è sempre la parte di forum chiamata "software" o tuttalpiù il bar sport per spostare la discussione, non credo sia necessario chiuderla.

I problemi detti NP-Completi sono problemi dallo stato non noto... cioè non è detto che non esistano soluzioni polinomiali ma nessuno non è ancora riuscito a trovarle e sì, c'è un premio in denaro (1 mln di dollari) per ogni problema NP-Completo risolto (con opportuna dimostrazione matematica).

Se dovessimo risolverlo qua, devolveremo tutti i soldi alla community che volete che vi dica :D .

Comunque tornando nella discussione sei sicuro che il problema che hai enunciato sia NP completo? Perchè stavo dando un'occhiata al mio libro di algoritmi e sono abbastanza sicuro che non si rifaccia a nessuno dei problemi che sono spiegati all'interno del libro...

lpleo: Invece... a me interessa come discussione :D Se proprio non è adatta in questo luogo, c'è sempre la parte di forum chiamata "software" o tuttalpiù il bar sport per spostare la discussione, non credo sia necessario chiuderla.

Esatto, questo è un topic per bar sport, non ha nulla a che vedere con Arduino, queste cose non si fanno sulle piccole mcu 8 bit.

Comunque tornando nella discussione sei sicuro che il problema che hai enunciato sia NP completo? Perchè stavo dando un'occhiata al mio libro di algoritmi e sono abbastanza sicuro che non si rifaccia a nessuno dei problemi che sono spiegati all'interno del libro...

Infatti il problema proposto non ha nulla a che vedere con la complessità NP, oltre alla semplice soluzione che ho proposto me ne sono venute in mente almeno altre due decisamente molto più complesse da implementare, ma sicuramente più efficienti, alla fine è solo il classico problema di calcolo combinatorio, nulla di più nulla di meno.

@ dr_vagus "Per altro non di mia invenzione, ma riferitomi da un ingegnere che si occupava di IA."

Forse è meglio che quel ingegnere cambia mestiere perché ha detto una cavolata abbastanza grossa, oppure sei tu che non hai capito cosa ti ha detto esattamente e lo hai interpretato a tuo modo.

@drvagus

Guarda che non è vero che sono irrisolti... tutt'altro, gli algoritmi di risoluzione sono ben noti però.. hanno un tempo esponenziale alla dimensione del problema mentre lo si vorrebbe polinomiale.

Se trovi difficile quicksort lascia perdere

@Ipleo di problemi particolari sussumibili sotto la classe degli NP completi ve ne possono essere infiniti. Pertanto non credo che in un libro possano essere rappresentati tutti.

Non sono sicuro, sono ragionevolmente certo che si tratti di un tale problema, non tanto perchè me lo ha riferito l'ingegnere che si occupava di IA, perchè io sono un tipo maledettamente curioso e non mi fido di nessuno. Quanto perchè mi sembra corrisponda concettualmente alla definizione di quel tipo di problemi.

per esempio prendiamo la definizione informale. Dice a proposito della classi di complessità P e NP (che poi è il problema generale per il quale c'è il premio) " esso [problema] richiede di determinare se ogni problema per il quale un computer è in grado di verificare la correttezza di una soluzione positiva, in un tempo accettabile, è anche un problema che può essere risolto dal computer in un tempo accettabile (ovvero se il computer è in grado di trovare da solo una soluzione positiva in un tempo accettabile). Se la risposta è no, allora esistono problemi per i quali è più complesso calcolare una certa soluzione che verificarla."

ecco tra gli esterischi viene definito un problema NP : [u]se nel cercale la soluzione a un dato problema (per es. distribuire pesi su due piatti in modo da minimizzare la differenza) essa deve essere dimostrabile e calcolabile da computer in tempo accettabile allora mi trovo di fronte a un problema di quella classe.[/u]

e capisci bene che per il problema che ho posto il numero di combinazioni cresce in modo fattoriale o esponenziale e cosi pure il tempo di elaborazione, occorre quindi un sistema che trovi la soluzione e la sua dimostrazione scartando (diciamo cosi, sempre e in modo informale, colloquiale) la maggior parte delle combinazioni palesemente inutili.

E questo in robotica è un problema che potrebbe capitare, se una macchina deve scegliere la combinazione piu adatta per una certa operazione.

In wikipedia portano un esempio di problema NP completo "Un esempio di problema NP-completo è il problema delle somme parziali, cioè: dato un insieme finito di numeri interi, determinare se esiste un sottoinsieme tale che la somma dei suoi elementi sia zero."

converrai che è un problema del tutto simile a quello che ho indicato, che potrebbe essere parafrasato:

"Un esempio di problema NP-completo è il problema della distribuzione di due somme, cioè: dato un insieme finito di numeri interi, determinare se esiste un sottoinsieme tale che la somma dei suoi elementi sia quanto piu prossima alla somma dei restanti"

ciao

@flz47655 "Guarda che non è vero che sono irrisolti... tutt'altro, gli algoritmi di risoluzione sono ben noti però.. hanno un tempo esponenziale alla dimensione del problema mentre lo si vorrebbe polinomiale."

scusa devo essermi spiegato male, intendevo dire che non è risolto il problema generale (quello che ho virgolettato sopra, e per il quale c'è il premio). I singoli problemi sono pure risolvibili facilmente. In quello che ho presentato basta prendere i pesi e fare tutte le combinazioni e prendi quella a differenza minore, mica ci vuole tanto. il problema non è certo questo pero'. Ho provato esporlo qui sopra.

dr_vagus: E questo in robotica è un problema che potrebbe capitare, se una macchina deve scegliere la combinazione piu adatta per una certa operazione.

Ma assolutamente no, perlomeno non con gli attuali robot da lavoro visto che sono solo dei "semplici" esecutori di sequenze con una minima capacità di azione autonoma in base a quanto dicono i sensori, azioni autonome che comunque sono state preprogrammate da un essere umano.

Gli "N pesi" sono noti e finiti, noti ma non finiti, o ignoti ?

Da come descrivi il problema, semprerebbe noti ma non finiti (pesi dei singoli oggetti sempre uguali per la medesima classe di oggetti, numero possibile degli oggetti non definito ed arbitrario)

In questo caso, un singolo algoritmo semplicemente non esiste, perche' non gli puoi fornire tutti gli elementi per effettuare il calcolo (in quanto non puoi comunicargli "ci sono N1 pere, N2 mele, N3 sassi ..." ne tantomeno puoi sapere in precedenza quanti dei diversi oggetti sono presenti su quale piatto, non almeno nei termini in cui tu hai esposto il problema ... il sistema dovrebbe prima effettuare una serie di operazioni per "scoprire" quanti elementi di quale classe siano presenti su quale piatto, ed in seguito "decidere" come distribuirli in modo da ottimizzare il peso, e questo e' virtualmente impossibile con un singolo algoritmo ...

Ti faccio un'esempio banale, su un piatto c'e' una pietra da 20Kg, ed una mela da 200gr, sull'altro ci sono 100 mele da 200gr ... secondo la tua esposizione del problema, il sistema NON SA ne quanto pesa una mela, ne quanto pesa una pietra, ne quanti oggetti siano presenti su entrambi i piatti ne quali siano ... prova ad immaginare tutte le possibili combinazioni che ha il sistema anche solo per INIZIARE a tentare di risolvere il problema, senza nessuno di quei dati di partenza ... (ed ovviamente non sa neppure che sui piatti ci sono solo mele e pietre, per cui se si aspetta anche altri possibili oggetti e prende in considerazione ogni peso inserito come possibilita', i numeri crescono in modo esponenziale)

dr_vagus: ... "Un esempio di problema NP-completo è il problema delle somme parziali, cioè: dato un insieme finito di numeri interi, determinare se esiste un sottoinsieme tale che la somma dei suoi elementi sia zero." ...

Questo e' un tipico esempio di modo stupido di esporre un problema.

Mi spiego meglio.

"100 numeri interi", e', di fatto "un'insieme finito di numeri interi" ... io pero' in questo modo non ti dico quali siano, ne con che frequenza si ripetano, ne se si ripetono, ne qual'e' la loro grandezza, ne la loro distribuzione ... con questa esposizione del problema, tu puoi avere letteralmente qualsiasi cosa, da cento numeri "1", a cento numeri primi da 50000 cifre l'uno, a qualsiasi altra possibile combinazione ... quali sono i tuoi parametri operativi per iniziare a scoprire quali numeri ci sono nell'insieme finito di numeri interi che ti ho fornito ? ... :)

Inoltre, anche se io ti dessi un'insieme finito di numeri interi specificandoti ognuno dei numeri contenuti nell'insieme (condizione non richiesta dalla descrizione di cui sopra), per fare in modo "che la somma dei suoi elementi sia zero.", e' ovviamente necessario che almeno uno dei numeri dell'insieme sia un'intero negativo (con valore pari alla somma di tutti gli altri, fra l'altro), oppure che ci siano in ogni caso valori negativi in quantita' sufficente ad azzerare quelli positivi ... cosa che non e' detto sia vera, dato che "un'insieme finito di numeri interi" non implica necessariamente la presenza di valori negativi all'interno dello stesso, il che, ovviamente, implica la possibilita' tutt'altro che remota che non sia in alcun modo possibile avere una somma zero ;)