1.4 Esplosione combinatoria e forza bruta¶
Parte 1 · Problemi di ottimizzazione combinatoria · Capitolo 1 · Capitolo 1: Ottimizzazione combinatoria · Dispensa, volume 1 (PDF) · Slide · Esercizi: Ottimizzazione combinatoria · App: Forza bruta sul problema dello zaino 0/1
- Poiché la regione ammissibile è finita, un problema di ottimizzazione combinatoria si può sempre risolvere per enumerazione completa: elenchiamo tutte le soluzioni candidate, scartiamo quelle non ammissibili e teniamo la migliore. Questo algoritmo si chiama forza bruta.
Algoritmo
-
Input: un'istanza di un problema di ottimizzazione combinatoria in forma di massimo.
-
Output: una soluzione ottima e il valore ottimo.
-
Passo 0: Inizializzazione. Porre \(\bar S \leftarrow\) nessuna e \(\LB \leftarrow -\infty\).
-
Passo 1: Enumerazione. Per ogni soluzione candidata \(S\) (sottoinsieme, ordinamento, partizione):
-
se \(S\) non è ammissibile, scartarla;
-
se \(S\) è ammissibile e \(f(S) > \LB\), porre \(\bar S \leftarrow S\) e \(\LB \leftarrow f(S)\).
-
-
Passo 2: Output. Restituire \(\tilde S = \bar S\) e \(z(I) = \LB\).
STOP
Esempio 1.3: forza bruta sulla piccola istanza
Per l'istanza dell'Esempio 1.1 i \(2^4=16\) sottoinsiemi di \(\mathscr{U}\) sono:
| \(S\) | \(f(S)\) | ammissibile | \(S\) | \(f(S)\) | ammissibile |
|---|---|---|---|---|---|
| \(\emptyset\) | \(0\) | sì | \(\{2,3\}\) | \(10\) | sì |
| \(\{1\}\) | \(7\) | sì | \(\{2,4\}\) | \(9\) | sì |
| \(\{2\}\) | \(6\) | sì | \(\{3,4\}\) | \(7\) | sì |
| \(\{3\}\) | \(4\) | sì | \(\{1,2,3\}\) | \(17\) | no |
| \(\{4\}\) | \(3\) | sì | \(\{1,2,4\}\) | \(16\) | no |
| \(\{1,2\}\) | \(13\) | no | \(\{1,3,4\}\) | \(14\) | no |
| \(\{1,3\}\) | \(11\) | sì | \(\{2,3,4\}\) | \(\mathbf{13}\) | sì |
| \(\{1,4\}\) | \(10\) | sì | \(\{1,2,3,4\}\) | \(20\) | no |
Fra gli \(11\) sottoinsiemi ammissibili, il migliore è \(\tilde S = \{2,3,4\}\), con \(z(I)=13\). È l'unica soluzione ottima: anche il sottoinsieme \(\{1,2\}\) ha valore \(13\), ma non è ammissibile.
1.4.1 Crescita esponenziale¶
- La forza bruta funziona per le piccole istanze viste sopra, ma il numero di candidate cresce molto rapidamente con la dimensione \(n\) dell'istanza. La tabella seguente confronta la crescita polinomiale e quella esponenziale.
1.4.2 Tempi di calcolo¶
- Supponiamo che un calcolatore valuti \(10^9\) soluzioni candidate al secondo, e calcoliamo il tempo di un'enumerazione completa (un anno \(=365.25\) giorni):
| \(n\) | \(2^n\) | tempo a \(10^9\) al secondo | tempo a \(10^{12}\) al secondo |
|---|---|---|---|
| \(10\) | \(1\,024\) | \(\approx 1.02\) microsecondi | \(\approx 1.02\) nanosecondi |
| \(20\) | \(\approx 1.05 \cdot 10^{6}\) | \(\approx 1.05\) millisecondi | \(\approx 1.05\) microsecondi |
| \(30\) | \(\approx 1.07 \cdot 10^{9}\) | \(\approx 1.07\) secondi | \(\approx 1.07\) millisecondi |
| \(40\) | \(\approx 1.10 \cdot 10^{12}\) | \(\approx 18.3\) minuti | \(\approx 1.10\) secondi |
| \(50\) | \(\approx 1.13 \cdot 10^{15}\) | \(\approx 13.0\) giorni | \(\approx 18.8\) minuti |
| \(60\) | \(\approx 1.15 \cdot 10^{18}\) | \(\approx 36.5\) anni | \(\approx 13.3\) giorni |
| \(70\) | \(\approx 1.18 \cdot 10^{21}\) | \(\approx 3.74 \cdot 10^{4}\) anni | \(\approx 37.4\) anni |
| \(80\) | \(\approx 1.21 \cdot 10^{24}\) | \(\approx 3.83 \cdot 10^{7}\) anni | \(\approx 3.83 \cdot 10^{4}\) anni |
| ordinamenti ciclici: \((n-1)!/2\) | partizioni: \(B(n)\) | ||||
|---|---|---|---|---|---|
| \(n\) | numero | \(10^9\) al secondo | \(10^{12}\) al secondo | numero | \(10^9\) al secondo |
| \(10\) | \(181\,440\) | \(\approx 181\) microsecondi | \(\approx 181\) nanosecondi | \(115\,975\) | \(\approx 116\) microsecondi |
| \(15\) | \(\approx 4.36 \cdot 10^{10}\) | \(\approx 43.6\) secondi | \(\approx 43.6\) millisecondi | \(\approx 1.38 \cdot 10^{9}\) | \(\approx 1.38\) secondi |
| \(20\) | \(\approx 6.08 \cdot 10^{16}\) | \(\approx 1.93\) anni | \(\approx 16.9\) ore | \(\approx 5.17 \cdot 10^{13}\) | \(\approx 14.4\) ore |
| \(25\) | \(\approx 3.10 \cdot 10^{23}\) | \(\approx 9.83 \cdot 10^{6}\) anni | \(\approx 9.83 \cdot 10^{3}\) anni | \(\approx 4.64 \cdot 10^{18}\) | \(\approx 147\) anni |
- Un calcolatore \(1000\) volte più veloce non cambia il quadro: poiché \(2^{10} = 1024 > 1000\), nello stesso tempo enumera i sottoinsiemi di soli \(10\) elementi in più, circa. Per gli ordinamenti ciclici il guadagno è ancora minore: passare da \(n\) a \(n+1\) elementi moltiplica il loro numero per \(n\), e \(15 \cdot 16 \cdot 17 = 4080 > 1000\), quindi da \(15\) elementi in su il calcolatore più veloce guadagna meno di \(3\) elementi.
L'enumerazione completa è possibile solo per istanze molto piccole. Calcolatori più veloci non aiutano: un numero esponenziale di candidate vanifica qualunque accelerazione costante. Servono approcci più intelligenti, che escludono intere parti dello spazio delle soluzioni senza esplorarle.