problema NP complesso

Etemenanki: ...per fare in modo "che la somma dei suoi elementi sia zero."

Infatti non "devi fare in modo che" la somma faccia zero. Non è questo che chiede il problema.

ciao

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

Alla "Community"??? :o Per carità! Abbiamo visto che ne ha già fin troppi la "Community"! :D

BaBBuino: ... Per carità! Abbiamo visto che ne ha già fin troppi la "Community"! :D

Be, se "voi ricconi" ne avete gia cosi tanti che non sapete piu dove metterli, un'angolino nel mio ripostiglio per farceli stare ve lo trovo ... :P :D :D :D

dr_vagus: Infatti non "devi fare in modo che" la somma faccia zero. Non è questo che chiede il problema. ciao

Io mi riferivo al problema che tu hai citato come presente in wiki, e cioe' "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."

Se io leggo una domanda come quella, dove si richiede di "determinare se esiste un sottoinsieme tale che la somma dei suoi elementi sia zero", ho per logica (ed unica possibile) linea di indagine che devo, appunto, determinare l'esistenza o meno di tale possibilita' (l'esposizione del problema, in quei termini, non richiede altro, ne consente altro) ... in un caso del genere, dati tutti i numeri dell'insieme noti, per determinare l'esistenza di tale possibilita' basta la semplice aritmetica, vale a dire che si prendono tutti i numeri dell'insieme e si sommano, positivi e negativi (se ce ne sono), e se il risultato e' zero, ho determinato che esiste (cioe' il sottoinsieme di tutti i numeri positivi sommati a tutti i numeri negativi e' zero), se invece non lo e', ho determinato che non esiste ... qualora invece non sia noto anche uno solo dei numeri dell'insieme, la domanda in se stessa (come del resto il problema, con quella premessa) e' una totale illogicita', che non merita neppure di essere presa in considerazione ...

Per quello parlavo di modo estremamente stupido di esporre un problema (da parte di chi ha scritto l'articolo originale, non da parte tua) ... perche', esposta in quei termini la domanda, a parte quello elementare appena esposto, semplicemente non ha un qualsiasi altro senso logico (poi non venitemi a dire che la matematica non sempre ha un senso logico, quello lo so gia :P :D :D :D) ...

@dr_vagus Ho un libro di algoritmi, dove sono esemplificati alcuni problemi np completi e la loro risoluzione non ottima ma sufficiente. Uno di questi è il problema del commesso viaggiatore, o quello dello zaino. E per questi problemi, esistono soluzioni approssimate ma buone.

Volevo ricondurlo ad un pattern e darti l'algoritmo approssimato.

Tuttavia più ci riflettevo più il problema che hai posto, più mi sono reso conto che come ti ha indicato @Etemenanki Gli "N pesi" sono noti e finiti, noti ma non finiti, o ignoti ?

Perchè se sono noti e finiti, il problema secondo me non è NP complesso.

L'unico pattern che mi ricorda, potrebbe essere appunto quello del problema dello zaino, ma allora hai posto il problema in maniera errata...

Dopo non ho il tempo di riprendere in mano tutta la teoria eh, vado ad occhio.

Se non ho preso una cantonata, e se i pesi sono dichiarati e di numero finito io lo risolverei così:

#include <stdio.h>
#include <stdlib.h>

int main() {
    int masse[] = {50, 38, 22, 21, 11, 4, 2, 1};
    int massedx[8];
    int massesx[8];

    ///abbiamo ordinato il vettore tramite bucket sort (complessità n) e contato il numero di elementi -> tempo lineare
    int n=8,i=0;

    int sd=0,sx=0,cd=0,cx=0; ///somma masse destre e sinistre;
    ///for -> tempo lineare
    for(i=0;i<n;i++) {
        if(sd<=sx) {
            sd+=masse[i];
            massedx[cd]=masse[i];
            cd++;
        }
        else {
            sx+=masse[i];
            massesx[cx]=masse[i];
            cx++;
        }
    }

    printf("\nTotale masse a dx: %d\nMasse a destra:\n",sd);
    for(i=0;i<cd;i++) {
        printf("%d\n",massedx[i]);
    }

    printf("\nTotale masse a sx: %d\nMasse a sinistra:\n",sx);
    for(i=0;i<cx;i++) {
        printf("%d\n",massesx[i]);
    }

    ///tempo n (bucket sort) + n (conteggio del numero di elementi) + n (primo ciclo for) -> non è neanche esponenziale
    ///Quindi non è neanche NP.
}

Dopo ripeto, potrei aver preso una cantonata…

lpleo: Tuttavia più ci riflettevo più il problema che hai posto, più mi sono reso conto che come ti ha indicato @Etemenanki Gli "N pesi" sono noti e finiti, noti ma non finiti, o ignoti ?

basta leggere la definizione: "...dato un insieme finito di numeri interi...", secondo te sono infiniti?

Quanto ad esse noti, Etemenanki ha posto questa domanda, e alla risposta c'è arrivato da solo: "qualora invece non sia noto anche uno solo dei numeri dell'insieme, la domanda in se stessa (come del resto il problema, con quella premessa) e' una totale illogicita', che non merita neppure di essere presa in considerazione ... "

E' ovvio quindi che sono noti tutti (avevo dato anche un esempio). D'altra parte quando si scrive che il numero è "dato", significa che è reso noto, conosciuto. E' difficile "dare" un numero senza farlo conoscere (magari dentro una scatola o in busta chiusa?). In realtà l'enunciazione di wikipedia di quel problema è formulata bene, chiara e direi anche elementare.

Perchè se sono noti e finiti, il problema secondo me non è NP complesso.

Per quanto mi consta i possibili problemi della classe NP completi sono "necessariamente" formati da un numero finito di elementi e tutti conosciuti, se al contrario fossero infiniti e non noti torneremmo alla perspicace intuizione di Etemenanki , e quindi non sarebbe neanche un NP completo, a meno di non definire un problema NP completo come una "totale illogicità", io direi pure insensatezza.

ciao

Etemenanki: Io mi riferivo al problema che tu hai citato come presente in wiki, e cioe' "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."

... in un caso del genere, dati tutti i numeri dell'insieme noti, per determinare l'esistenza di tale possibilita' basta la semplice aritmetica, vale a dire che si prendono tutti i numeri dell'insieme e si sommano, positivi e negativi (se ce ne sono), e se il risultato e' zero, ho determinato che esiste (cioe' il sottoinsieme di tutti i numeri positivi sommati a tutti i numeri negativi e' zero)

Se sommi TUTTI i numeri (positivi e negativi che siano), qualunque sia il risultato, NON hai determinato un SOTTOinsieme, come chiede il problema. Hai determinato l'INSIEME tutto intero.

Mentre il problema è di verificare se vi sia un SOTTO-insieme la cui somma dia zero. INSIEME e SOTTOINSIEME sono due cose diverse.

faccio un esempio

se hai un INSIEME di 10 numeri (di qualsivoglia segno), un qualsiasi SOTTOINSIEME di quell INSIEME non puo' essere di 10 numeri. Ci sei? deve essere di un numero inferiore a 10, ok?

Dunque se devi determinare un sottoinsieme allora il problema diventa combinatorio.

ciao

lpleo: Se non ho preso una cantonata, e se i pesi sono dichiarati e di numero finito io lo risolverei così:

e il risultato quale sarebbe? puoi postarlo?

@dr_vagus

Totale masse a dx: 75 Masse a destra: 50 21 4

Totale masse a sx: 74 Masse a sinistra: 38 22 11 2 1

dr_vagus:

se hai un INSIEME di 10 numeri (di qualsivoglia segno), un qualsiasi SOTTOINSIEME di quell INSIEME non puo’ essere di 10 numeri. …

Ed io che ho detto ?

“il sottoinsieme di tutti i numeri positivi sommati a tutti i numeri negativi e’ zero”

tutti i numeri positivi sono un sottoinsieme, tutti i numeri negativi sono un sottoinsieme, se ovviamente sono tutti positivi, il problema non ha soluzione logica.

Mi porto anche piu in la’, se nel tuo insieme di 10 numeri, ci sono un +5 ed un -5, la loro somma e’ gia un sottoinsieme con risultato zero (ovviamente questo presuppone di ignorare tutto il resto dell’insieme di numeri, ma il problema non lo vieta, e come ho detto, non sempre la matematica e’ anche logica :stuck_out_tongue: :D)

Etemenanki: Ed io che ho detto ?

"il sottoinsieme di tutti i numeri positivi sommati a tutti i numeri negativi e' zero"

tutti i numeri positivi sono un sottoinsieme, tutti i numeri negativi sono un sottoinsieme,

se sommi il sottoinsieme di TUTTI i positivi e il sottoinsieme di TUTTI i negativi, hai sommato TUTTI i numeri dell'insieme. Il risultato finale è che non hai trovato un sottoinsieme che fa zero, ma l'insieme tout court che fa zero.

ma il problema non chiede questo.

il problema chiede se esiste un sottoinsieme che faccia zero. tu invece stai verificando se l'insieme faccia zero. Che è un altro problema.

lpleo: Se non ho preso una cantonata, e se i pesi sono dichiarati e di numero finito io lo risolverei così: " ///abbiamo ordinato il vettore tramite bucket sort (complessità n) e contato il numero di elementi -> tempo lineare ///tempo n (bucket sort) + n (conteggio del numero di elementi) + n (primo ciclo for) -> non è neanche esponenziale ///Quindi non è neanche NP."

Dopo ripeto, potrei aver preso una cantonata... "

no credo che tu sia l'unico che ha capito il problema e ha dato una possibile risposta. Mi sono andato a vedere qualcosa. Credo che tu abbia ragione, la differenza tra il problema dato da Wiki pedia e quello dato da me è che - in termini informali - il primo è un problema NP completo in quanto è un problema di decidibilità. mentre quello della distribuzione dei pesi è un problema di ottimizzazione, in tal caso non puo' essere un NP completo, tuttavia rimane pero' un problema NP-difficile.

ciao