ݺߣ

ݺߣShare a Scribd company logo

Problemi np con esempio

•
•
Rice Cipriani
Rice Cipriani
1 of 3
Download to read offline
per capire se un problema è np (ovvero risolvibile con un algoritmo non deterministico in tempo polinomiale) se riesci quindi a trovare un algoritmo che ti ricava in tempo polinomiale non deterministico le soluzioni candidate e poi trovi un algoritmo che dalla soluzione candidata ti sa dire se è una istanza yes in tempo polinomiale allora il problema è np. quindi il problema si divide in due 1) trovare un algoritmo per ricavare le soluzioni 2) dalle soluzioni trovare un algoritmo che ne stabilisca se sono istanze yes Il secondo è alquanto semplice anche se non c'è una maniera specifica per tutti, ad ogni esercizio devi trovare un modo diverso ma la seconda parte è la cosa più facile. Per la prima che apparentemente sembra difficile c'è la storia dei guess che aiuta tantissimo. Infatti a te serve un algoritmo che generi tutte le possibili istanze in tempo polinomiale non deterministico. L'algoritmo con le guess lo genera addirittura in tempo lineare (o lineare per logaritmico a seconda se le guess sono binarie o secondo un alfabeto finito). Quindi il difficile adesso è trovare il modo di rappresentare i tuoi dati e darli in pasto all'algoritmo guess. ______________ ricapitolando 1) trovare un vettore che rappresenta i tuoi dati che può essere o binario (allora la generazioni è lineare) oppure un vettore di elementi di un certo alfabeto di n elementi (allora la generazione è logaritmina rispetto al quell'n) 2) trovare un algoritmo che dica se il vettore generato è yes o no
allora potremmo prendere un esempio concreto 24-giugno-2004 Esercizio 4 (25%) Si consideri il problema di decisione PARTIZIONE IN CLIQUE. PARTIZIONE IN CLIQUE Istanza: <G, K>, dove G = (V,E) è un grafo e K è un intero tale che 0 < K ≤ |V|. Predicato: E’ possibile partizionare i vertici di G in K insiemi (disgiunti) V1,....,VK tali che: per 1 ≤ i ≤ K il sottografo di G che comprende i vertici di Vi e tutti gli archi incidenti su tali vertici è completo (cioè Vi è una clique di G)? 4.1) Dimostrare che il problema PARTIZIONE IN CLIQUE appartiene ad NP. Il problema chiede di trovare una partizione in sottoinsiemi del grafo in maniera tale che siano tutte clique. Allora la prima cosa è capire come rappresentare in un vettore questi dati il concetto è che tu devi prendere i tuoi dati pensandoli come in generale ad una istanza; non devi pensare al risultato che vuoi ma devi pensare ad una certa istanza e a come codificarla, poi l'algoritmo guess provvederà a riempire il vettore in tutti i modi possibili. In questo caso io avevo pensato ad un vettore che rappresenta tutti i vertici e quindi di dimensione |V|. Ogni elemento del vettore può avere un valore da 1 a k e rappresenta l'appartenenza ad una partizione; in questo modo sai che tutte le istanze sono tutte le possibile combinazioni di appartenenza dei vertici ad una certa partizione k-esima
il concetto è che alla fine dei guess tu hai questo vettore riempito in miliadri di modi, ovvero tutte le maniere possibili. Ogni istanza rappresenta un modo di associare ogni vertice ad una partizione tu trovi una maniera di rappresentare i dati in maniera generica e poi l'algoritmo con le guess riempe i vettori in tutte le maniere possibili ogni posizione i-esima ha un valore 1<n<k che rappresenta l'appartenenza dell'i-esimo vertice alla partizione n-esima. Dopo |V| guess avrai tutte le possibili istanze (in numero pari a K|V|). Come esempio si può prendere un triangolo con attaccato un vertice. Quindi la rappresentazione è un vettore di 4 elementi ciascuno identifica un vertice. Nel vettore ci memorizzi una partizione di appartenenza (da 1 a 4 siccome al massimo puoi avere 4 partizioni). Dopo ogni guess riempo una posizione da destra verso sinistra con un numero. I rami generati fissano un numero. Dopo 4 guess ho tutte le mie 64 combinazioni. Adesso devo determinare un algoritmo di costo polinomiale che presa una qualsiasi combinazione determina se è una istanza yes. Un possibile algoritmo di costo quadratico è: scandisco ogni elemento del vettore; per ognuno scandisco tutti i suoi successivi; per ogni coppia determino se appartengono alla stessa partizione (se il vettore in corrispondenza delle due posizioni contiene lo stesso numero) se appartengono alla stessa partizione allora determino, con la matrice di adiacenze (supposta riempita), se i vertici sono adiacenti; se non sono adiacenti allora l'istanza è no.

More Related Content

Problemi np con esempio

  • 1. per capire se un problema è np (ovvero risolvibile con un algoritmo non deterministico in tempo polinomiale) se riesci quindi a trovare un algoritmo che ti ricava in tempo polinomiale non deterministico le soluzioni candidate e poi trovi un algoritmo che dalla soluzione candidata ti sa dire se è una istanza yes in tempo polinomiale allora il problema è np. quindi il problema si divide in due 1) trovare un algoritmo per ricavare le soluzioni 2) dalle soluzioni trovare un algoritmo che ne stabilisca se sono istanze yes Il secondo è alquanto semplice anche se non c'è una maniera specifica per tutti, ad ogni esercizio devi trovare un modo diverso ma la seconda parte è la cosa più facile. Per la prima che apparentemente sembra difficile c'è la storia dei guess che aiuta tantissimo. Infatti a te serve un algoritmo che generi tutte le possibili istanze in tempo polinomiale non deterministico. L'algoritmo con le guess lo genera addirittura in tempo lineare (o lineare per logaritmico a seconda se le guess sono binarie o secondo un alfabeto finito). Quindi il difficile adesso è trovare il modo di rappresentare i tuoi dati e darli in pasto all'algoritmo guess. ______________ ricapitolando 1) trovare un vettore che rappresenta i tuoi dati che può essere o binario (allora la generazioni è lineare) oppure un vettore di elementi di un certo alfabeto di n elementi (allora la generazione è logaritmina rispetto al quell'n) 2) trovare un algoritmo che dica se il vettore generato è yes o no
  • 2. allora potremmo prendere un esempio concreto 24-giugno-2004 Esercizio 4 (25%) Si consideri il problema di decisione PARTIZIONE IN CLIQUE. PARTIZIONE IN CLIQUE Istanza: <G, K>, dove G = (V,E) è un grafo e K è un intero tale che 0 < K ≤ |V|. Predicato: E’ possibile partizionare i vertici di G in K insiemi (disgiunti) V1,....,VK tali che: per 1 ≤ i ≤ K il sottografo di G che comprende i vertici di Vi e tutti gli archi incidenti su tali vertici è completo (cioè Vi è una clique di G)? 4.1) Dimostrare che il problema PARTIZIONE IN CLIQUE appartiene ad NP. Il problema chiede di trovare una partizione in sottoinsiemi del grafo in maniera tale che siano tutte clique. Allora la prima cosa è capire come rappresentare in un vettore questi dati il concetto è che tu devi prendere i tuoi dati pensandoli come in generale ad una istanza; non devi pensare al risultato che vuoi ma devi pensare ad una certa istanza e a come codificarla, poi l'algoritmo guess provvederà a riempire il vettore in tutti i modi possibili. In questo caso io avevo pensato ad un vettore che rappresenta tutti i vertici e quindi di dimensione |V|. Ogni elemento del vettore può avere un valore da 1 a k e rappresenta l'appartenenza ad una partizione; in questo modo sai che tutte le istanze sono tutte le possibile combinazioni di appartenenza dei vertici ad una certa partizione k-esima
  • 3. il concetto è che alla fine dei guess tu hai questo vettore riempito in miliadri di modi, ovvero tutte le maniere possibili. Ogni istanza rappresenta un modo di associare ogni vertice ad una partizione tu trovi una maniera di rappresentare i dati in maniera generica e poi l'algoritmo con le guess riempe i vettori in tutte le maniere possibili ogni posizione i-esima ha un valore 1<n<k che rappresenta l'appartenenza dell'i-esimo vertice alla partizione n-esima. Dopo |V| guess avrai tutte le possibili istanze (in numero pari a K|V|). Come esempio si può prendere un triangolo con attaccato un vertice. Quindi la rappresentazione è un vettore di 4 elementi ciascuno identifica un vertice. Nel vettore ci memorizzi una partizione di appartenenza (da 1 a 4 siccome al massimo puoi avere 4 partizioni). Dopo ogni guess riempo una posizione da destra verso sinistra con un numero. I rami generati fissano un numero. Dopo 4 guess ho tutte le mie 64 combinazioni. Adesso devo determinare un algoritmo di costo polinomiale che presa una qualsiasi combinazione determina se è una istanza yes. Un possibile algoritmo di costo quadratico è: scandisco ogni elemento del vettore; per ognuno scandisco tutti i suoi successivi; per ogni coppia determino se appartengono alla stessa partizione (se il vettore in corrispondenza delle due posizioni contiene lo stesso numero) se appartengono alla stessa partizione allora determino, con la matrice di adiacenze (supposta riempita), se i vertici sono adiacenti; se non sono adiacenti allora l'istanza è no.