Esplosione combinatoria - Combinatorial explosion

In matematica , un'esplosione combinatoria è la rapida crescita della complessità di un problema a causa di come la combinatoria del problema è influenzata dall'input, dai vincoli e dai limiti del problema. L'esplosione combinatoria è talvolta usata per giustificare l'intrattabilità di certi problemi. Esempi di tali problemi includono alcune funzioni matematiche , l'analisi di alcuni enigmi e giochi e alcuni esempi patologici che possono essere modellati come funzione di Ackermann .

Esempi

piazze latine

Un quadrato latino di ordine n è un array n  ×  n con voci da un insieme di n elementi con la proprietà che ogni elemento dell'insieme si verifica esattamente una volta in ogni riga e in ogni colonna dell'array. Un esempio di quadrato latino di ordine tre è dato da,

1	2	3
2	3	1
3	1	2

Un esempio comune di quadrato latino sarebbe un puzzle di Sudoku completato . Un quadrato latino è un oggetto combinatorio (al contrario di un oggetto algebrico) poiché conta solo la disposizione delle voci e non ciò che le voci sono effettivamente. Il numero di quadrati latini in funzione dell'ordine (indipendente dalla serie da cui sono prelevati i iscrizioni) (sequenza A002860 in OEIS ) fornisce un esempio di esplosione combinatoria come illustrato dalla seguente tabella.

sudoku

Un'esplosione combinatoria può verificarsi anche in alcuni enigmi giocati su una griglia, come il Sudoku. Un Sudoku è un tipo di quadrato latino con la proprietà aggiuntiva che ogni elemento si verifica esattamente una volta nelle sottosezioni di dimensione √ n  ×  √ n (chiamate caselle ). L'esplosione combinatoria si verifica all'aumentare di n , creando limiti alle proprietà dei Sudoku che possono essere costruiti, analizzati e risolti, come illustrato nella tabella seguente.

Giochi

Un esempio in un gioco in cui la complessità combinatoria porta a un limite di risolvibilità è nella risoluzione degli scacchi (un gioco con 64 caselle e 32 pezzi). Gli scacchi non sono un gioco risolto . Nel 2005 sono stati risolti tutti i finali delle partite di scacchi con sei pezzi o meno, mostrando il risultato di ogni posizione se giocata perfettamente. Ci sono voluti altri dieci anni per completare la base del tavolo con l'aggiunta di un altro pezzo degli scacchi, completando così una base del tavolo da 7 pezzi. Aggiungere un pezzo in più a un finale di scacchi (creando così una base di 8 pezzi) è considerato intrattabile a causa della complessità combinatoria aggiunta.

Inoltre, la prospettiva di risolvere giochi simili a scacchi più grandi diventa più difficile all'aumentare delle dimensioni della scacchiera, come nelle varianti di scacchi grandi e negli scacchi infiniti .

informatica

L'esplosione combinatoria può verificarsi negli ambienti informatici in modo analogo alle comunicazioni e allo spazio multidimensionale . Immagina un sistema semplice con una sola variabile, un booleano chiamato A . Il sistema ha due possibili stati, A = vero o A = falso. L'aggiunta di un'altra variabile booleana B darà al sistema quattro possibili stati, A = vero e B = vero, A = vero e B = falso, A = falso e B = vero, A = falso e B = falso. Un sistema con n booleani ha 2 ⁿ stati possibili, mentre un sistema di n variabili ciascuna con Z valori consentiti (piuttosto che solo i 2 (vero e falso) dei booleani) avrà Z ⁿ stati possibili.

I possibili stati possono essere pensati come i nodi foglia di un albero di altezza n , dove ogni nodo ha Z figli. Questo rapido aumento dei nodi foglia può essere utile in aree come la ricerca , poiché è possibile accedere a molti risultati senza dover scendere molto lontano. Può anche essere un ostacolo durante la manipolazione di tali strutture.

Una gerarchia di classi in un linguaggio orientato agli oggetti può essere pensata come un albero, con diversi tipi di oggetti che ereditano dai loro genitori. Se è necessario combinare diverse classi, come in un confronto (come A  <  B ), il numero di possibili combinazioni che possono verificarsi esplode. Se ogni tipo di confronto deve essere programmato, questo diventa presto intrattabile anche per un piccolo numero di classi. L'ereditarietà multipla può risolvere questo problema, consentendo alle sottoclassi di avere più genitori, e quindi è possibile considerare alcune classi padre anziché ogni figlio, senza interrompere alcuna gerarchia esistente.

Un esempio è una tassonomia in cui diverse verdure ereditano dalle loro specie antenate. Il tentativo di confrontare la bontà di ogni verdura con le altre diventa intrattabile poiché la gerarchia contiene solo informazioni sulla genetica e non fa menzione della bontà. Tuttavia, invece di dover scrivere confronti per carota/carota, carota/patata, carota/germoglio, patata/patata, patata/germoglio, germoglio/germoglio, possono tutti moltiplicarsi ereditando da una classe separata di gustosi mantenendo il loro attuale antenato. gerarchia basata, quindi tutto quanto sopra può essere implementato solo con un confronto gustoso/gustoso.

Aritmetica

Supponiamo di prendere il fattoriale di n :

${\displaystyle n!=n\cdot (n-1)\cdot \ldots\cdot 2\cdot 1}$

Allora 1! = 1, 2! = 2, 3! = 6 e 4! = 24. Tuttavia, arriviamo rapidamente a numeri estremamente grandi, anche per n relativamente piccoli . Ad esempio, 100! ?9.332 621 54 × 10 ¹⁵⁷ , un numero così grande che non può essere visualizzato sulla maggior parte dei calcolatori e molto più grande del numero stimato di particelle fondamentali nell'universo.

Comunicazione

Utilizzando linee di comunicazione separate, quattro organizzazioni richiedono sei canali

Utilizzando un intermediario, è richiesto un solo canale per organizzazione

Nell'amministrazione e nell'informatica , un'esplosione combinatoria è l'aumento in rapida accelerazione delle linee di comunicazione man mano che le organizzazioni vengono aggiunte in un processo. (Questa crescita è spesso descritta casualmente come "esponenziale", ma in realtà è polinomiale .)

Se due organizzazioni hanno bisogno di comunicare su un particolare argomento, potrebbe essere più semplice comunicare direttamente in modo ad hoc: è necessario un solo canale di comunicazione . Tuttavia, se viene aggiunta una terza organizzazione, sono necessari tre canali separati. L'aggiunta di una quarta organizzazione richiede sei canali; cinque dieci; sei quindici; eccetera.

In generale, ci vorranno linee di comunicazione per n organizzazioni, che è solo il numero di 2- combinazioni di n elementi (vedi anche coefficiente binomiale ). ${\displaystyle l={\frac {n(n-1)}{2}}={n \scegli 2}}$

L'approccio alternativo consiste nel rendersi conto quando questa comunicazione non sarà un requisito una tantum e produrre un modo generico o intermedio di trasmissione delle informazioni. Lo svantaggio è che ciò richiede più lavoro per la prima coppia, poiché ciascuno deve convertire il proprio approccio interno in quello comune, piuttosto che l'approccio superficialmente più semplice di comprendere semplicemente l'altro.

Guarda anche

Riferimenti