I. Problemi di Connessione e Ricerca di Sotto-Strutture Ottimali¶
1. Problema dell'Albero di Supporto a Peso Minimo (Minimum Spanning Tree - MST)¶
Il problema MST consiste nell'individuare, in un grafo $G=(V, E)$, un sottoinsieme di archi $E_T \subset E$ tale che il grafo parziale $(V, E_T)$ sia un albero di supporto (ovvero sia connesso e aciclico) e che il suo costo/peso totale $w(T) = \sum_{(i, j) \in E_T} w_{ij}$ sia minimo. Gli algoritmi per la risoluzione dell'MST (come l'algoritmo greedy, MST-1 e MST-2) rientrano nella classe P, in quanto hanno tutti complessità polinomiale. Ad esempio, l'algoritmo greedy per MST richiede $O(|E| \log(|E|))$ operazioni.
2. Problemi di Matching (Accoppiamento)¶
Un matching $M$ in un grafo non orientato è un sottoinsieme di archi $M \subseteq A$ tale che per ogni nodo esiste al massimo un arco in $M$ incidente su quel nodo (ovvero, non ci sono archi adiacenti tra loro). - Problema di Matching di Peso Massimo: Si cerca un matching $M$ che massimizzi il peso totale $w(M) = \sum_{(i, j) \in M} w_{ij}$. - Problema di Matching di Cardinalità Massima su Grafi Bipartiti: Un caso particolare in cui il grafo $G$ è bipartito e tutti i pesi sono unitari ($w_{ij} = 1$), e l'obiettivo è massimizzare la cardinalità $|M|$. Questo problema può essere riformulato come problema di flusso massimo su un grafo orientato ausiliario. - Problema di Assegnamento: Problema che coinvolge un grafo bipartito completo $G = (V_1 \cup V_2, A)$ con $|V_1| = |V_2| = n$. L'obiettivo è trovare un matching di cardinalità $n$ (un accoppiamento che copra tutti i nodi) che minimizzi il costo totale $d(M)$. L'Algoritmo Ungherese è un approccio risolutivo per questo problema.
3. Problemi di Sottoinsiemi di Nodi¶
Questi problemi, che sono equivalenti tra loro, sono classificati come NP-completi e sono considerati "difficili": - Problema del Massimo Insieme Indipendente: Trovare il sottoinsieme di nodi $I$ di cardinalità massima in cui nessuna coppia di nodi è collegata da un arco. - Problema di Massima Clique: Trovare il sottoinsieme di nodi $C$ (una clique) di cardinalità massima in cui tutti i nodi sono collegati tra loro da archi. - Un insieme indipendente in un grafo $G$ è una clique del suo grafo complementare $\bar{G}$, dimostrando l'equivalenza dei due problemi.
II. Problemi di Cammino e Ciclo¶
1. Problema del Cammino Minimo (Shortest Path - SP)¶
Il problema SP consiste nel trovare un cammino orientato $P$ da un nodo sorgente $o$ a un nodo destinazione $d$ che minimizzi la sua lunghezza totale $f(P)$, data dalla somma delle distanze $d_{ij}$ degli archi che lo compongono. - L'algoritmo di Programmazione Dinamica (PD) per SP è noto come Algoritmo di Dijkstra. Tale algoritmo ha complessità polinomiale $O(m + n \log(n))$ se implementato con un binary heap, dove $n=|V|$ e $m=|A|$. - L'Algoritmo A è una variante di Dijkstra che utilizza una funzione euristica $h(i)$ per limitare dal di sotto la distanza dal nodo target $d$ e migliorare l'efficienza. - Esiste anche il Problema SP con vincolo di risorsa*, dove lo stato è definito da una tripletta $(i, \ell_i, \rho_i)$ per tenere conto sia della lunghezza $\ell_i$ che del consumo di risorsa $\rho_i$, limitato da una disponibilità massima $R$.
2. Problema del Commesso Viaggiatore (Traveling Salesman Problem - TSP)¶
In un grafo completo, il problema TSP consiste nel trovare un circuito hamiltoniano di distanza totale minima $f(C)$. Un circuito hamiltoniano è un ciclo che tocca tutti i nodi del grafo una e una sola volta. - Il numero di circuiti hamiltoniani è elevato (ad esempio, $(n-1)!$ nel caso asimmetrico), il che rende l'enumerazione completa inaccettabile anche per grafi di piccole dimensioni. - Il TSP è un problema NP-completo. Non sono noti algoritmi di complessità polinomiale in grado di risolverlo. - Gli approcci euristici per il TSP includono l'algoritmo greedy e la ricerca locale 2opt, i quali hanno complessità polinomiale ma non garantiscono di trovare soluzioni ottime. - Il Problema TSP metrico è un caso speciale in cui le distanze sono simmetriche e soddisfano la disuguaglianza triangolare. Per il TSP metrico, l'algoritmo Double Spanning Tree (DST) è un algoritmo di 1-approssimazione.
III. Problemi di Flusso di Rete¶
I problemi di flusso riguardano l'instradamento di quantità di prodotto o dati attraverso una rete rappresentata da un grafo orientato.
1. Problema di Flusso Massimo¶
L'obiettivo è massimizzare il flusso totale $F(x)$ che esce dalla sorgente $S$ e arriva alla destinazione $D$, rispettando i vincoli di equilibrio (flusso uscente = flusso entrante) per tutti i nodi intermedi $i \in V \setminus {S, D}$ e le capacità degli archi $0 \le x_{ij} \le d_{ij}$. - L'Algoritmo di Ford-Fulkerson risolve questo problema implementando la ricerca locale. - Relazione Taglio Minimo/Flusso Massimo: Il valore ottimo del problema di flusso massimo è uguale al valore ottimo del problema del taglio a costo minimo. Quest'ultimo consiste nel trovare un taglio della rete $S_U$ (un insieme di archi che separano $S$ da $D$) con costo minimo.
2. Problema di Flusso a Costo Minimo¶
L'obiettivo è trovare un flusso ammissibile $x$ che rispetti i vincoli di bilancio in ogni nodo (la differenza tra flusso uscente e entrante deve essere pari a $b_i$, dove $b_i$ è la quantità realizzata/rivenduta) e i limiti di capacità, minimizzando il costo di trasporto totale $\sum c_{ij} x_{ij}$. - Questo problema può essere affrontato nel caso a capacità illimitate e nel caso a capacità limitate. - La soluzione ottima è associata a una base ammissibile $B$ (capacità illimitate) o a una tripla ammissibile $T$ (capacità limitate), che sono strutture finite legate agli alberi di supporto del grafo.