Spazio delle soluzioni Flashcards
Quali strutture dati si utilizzano tipicamente per le funzioni di calcolo combinatorio?
typedef struct l { int *scelte; int n_scelte; } Livello;
int *val; oppure Livello *val;
int *mark;
int *sol;
Principio di moltiplicazione: esempio
poké: 3 di una, 2 dell’altro, ecc.
32…
Principio di moltiplicazione: codice
int princ_molt(int pos, Livello *val, int *sol, int n, int cnt){
int i;
if(pos >= n){
for(i = 0; i < n; i++) printf(“%d”, sol[i]);
return cnt+1;
}
for(i = 0; i < val[pos].n_scelte; i++){
sol[pos] = val[pos].scelte[i];
cnt = princ_molt(pos+1, val, sol, n, cnt);
}
return cnt;
}
Disposizioni semplici: esempio
Raggruppamento k a k, senza ripetizione
n!/(n-k)!
per esempio: quanti numeri di due cifre distinte si possono formare con 4 cifre totali?
Disposizioni semplici: codice
int dispiace_semplici(int pos, int val, intsol, int *mark, int k, int n, int cnt){ int i;
if(pos >= k){
// stampa sol
return cnt+1;
}
for (i = 0; i < n; i++){
if (mark[I] == 0){
mark[i] = 1;
sol[pos] = val[I];
cnt = disp_sempl(pos + 1, val, sol, mark, k, n, cnt);
mark[i] = 0;
}
}
return cnt;
}
Disposizioni con ripetizione: esempio
elementi k a k, non distinti
n^k;
esempio: quanti sono i numeri binari su 4 bit?
2^4
Disposizioni con ripetizione: codice
int disp_rip(int pos, int * val, int *sol, int n, int k, int cnt){
if (pos>=k){
//stampa sol
return cnt+1;
}
for(i = 0; i < n; i++){
sol[pos] = val[I];
cnt = disp_rip(pos+1, val, sol, n, k, cnt);
}
return cnt;
}
Permutazioni semplici: esempio
n!
Permutazioni con ripetizione: esempio
n!/a!B!…
Permutazioni semplici: codice
int permutazioni_semplici(int pos, int val, intsol, int * mark, int n, int cnt){
if (pos>=n){ // stampa return cnt+1;}
for (int i = 0; i < n; i++){
if (mark[I] == 0){
mark[i] = 1;
sol[pos] = val[I];
cnt = permutazioni_semplici(pos +1, val, sol, mark, n, cnt);
mark[i] = 0;
}
}
return cnt;
}
Permutazioni con ripetizione: codice
int perm_r(int pos, int *dist_val, int n_dist, int *sol, int *mark, int n, int cnt){
if (pos >= n) {
// stampa
return cnt+1;
}
for(int i = 0; i < n_dist; i++){
if(mark[I] > 0){
mark[i]–;
sol[pos] = dist_val[i];
cnt = perm_r(pos+1, dist_val, n_dist, sol, mark, n, cnt);
mark[i]++;
}
}
return cnt;
}
Combinazioni semplici: esempio
in quanti modi si possono stringere la mano 20 persone?
binomiale (20 2)
Combinazioni semplici: codice
int comb_s(int pos, int *val, int *sol, int n, int k, int start, int cnt){
if (pos >= k) {…}
for(int i = start; i < n; i ++){
sol[pos] = val[I];
cnt = comb_s(pos+1, val, sol, n, k, I+1, cnt);
}
return cnt;
}
Combinazioni con ripetizione: esempio
Date 5 gocce bianche e 5 nere, quanti colori diversi si possono formare mischiando tra loro 5 gocce prese dai due colori?
binomiale (n+k-1)/k
Combinazioni con ripetizione: codice
int comb_r(int pos, int *val, int *sol, int n, int k, int start, int cnt){
if (pos >= k) {…}
for(i = start; I < n; i++){
sol[pos] = val[I];
cnt = comb_r(pos+1, val, sol, n, k, start, cnt);
}
return cnt;
}
Dato un insieme I, quando i blocchi in cui è diviso sono una sua partizione?
Dato un insieme I e S_i sottoinsiemi ciascuno di k_i elementi, essi sono una partizione di I se:
- ogni blocco non è vuoto
- e sono tutti disgiunti
- e la loro somma dà l’insieme I
Data la partizione di un insieme, l’ordine dei blocchi e degli elementi in essi conta?
NO
Dato un insieme I, quale può essere il numero complessivo di partizioni?
Il numero complessivo di partizioni è definito dai numeri di Bell: 1, 1, 2, 5, 15, 52
Quali modelli ci sono per calcolare l’insieme delle parti?
- paradigma divide et impera
- disposizioni ripetute
- combinazioni semplici
Insieme delle parti con paradigma divide et impera, caratteristiche
per k = 0 viene ritornato l’insieme vuoto, per k > 0 l’insieme delle parti per k elementi è l’insieme delle parti per k-1 elementi a cui decido se aggiungere o meno il kesimo elemento -> due rami ricorsivi distinti
Insieme delle parti con disposizioni ripetute, caratteristiche
- in sol gli elementi sono o 0 o 1 p
- bisogna scegliere se prendere il k-esimo elemento (sol[pos] = 1) oppure no (sol[pos] = 0) e per questo ci sono due rami ricorsivi distinti
Insieme delle parti con combinazioni semplici, caratteristiche
c’è una funzione wrapper che chiama la funzione ricorsiva con k diverso ogni volta (k: numero degli elementi)
Come si possono rappresentare le partizioni di un insieme?
- per ogni elemento si indica il blocco a cui appartiene
- dato ogni blocco se ne elencano gli elementi
Numero casuale di partizioni con disposizioni ripetute
appunti
algoritmo di Er
appunti
Quali sono le possibilità per chiudere le ritorsioni quando si vuole una sola soluzione?
1) flag come variabile globale o come parametro by reference
2) funzione ricorsiva che ritorna una valore di successo o fallimento che viene testato
cosa si intende per pruning?
è la riduzione dello spazio di ricerca che non porta alla perdita di informazioni o di completezza, ma che scarta a priori i riami dell’albero delle soluzioni che sicuramente falliranno, seguendo vincoli he permettano di non perdere soluzioni
metodologie di anticipazione dei vincoli
non c’è una metodologia generale. tipicamente i casi sono:
- filtro statico sulle scelte: condizioni che dipendono dal problema e non dalle scelte precedenti
- filtro dinamico: dipendono da entrambe le cose
- speranza
