Ultimo dei problemi NP-HARD da risolvere con tecnica greedy e con programmazione lineare. E’ un problema che ricade nei problemi di copertura perché in input abbiamo un grafo:

$Input: G =(V,E)\space,\space undirected$

$Output: Vertex\space Cover\space G$ (con cardinalità minima)

è un problema di minimizzazione. VC è un sotto insieme che copra tutti gli archi del grafo: $V'\sube V \space t.c. \forall \space (u,v) \in E, \space u \in V' \space o \space v \in V'$

F5

<aside> 📢 Devo prendere l’insieme minimo di vertici che mi permette di accedere a tutti gli archi, senza prendere TUTTI i vertici.

</aside>

Pensa di dover metter il minor numero di telecamere possibili per andare a coprire tutte le strade.

I problemi di questo tipo, NP-HARD, come dicevamo prima: la loro difficoltà non è né nell’enunciarli né nel trovare una soluzione qualunque perché posso sempre andare a usare la forza bruta a tutto busso e bona, ma è conveniente come un bazuka in c***. In questo caso anche se prendo sotto insiemi piccoli comunque pago tantissimo, soprattutto se ho grafi molto grandi.

Che cosa vuol dire andare di soluzione greedy??

Quando faccio un algoritmo greedy per un problema NP Hard non mi interessa andare a trovare una sotto struttura ottima, tanto non sarei comunque in grado di andare a trovare una soluzione ottima polinomiale e quindi P = NP.

Costruisco la mia soluzione in maniera incrementale aggiungendo ad un pezzettino di soluzione in maniera ammissibile, che poi devo andare a capire quanto sia effettivamente buona rispetto all’ottimo.

La cosa più gnocca è andare tutto random, senza nemmeno stare a pensare. Del tipo: prendo nodo 3 e poi vado a fare una scelta sugli altri in cui riduco il grafo di partenza e gli archi incidenti su quel nodo. Scelgo di nuovo a caso e viene fuori per esempio il 4. e mi rimane da coprire un solo arco (1→2), quindi devo fare ancora una scelta e prendere un ultimo vertice.

Il costo dell’ottimo nella soluzione è una raggiera in cui prendo se va bene il centro e se va male tutti i raggi. Alla fine in caso spendo 1 e nell’altro n-1, quindi alla fine questo approccio random mi costa n-1

F6

Posso fare un ragionamento di prendere solamente quelli con grado maggiore. Questo potrebbe funzionare ma ci sono istanze di grafi che non riesco ad avere un rapporto tra costo di approssimazione e costo soluzione dipende da N e quindi mi attacco al tram, perché approssimo molto male.

Voglio almeno riuscire ad avere un fattore di approssimazione che sia una costante piccola e cercare di averla più piccola possibile.

Facciamo ancora un algoritmo greedy, ma invece di andare a scegliere a caso scegliamo a caso un arco e mettiamo nel cover entrambi gli estremi dell’arco e poi andiamo avanti così. Praticamente ragiono prendendo gli archi e non i nodi.

Questo modo di procedere ci permette di aver non solo in quel caso ma in tutti i casi ≤ di 2. Gli archi li vado a scegliere in maniera casuale.

foto 8, questo algoritmo va a modificare il grafo, poi se uno vuole si fa anche la copia del grafo