Il problema suona così: otteniamo n-cubi. Ogni cubo ha una lunghezza (la "lunghezza del bordo") e un colore. Le lunghezze dei bordi sono distinte, ma i bordi non lo sono, ad esempio: due cubi non possono mai avere la stessa lunghezza, ma è possibile avere la stessa colore. I colori vanno da 1 a p (viene indicato p).
Dobbiamo costruire una torre cubica che abbia un'altezza massima, seguendo queste regole:
1) un cubo non può essere posizionato su un cubo se hanno lo stesso colore;
2) un cubo non può essere posizionato su un cubo la cui lunghezza del bordo è inferiore.
ad esempio: il cubo c1 ha una lunghezza di 3, il cubo c2 ha una lunghezza di 5. il cubo c1 può essere posizionato sulla parte superiore di c2, ma il cubo c2 non può essere posizionato sulla parte superiore di c1.
Bene, quindi l'algoritmo che ho ideato per risolvere questo problema è questo:
- ordiniamo i cubi per lunghezza del bordo, in ordine decrescente e li inseriamo in una matrice;
- aggiungiamo il primo cubo nella matrice alla Torre;
- salviamo la lunghezza dell'ultimo cubo inserito (in questo caso, la lunghezza del primo cubo) nella variabile l;
- salviamo il colore dell'ultimo cubo inserito (in questo caso, il colore del primo cubo) nella variabile c;
- esaminiamo il resto dell'array, inserendo il primo cubo la cui lunghezza è più piccola di l e il colore è diverso da c e quindi ripetiamo 3-4-5;
Ora, ciò con cui ho difficoltà è, come posso dimostrare che questo avido algoritmo sia quello ottimale? Immagino che la prova debba in qualche modo assomigliare a quella qui: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/04GreedyAlgorithmsI-2x2.pdf
risposte:
2 per risposta № 1La domanda è:
- Esiste un caso in cui la raccolta del cubo di lunghezza massima non è ottimale?
Ad ogni nodo decisionale dobbiamo decidere se scegliamo un o B, dato A> B:
Supponiamo che il picking b sia strettamente ottimale (implica l'altezza massima):
- Caso 1:
col(a) == col(b) b optimal => final tower: b, x0, x1, ...- ma valido anche per costruzione con uguale altezza:
a, x0, x1, ... - valido perché:
col(a) == col(b),(a > b) & (b > x0) => (a > x0)(Transitività) contraddizione!
Caso 2
col(a) != col(b)b optimal -> final tower: b, x0, x1, ...- ma anche costruzione valida con più altezza:
a, b, x0, x1, ... - valido perché:
(a > b) & (col(a) != col(b)) => a before b - contraddizione!
Abbiamo ipotizzato che la raccolta b sia strettamente ottimale e mostrasse contraddizioni. Scegliere b può essere ugualmente buono o peggio che scegliere a (il cubo di lunghezza massima di quelli rimanenti).