2.11 Lezione 11
L'algoritmo di per sè è un algoritmo abbastanza semplice:
public void sort(String[] a){
int n = a.length;
MaxPQ<String> pq = new MaxPQ<String>();
for(int i = 0; i < n; i++)
pq.insert(a[i]);
for(int i = n-1; i >= 0; i--)
a[i] = pq.delMax();
}Facendo l'operazione delMax() struttura dati si riconfigurerà seguendo il sink down.
- Vedere l'array come un albero binario completo.
- Costruzione dell'heap: costruire un max-heap con tutte le n chiavi.
- Sortdown: rimuovere ripetutamente la chiave maggiore.
Per le ultime due fasi osserviamo i passi:
- nella prima fase ho le chiavi in un ordine arbitrario, quindi la prima cosa da fare è costruire l'heap.
- Costruisco quindi un maxHeap;
- Ad ogni passo predno l'elemento radice (sicuramente il più grande) e lo pongo nella posizione giusta.
- Quando faccio la rimozione devo capire quale sarà il prossimo massimo:
- Effettuo la sostituzione tra il primo elmento ed ultimo elemento utile
- Successivamente, effettuo il sink down.
Potremmo pensare di utilizzare lo swim e partire da sinistra verso destra, per ordinare le varie chiavi, ma un modo più intelligente di procedere è invece partire da destra verso sinistra.
Questo perchè, se considero ogni nodo come se fosse un sotto-heap, vuol dire che posso partire a fare il sink down, partendo dalla metà dell'array, in quanto per metà dell'array i nodi sono foglia, ovvero non hanno figli.
Dato una collezione di 11 elementi, partiamo quindi dalla posizione 5, visto che 11/2 ~ 5.
- vado a confrontare il nodo corrente (5) con i nodi figli.
- Dobbiamo Rispettare le proprietà dell'heap, se l'heap non è ordinato, effettuiamo lo scambio con il figlio.
- Decremento l'indice, quindi da 5 passiamo al nodo 4.
- Ancora una volta controllo la proprietà dell'heap, se essa è rispettata decremento ancora, altrimenti effettuo uno scambio.
- Se mi trovo in un caso in cui l'ordine non viene rispettato, quindi effettuo uno scambio con un figlio, e poi anche dopo aver effettuato lo scambio, il nuovo figlio ancora una volta non rispetta l'ordine, continuo a scambiare (sink down) finchè non rispetto l'ordine dell'heap.
Clicca sull'immagine per aprire il video su YouTube
Il primo passo consiste nel costruire un Heap usando un metodo bottom up, ovvero non partiamo dalla radice, ma partiamo dalla metà dell'heap.
for(int k = n/2; k <= 1; k--)
sink(a, k, n);Nel secondo passo, invece:
- Eliminiamo il massimo, uno alla volta.
- Lasciamo gli elementi nell'array, invece di porli a null
while (n > 1){
exch(a, 1, n--);
sink(a, 1, n);
}public class Heap{
public static void sort(Comparable[] a){
int n = a.length;
for(int j = n/2; k>=1; k--)
sink(a, k, n);
while(n > 1){
exch(a, 1, n);
sink(a, 1, n--);
}
}
private static void sink(){/**come prima*/}
private static boolean less(){/**come prima*/}
private static void exch(){/**come prima*/}
}vogliamo dimostrare che per fare la costruzione dell'heap, impieghiamo n scambi e 2n confronti.
Assumiamo che n sia uguale a 22h+1-1, ad esempio, in un albero completo con profondità 3, avremo 15 elementi.
Otteniamo quindi la somma, per ogni nodo, pari a:
h + 2(h -1) + 4(h - 2) + 8(h - 3) + ... + 2^h (0) = 2<sup>h+1</sup> - h - 2
= N - (h - 1)
< = N
Abbiamo quindi dimostrato che per costruire l'heap facciamo al massimo N exchanges.
Per effettuare uno scambio, dobbiamo fare due confronti (perchè dobbiamo capire qual è il massimo tra i due figli di ogni nodo) di conseguenza, dimostriamo che utilizziamo al più 2 n confronti.
Per effettuare il delMax, l'heapsort utilizza al più 2 n lg n confronti e scambi.
Obbiettivo: Simulare il movimento di n particelle in movimento che si comportano secondo le leggi delle collisioni elastiche all'interno di un "contenitore".
- Le particelle in movimento interagiscono attraverso urti elastici con altre particelle o con le pareti del contenitore.
- Ogni particella è rappresentata da un disco con i seguenti attributi noti:
- Posizione
- velocità
- massa
- radio
- Non sono presenti altre forze (come l'attrito). Questo punto implica che le particelle viaggiano in un moto rettilineo e a velocità costante.
Per simulare questo modello, possiamo pensare di tenere traccia della velocità e della posizione durante il tempo per ogni particella.
Data la posizione e la velocità all'istante di tempo t, possiamoa aggiornare per ogni particella posizione e velocità per riflettere la situazione che si verrà a verificare all'istante di tempo t + Δ t.
public class BouncingBalls{
public static void main(String[] args){
int n = Integer.parseInt(args[0]);
Ball[] balls = new Ball[n];
for(int i = 0; i < n; i+)
balls[i] = new Ball();
while(true){
StdDraw.clear();
for(int i = 0; i < n; i++){
balls[i].move(0.5);
balls[i].draw();
}
StdDraw.show(50);
}
}
}Classe principale
public class Ball{
private double rx, ry;
private double vx, vy;
private final double radius;
public Ball(...){
//inizializzo le variabili d'istanza
}
public void move(double dt){
if((rx + vx*dt < radius) || (rx + vx*dt > 1.0 - radius)){
vx = -vx;
}
if((ry + vy*dt < radius) || (ry + vy*dt > 1.0 - radius)){
vy = -vy;
}
rx = rx + vx*dt;
ry = ry + vy*dt;
}
public void draw(){
StdDraw.filledCircle(rx, ry, radius);
}
}Classe Ball
La fisica può dirci quando avverà una collisione e quali saranno gli effetti, quindi possiamo ricalcolare la posizione di ogni palla.
I problemi relativi all'algoritmo, risiedono sopratutto in alcune domande:
- Quale oggetto farà i controlli?
- È necessario eseguire molti controlli, in quanto ad ogni istante di tempo t devo verificare le collisioni con le pareti e con ogni altra particella.
La time driven simulation consiste di discretizzare il tempo ad intervalli Δt, aggiornare la posizione di ogni particella dopo ogni intervallo di tempo e controllare le sovrapposizioni. Nel caso ci siano delle sovrapposizioni, torniamo fino al momento della collisione e riaggiornare il tutto.
Questo modello presenta una serie di problemi, infatti per ogni istante di tempo è necessario controllare circa n2 / 2 collisioni, in quanto dobbiamo verificare per ogni coppia di particelle se c'è una collisione. Inoltre la scelta di Δt è decisiva, inquanto se essa è troppo piccola la simulazione sarà molto lenta, mentre se è troppo grande potremmo perderci delle collisioni.
Possiamo quindi pensare ad un approccio alternativo, che si focalizza sugli istanti di tempo in cui le collisioni si verificano, visto che le particelle, muovendosi di moto rettilineo uniforme, sappiamo, per via del moto, quando una collisione avverrà. Quindi, invece di aspettare che una collisione avvenga, prevediamo quando questa avverrà, attraverso le leggi della fisica, e la simuliamo.
Possiamo quindi usare una coda a priorità delle collisioni, dove la priorità di ogni collisione è dettata dal tempo. Ogni elemento nella coda è una collisione potenziale, che avviene tra le particelle o una parete.
Andare a rimuovere un elemento dalla coda, significa prendere il prossimo evento di collisione e processarlo. Per l'implementazione di questo tipo di approccio abbiamo bisogno di algoritmi per la predizione delle collisioni e di collision resolution, ovvero se una collisione si verifica è necessario aggiornare le particelle a seconda delle leggi degli urti elastici.
La velocità delle particelle fornisce esattamente le informazioni di cui abbiamo bisogno:
Supponiamo che ad un tempo t abbiamo una particella di raggio s alla posizione (rx, ry) che si muove ad una velocità (vx, vy).
Ad esempio consideriamo la parete verticale:
- Per semplicità diciamo che la parete corrisponde ad un x = 1 (retta) ed un y compreso tra 0 ed 1. Siccome stiamo verificando la collisione tra una particella e la parete veritcale, siamo interessati alla componente orizzontale del moto, motivo per cui ci concentriamo sulla componente x della posizione e della componente x della velocità.
Se la velocità vx è negativa, non ci sarà una collisione, in quanto la particella si muove nel verso opposto alla parete.
Se essa è positiva ci sarà una potenziale collisione con la parete verticale.