Albero->Chiavi->Peso->ProgrDinam[risoltoOnlyReferee]
Dobbiamo costruire un albero di ricerca che contiene $n$ chiavi $k_1 < k_2 < ... < k_n$
Ciascuna delle chiavi ha un peso associato $p_i$ che rappresenta la frequenza (data) con cui si stima che la chiave venga ricercata. Per semplicità assumiamo che la radice dell'albero sia a livello $1$, il costo dell'albero di ricerca per le $n$ chiavi viene definito come $\sum_{i=1}^{n} (p_i * l_i)$ dove $l_i$ è il livello dell'albero in cui si trova la chiave $k_i$.
Descrivere un algoritmo e scrivere lo pseudocodice adatto a trovare l'ABR di costo minimo con complessità minore.
Ciascuna delle chiavi ha un peso associato $p_i$ che rappresenta la frequenza (data) con cui si stima che la chiave venga ricercata. Per semplicità assumiamo che la radice dell'albero sia a livello $1$, il costo dell'albero di ricerca per le $n$ chiavi viene definito come $\sum_{i=1}^{n} (p_i * l_i)$ dove $l_i$ è il livello dell'albero in cui si trova la chiave $k_i$.
Descrivere un algoritmo e scrivere lo pseudocodice adatto a trovare l'ABR di costo minimo con complessità minore.
Risposte
Ciao Giova411 
Allora, provo a spiegarti una possibile soluzione. Supponiamo di avere: un array K (che sta per Keys) dove memorizzare le chiavi del mio albero (inizialmente nell'ordine dato $k_1, k_2, ..., k_n$), un array W (che sta per Weights) dove memorizzare i pesi associati alle chiavi del mio albero (inizialmente nell'ordine dato $p_1, p_2, ..., p_n$) ed infine un array C (che sta per Configurations) dove memorizzare di volta in volta le chiavi del mio albero risultante nell'ordine in cui forniscono la configurazione che rende in quel momento minimo il costo totale di ricerca. Per determinare la configurazione minima io procederei come segue:
[list=1]
[*:2lh5dr92]Genero tutte le possibili permutazioni di W (aggiornando di volta in volta correntemente anche K chiaramente);[/*:m:2lh5dr92]
[*:2lh5dr92]Per ciascuna permutazione generata verifico se ottengo un albero di ricerca con il K corrente;[/*:m:2lh5dr92]
[*:2lh5dr92]Se K non mi fornisce la configurazione di un albero di ricerca allora passo banalmente alla permutazione successiva;[/*:m:2lh5dr92]
[*:2lh5dr92]Se K invece mi fornisce la configurazione di un albero di ricerca allora verifico se la soluzione appena determinata è migliore rispetto a quella fornita dai valori attualmente presenti in C;[/*:m:2lh5dr92]
[*:2lh5dr92]Se la soluzione corrente è migliore allora copio i valori di K in C;[/*:m:2lh5dr92]
[*:2lh5dr92]Se la soluzione corrente non è migliore allora passo alla successiva permutazione.[/*:m:2lh5dr92][/list:o:2lh5dr92]
Una variante a questo procedimento (che secondo me ci permetterebbe di risparmiare parecchio) potrebbe essere, anziché partire generando tutte le possibili permutazioni, generare tutti i possibili alberi binari di ricerca con le chiavi date (il problema è "solo" dovuto a scegliere la radice) ed eseguire successivamente il controllo se abbiamo una soluzione migliore rispetto alla precedente o meno. Anzi, ora che ci penso sicuramente conviene per via della dimensione del nostro problema: se $n$ è il numero di nodi che abbiamo le possibili permutazioni delle chiavi sono $n!$ (numero molto alto) ma il numero di alberi binari di ricerca che possiamo generare dovrebbe essere sicuramente minore di tale quantità.
Questa sera se vuoi che ho un po' più tempo ti posso spiegare più nel dettaglio.
Allora, provo a spiegarti una possibile soluzione. Supponiamo di avere: un array K (che sta per Keys) dove memorizzare le chiavi del mio albero (inizialmente nell'ordine dato $k_1, k_2, ..., k_n$), un array W (che sta per Weights) dove memorizzare i pesi associati alle chiavi del mio albero (inizialmente nell'ordine dato $p_1, p_2, ..., p_n$) ed infine un array C (che sta per Configurations) dove memorizzare di volta in volta le chiavi del mio albero risultante nell'ordine in cui forniscono la configurazione che rende in quel momento minimo il costo totale di ricerca. Per determinare la configurazione minima io procederei come segue:
[list=1]
[*:2lh5dr92]Genero tutte le possibili permutazioni di W (aggiornando di volta in volta correntemente anche K chiaramente);[/*:m:2lh5dr92]
[*:2lh5dr92]Per ciascuna permutazione generata verifico se ottengo un albero di ricerca con il K corrente;[/*:m:2lh5dr92]
[*:2lh5dr92]Se K non mi fornisce la configurazione di un albero di ricerca allora passo banalmente alla permutazione successiva;[/*:m:2lh5dr92]
[*:2lh5dr92]Se K invece mi fornisce la configurazione di un albero di ricerca allora verifico se la soluzione appena determinata è migliore rispetto a quella fornita dai valori attualmente presenti in C;[/*:m:2lh5dr92]
[*:2lh5dr92]Se la soluzione corrente è migliore allora copio i valori di K in C;[/*:m:2lh5dr92]
[*:2lh5dr92]Se la soluzione corrente non è migliore allora passo alla successiva permutazione.[/*:m:2lh5dr92][/list:o:2lh5dr92]
Una variante a questo procedimento (che secondo me ci permetterebbe di risparmiare parecchio) potrebbe essere, anziché partire generando tutte le possibili permutazioni, generare tutti i possibili alberi binari di ricerca con le chiavi date (il problema è "solo" dovuto a scegliere la radice) ed eseguire successivamente il controllo se abbiamo una soluzione migliore rispetto alla precedente o meno. Anzi, ora che ci penso sicuramente conviene per via della dimensione del nostro problema: se $n$ è il numero di nodi che abbiamo le possibili permutazioni delle chiavi sono $n!$ (numero molto alto) ma il numero di alberi binari di ricerca che possiamo generare dovrebbe essere sicuramente minore di tale quantità.
Questa sera se vuoi che ho un po' più tempo ti posso spiegare più nel dettaglio.
"onlyReferee":
Questa sera se vuoi che ho un po' più tempo ti posso spiegare più nel dettaglio.
Ciao Prof
Guarda non ho nessuna fretta!!! Anche tra un mese! Devo cercare ti apprendere la tecnica.
Di programmazione dinamica in questo forum ne ho trovata ben poca...
Gli esempietti di PD sul "resto monetario", "confronto caratteri" etc l'ho capiti e stra-digeriti... Devo fare il salto ora!
In teoria dovrei confrontare meglio soluzioni trovate che siano "simili" a questa.
Allora, in linea di principio prima di ragionare sul codice (che a te piace tantissimo 
) nella programmazione dinamica bisogna analizzare attentamente l'individuazione dei sottoproblemi da risolvere. Se si considera il nostro scopo, ossia avere un albero di costo minimo, si nota come la formula per calcolare il costo dello stesso dipenda da due parametri essenzialmente: i pesi ed il numero di livelli. Ora, poiché i pesi sono quelli assegnati alle varie chiavi e non possiamo di certo pensare di cambiarli e considerando che le chiavi vanno inserite tutte nell'albero, sicuramente per minimizzare il costo bisognerà cercare di minimizzare il numero di livelli dell'albero. Volendo ci si può convincere di questo fatto anche ricorrendo ad un attimino di matematica e considerando il logaritmo (in una qualsivoglia base maggiore di $1$) di $p_i \cdot l_i$ (la quantità all'interno della sommatoria) anziché il prodotto senza logaritmo nella versione originale. Mi spiego meglio: si vede dunque esplicitando meglio la sommatoria ed eseguendo due calcoli sopra come per minimizzare il costo totale dell'albero si possa agire solo ed unicamente sul numero di livelli. Ora quindi il nostro problema si "sposta" nel cercare di determinare, dato un insieme di chiavi, un albero binario di ricerca che lo rappresenti con un numero di livelli quanto più piccolo possibile. E' dunque evidente che vogliamo avere un albero che sia sicuramente bilanciato. Una buona domanda arrivati a questo punto è chiedersi come ci dovremmo comportare nel caso in cuiabbiamo trovato due alberi con lo stesso numero di livelli. La risposta più semplice sembrerebbe essere che semplicemente scegliamo quello avente costo minora ma non ne sono sicuro nel senso che forse prima ci possono essere anche degli altri accorgimenti prima di arrivare a questa scelta.
Che te ne pare finora
) nella programmazione dinamica bisogna analizzare attentamente l'individuazione dei sottoproblemi da risolvere. Se si considera il nostro scopo, ossia avere un albero di costo minimo, si nota come la formula per calcolare il costo dello stesso dipenda da due parametri essenzialmente: i pesi ed il numero di livelli. Ora, poiché i pesi sono quelli assegnati alle varie chiavi e non possiamo di certo pensare di cambiarli e considerando che le chiavi vanno inserite tutte nell'albero, sicuramente per minimizzare il costo bisognerà cercare di minimizzare il numero di livelli dell'albero. Volendo ci si può convincere di questo fatto anche ricorrendo ad un attimino di matematica e considerando il logaritmo (in una qualsivoglia base maggiore di $1$) di $p_i \cdot l_i$ (la quantità all'interno della sommatoria) anziché il prodotto senza logaritmo nella versione originale. Mi spiego meglio: si vede dunque esplicitando meglio la sommatoria ed eseguendo due calcoli sopra come per minimizzare il costo totale dell'albero si possa agire solo ed unicamente sul numero di livelli. Ora quindi il nostro problema si "sposta" nel cercare di determinare, dato un insieme di chiavi, un albero binario di ricerca che lo rappresenti con un numero di livelli quanto più piccolo possibile. E' dunque evidente che vogliamo avere un albero che sia sicuramente bilanciato. Una buona domanda arrivati a questo punto è chiedersi come ci dovremmo comportare nel caso in cuiabbiamo trovato due alberi con lo stesso numero di livelli. La risposta più semplice sembrerebbe essere che semplicemente scegliamo quello avente costo minora ma non ne sono sicuro nel senso che forse prima ci possono essere anche degli altri accorgimenti prima di arrivare a questa scelta.Che te ne pare finora
Mi pare che lo sai fare e mi vuoi portare a ragionarci ma ho molti meno strumenti di te 
Per esempio io sono stato fermo un po' (ai tempi ricordo) sul discorso di avere un totale di nodi pari o dispari... (NON RIDERE!!)
Se ti dico pure cosa avevo pensato (E RIDI SICURO POI...)
Tipo di aggiungere nodi fittizi tipo nodi foglia oppure creare una matrice tridimensionale
Sì poi ho capito che stavo andando fuori da ogni logica. "Forse è più semplice" mi ripetevo.... Ma è rimasto lì senza soluzione senza 
La sottostruttura ottima forse l'ho capita è banale mi pare.
Non banale è la scelta che deve auto-imporsi la ricorrenza e, come dici tu, il bilanciamento per avere meno livelli possibile.
Sì ma io sono lontano (sempre di strumenti parlo) dal poter trovare una formula che mi dia la certezza che funzioni.
(immagina col codice come sono messo...
)
Sull'ultima considerazione tua non ho nulla da dire: mi sembra corretto, confronto gli alberi ABR e prendo il totale minore perché la struttura dell'albero dovrebbe essere creata, come dici tu, bilanciata e coi livelli tali da assicurarci un "totale minimo"
Per esempio io sono stato fermo un po' (ai tempi ricordo) sul discorso di avere un totale di nodi pari o dispari...
(NON RIDERE!!)Se ti dico pure cosa avevo pensato (E RIDI SICURO POI...)
Tipo di aggiungere nodi fittizi tipo nodi foglia oppure creare una matrice tridimensionale
Sì poi ho capito che stavo andando fuori da ogni logica. "Forse è più semplice" mi ripetevo.... Ma è rimasto lì senza soluzione senza La sottostruttura ottima forse l'ho capita è banale mi pare.
Non banale è la scelta che deve auto-imporsi la ricorrenza e, come dici tu, il bilanciamento per avere meno livelli possibile.
Sì ma io sono lontano (sempre di strumenti parlo) dal poter trovare una formula che mi dia la certezza che funzioni.(immagina col codice come sono messo...
)Sull'ultima considerazione tua non ho nulla da dire: mi sembra corretto, confronto gli alberi ABR e prendo il totale minore perché la struttura dell'albero dovrebbe essere creata, come dici tu, bilanciata e coi livelli tali da assicurarci un "totale minimo"
No, assolutamente, non l'ho mai svolto questo esercizio posto così: finora ti ho semplicemente riassunto i ragionamenti che ho svolto passo passo, avrei bisogno di ragionarci ancora anche io (assieme a te) prima di abbozzare una soluzione più dettagliata.
In ogni caso mi è sovvenuto in questo momento un altro ragionamento che, a mio parere, è molto importante. Per avere un albero bilanciato posso pensare di procedere come segue:
[list=1]
[*:325sa9n0]Innanzitutto ordino le $n$ chiavi in senso crescente rispetto ai loro valori;[/*:m:325sa9n0]
[*:325sa9n0]Ora devo effettuare una piccola distinzione relativamente al fatto di avere un numero di chiavi pari o dispari:
[list=1]
[*:325sa9n0]Se il numero delle chiavi è dispari allora considero l'elemento in posizione mediana, ossia ${n + 1} / 2$ e lo pongo come radice del mio albero. Richiamerò poi ricorsivamente la mia procedura per costruire degli alberi bilanciati una volta con la porzione di array a sinistra del mio elemento mediano ed un'altra con la porzione a destra. I sottoalberi risultanti da queste due chiamate li attaccherò rispettivamente il primo a sinistra ed il secondo a destra del mio elemento mediano;[/*:m:325sa9n0]
[*:325sa9n0]Se il numero delle chiavi è pari allora considero la porzione di array che va dal secondo all'ultimo elemento dello stesso (tale nuova porzione avrà un numero di chiavi dispari). Richiamo così la procedura per costruire l'albero bilanciato su tale nuova porzione di array ed all'albero risultante ci aggiungo il primo elemento dell'array iniziale che avevo originariamente scartato. Tale elemento che vado ad inserire pensandoci bene sarà il più piccolo di tale albero appena prodotto ed inoltre sono sicuro che tale operazione di inserimento non andrà ad aumentarmi il numero di livelli (ergo possiamo dire che di certo "non peggioriamo la situazione").[/*:m:325sa9n0][/list:o:325sa9n0][/*:m:325sa9n0][/list:o:325sa9n0]
Il caso base credo a questo punto che ce lo abbiamo quando siamo in presenza di un elemento soltanto nel nostro array. Resta poi da capire che algoritmo di ordinamento utilizzare. Non so perché ma al momento mi è venuto in mente il quicksort con questa idea dell'elemento mediano. Potrei sbagliarmi ma bisogna comunque rifletterci bene a mio parere.
Cosa ti sembra nel complesso, può funzionare Mi rendo conto che così a parole non è sempre facile descrivere i passi risolutivi, spero di aver fatto del mio meglio finora...
In ogni caso mi è sovvenuto in questo momento un altro ragionamento che, a mio parere, è molto importante. Per avere un albero bilanciato posso pensare di procedere come segue:
[list=1]
[*:325sa9n0]Innanzitutto ordino le $n$ chiavi in senso crescente rispetto ai loro valori;[/*:m:325sa9n0]
[*:325sa9n0]Ora devo effettuare una piccola distinzione relativamente al fatto di avere un numero di chiavi pari o dispari:
[list=1]
[*:325sa9n0]Se il numero delle chiavi è dispari allora considero l'elemento in posizione mediana, ossia ${n + 1} / 2$ e lo pongo come radice del mio albero. Richiamerò poi ricorsivamente la mia procedura per costruire degli alberi bilanciati una volta con la porzione di array a sinistra del mio elemento mediano ed un'altra con la porzione a destra. I sottoalberi risultanti da queste due chiamate li attaccherò rispettivamente il primo a sinistra ed il secondo a destra del mio elemento mediano;[/*:m:325sa9n0]
[*:325sa9n0]Se il numero delle chiavi è pari allora considero la porzione di array che va dal secondo all'ultimo elemento dello stesso (tale nuova porzione avrà un numero di chiavi dispari). Richiamo così la procedura per costruire l'albero bilanciato su tale nuova porzione di array ed all'albero risultante ci aggiungo il primo elemento dell'array iniziale che avevo originariamente scartato. Tale elemento che vado ad inserire pensandoci bene sarà il più piccolo di tale albero appena prodotto ed inoltre sono sicuro che tale operazione di inserimento non andrà ad aumentarmi il numero di livelli (ergo possiamo dire che di certo "non peggioriamo la situazione").[/*:m:325sa9n0][/list:o:325sa9n0][/*:m:325sa9n0][/list:o:325sa9n0]
Il caso base credo a questo punto che ce lo abbiamo quando siamo in presenza di un elemento soltanto nel nostro array. Resta poi da capire che algoritmo di ordinamento utilizzare. Non so perché ma al momento mi è venuto in mente il quicksort con questa idea dell'elemento mediano. Potrei sbagliarmi ma bisogna comunque rifletterci bene a mio parere.
Cosa ti sembra nel complesso, può funzionare
Mi rendo conto che così a parole non è sempre facile descrivere i passi risolutivi, spero di aver fatto del mio meglio finora...
No a parole ti spieghi benissimo e sei esaustivo alla grande: scrivi molto bene.
Ho letto e capito tutti i tuoi ragionamenti ma rimane che non c'é un'intuizione sola perché è troppo difficile l'argomento (per quanto sia figo!!!)
Coi casi base bisogna anche andarci coi piedi di piombo se usiamo la PD... Non sai mai che esce dal cilindro poi!!!
(Il problema poi che è un bordello da implementare.... La soluzione però potrei spedirla o chiedere ad un ricevimento! Per poi postarla qui che possa essere da esempio ai futuri utenti =)
Ho letto e capito tutti i tuoi ragionamenti ma rimane che non c'é un'intuizione sola perché è troppo difficile l'argomento (per quanto sia figo!!!)
Coi casi base bisogna anche andarci coi piedi di piombo se usiamo la PD... Non sai mai che esce dal cilindro poi!!!
(Il problema poi che è un bordello da implementare.... La soluzione però potrei spedirla o chiedere ad un ricevimento! Per poi postarla qui che possa essere da esempio ai futuri utenti =)
Sì, esatto...Sicuramente spesso possono esserci più intuizioni su come districare il bandolo della matassa e bisogna appunto provare a determinare quella più semplice. Se hai notato io stesso all'inizio ero partito dal discorso delle permutazioni e poi me ne sono progressivamente allontanato. Questo perché con lo studio e l'esperienza si impara che da queste è meglio stare lontani quando possibile poiché portano ad aumenti della complessità impressionanti (hai mai sentito parlare del problema del commesso viaggiatore ad esempio ).
Riguardo ai casi base effettivamente vi sono situazioni in cui non è affatto semplice determinare a priori per quali configurazioni particolari si può fornire una risposta secca e diretta senza scomposizione in sottoproblemi più semplici. Anche qui ci vogliono molta esperienza ed intuito. Ritengo tuttavia che nel problema in questione siamo anche piuttosto fortunati da questo punto di vista.
Ti dirò, secondo me non dovrebbe diventare qualcosa di estremo da implementare alla luce di queste considerazioni. Le chiamate ricorsive, seppur talvolta pensanti a livello computazionale e non sempre di ausilio alla leggibilità del programma, risparmiano moltissime righe di codice. In Prolog ad esempio quando si utilizza il modulo della programmazione a vincoli il più è sempre trovare una rappresentazione ideale del proprio problema. Una volta che questa funziona scrivere i vincoli è pressoché immediato e tutto il resto del codice da scrivere (poco) è puro contorno per "fare le cose fatte bene ed in maniera più elegante".
).Riguardo ai casi base effettivamente vi sono situazioni in cui non è affatto semplice determinare a priori per quali configurazioni particolari si può fornire una risposta secca e diretta senza scomposizione in sottoproblemi più semplici. Anche qui ci vogliono molta esperienza ed intuito. Ritengo tuttavia che nel problema in questione siamo anche piuttosto fortunati da questo punto di vista.
Ti dirò, secondo me non dovrebbe diventare qualcosa di estremo da implementare alla luce di queste considerazioni. Le chiamate ricorsive, seppur talvolta pensanti a livello computazionale e non sempre di ausilio alla leggibilità del programma, risparmiano moltissime righe di codice. In Prolog ad esempio quando si utilizza il modulo della programmazione a vincoli il più è sempre trovare una rappresentazione ideale del proprio problema. Una volta che questa funziona scrivere i vincoli è pressoché immediato e tutto il resto del codice da scrivere (poco) è puro contorno per "fare le cose fatte bene ed in maniera più elegante".
Commesso viaggiatore si l'ho visto tempo fa 
Non conosco Prolog
Ma dici che potrebbe esserci qualche paradigma da poter applicare? Qualche teorema noto?
La scelta poi come la vedi tu?
Io pensavo anche a: scelgo destra o sinistra (e viceversa) o scelgo un albero (o sottoalbero) rispetto ad un altro? Sembra stupida la domanda ma me la sto facendo adesso pure!!! Sarà che ho bisogno di dormire
Non conosco Prolog
Ma dici che potrebbe esserci qualche paradigma da poter applicare? Qualche teorema noto?
La scelta poi come la vedi tu?
Io pensavo anche a: scelgo destra o sinistra (e viceversa) o scelgo un albero (o sottoalbero) rispetto ad un altro? Sembra stupida la domanda ma me la sto facendo adesso pure!!! Sarà che ho bisogno di dormire
In realtà con questo approccio abbiamo già capito come procedere di fatto (prima l'ordinamento, poi il controllo se il numero di chiavi è pari/dispari, ecc) e di fatto ci evitiamo anche di analizzare molte delle possibili soluzioni che sappiamo già essere da scartare (ad esempio soluzioni rappresentanti alberi binari non di ricerca). Noi lavoriamo solo sul vettore e l'albero lo creiamo unicamente alla fine.
La PD è bella anche per questo: quando capisci l'idea giusta poi il resto viene da sé. Poi se ci sono teoremi utili che ci possono venire incontro bene sfruttarlo ma in tal caso (almeno io) non ne vedo.
PS: considerando inoltre che è un esercizio da esame che è stato dato è anche ragionevole che il problema non sia più complesso di quello che, finora, abbiamo capito.
La PD è bella anche per questo: quando capisci l'idea giusta poi il resto viene da sé. Poi se ci sono teoremi utili che ci possono venire incontro bene sfruttarlo ma in tal caso (almeno io) non ne vedo.
PS: considerando inoltre che è un esercizio da esame che è stato dato è anche ragionevole che il problema non sia più complesso di quello che, finora, abbiamo capito.
Sì mi sono spiegato malissimo difatti. Come dici tu possiamo ordinare quick o merge basta che sia efficente (nlog n) va benissimo. Ma la struttura la creiamo come abbiamo fatto in topic passati? Oppure ci mettiamo ad usare i red black?
Basta prendere il mediano (se è dispari) e poi va da se. Se è pari poi ok slittiamo di uno e entrà di forza come elemento più a sinistra vistro che sarà il minore... No tutto mi e' chiaro! Ma se mi metto a scrivere la ricorrenza disegno fumetti manga io...
Sarà che ho un sonno boia ma dico: si potrebbe pensare di ordinare per peso? Ossia il peso più grande lo mettiamo più in alto in modo che sia più velocemente "reperibile"? Fare una sorta di heap? Nelle scelte in fase di definizione. Poi come ci si regola con la "tabella"/"matrice"/"vettore" da creare per memorizzare i passi?
Se vuoi mandami a quel paese!
Basta prendere il mediano (se è dispari) e poi va da se. Se è pari poi ok slittiamo di uno e entrà di forza come elemento più a sinistra vistro che sarà il minore... No tutto mi e' chiaro! Ma se mi metto a scrivere la ricorrenza disegno fumetti manga io...
Sarà che ho un sonno boia ma dico: si potrebbe pensare di ordinare per peso? Ossia il peso più grande lo mettiamo più in alto in modo che sia più velocemente "reperibile"? Fare una sorta di heap? Nelle scelte in fase di definizione. Poi come ci si regola con la "tabella"/"matrice"/"vettore" da creare per memorizzare i passi?
Se vuoi mandami a quel paese!
Basta un ABR (Albero Binario di Ricerca) normalissimo in realtà alla fine. La "magia" sta nel fatto che con tutte le ipotesi che stiamo sfruttando (in parte date dal problema come ad esempio il fatto che non ci sono chiavi con lo stesso valore) ed i criteri di suddivisione in sottoproblemi adottati (scelta dell'elemento mediano nel caso di dimensione dell'array dispari, ecc) non dobbiamo far altro che comporre i vari sottoalberi del nostro albero risultante passo dopo passo. Sappiamo come determinare la chiave nel caso di array con dimensione dispari ed invece nel caso di dimensione pari che l'elemento inizialmente "scartato" (il minimo) andrà inserito nel sottoalbero che mi ha generato la chiamata ricorsiva, tutto qua. Pertanto può andare bene la struttura creata in topic passati secondo me, al massimo serviranno in più gli attributi di livello e peso (il livello andrà alla fine calcolato nodo per nodo ma non credo sia un problema).
Ci aggiorniamo domani Io vado a nanna.
PS: bello quando i thread diventano discussioni tra due utenti e basta, mi piace .
Ci aggiorniamo domani
Io vado a nanna.PS: bello quando i thread diventano discussioni tra due utenti e basta, mi piace
.
Tra le caXXate sparate ieri, giusto per cercare di pensare alternativo, chiedo:
un albero MaxHeap essendo un albero binario potrebbe servirci?
Abbiamo i pesi con frequenza alta messi in nodi che stanno in alto quindi il rispettivo livello (che è nel prodotto) verrà moltiplicato per un numero basso. Ad esempio il peso più alto sarebbe la radice che si moltiplica per uno.
Le chiavi non stanno nel prodotto e verrebbero associate ai pesi qualunque che vogliamo di volta in volta.
$k_1$ radice sta col peso maggiore dell'array quindi ultimo a destra $n$
$k_2$ primo figlio finistro elemento $n-1$
...etc... foglie con i primi elementi dell'array....
[size=85]Però forse esco proprio dal testo del problema che ho riletto per l'ennesima volta proprio right now....
[/size]
un albero MaxHeap essendo un albero binario potrebbe servirci?
Abbiamo i pesi con frequenza alta messi in nodi che stanno in alto quindi il rispettivo livello (che è nel prodotto) verrà moltiplicato per un numero basso. Ad esempio il peso più alto sarebbe la radice che si moltiplica per uno.
Le chiavi non stanno nel prodotto e verrebbero associate ai pesi qualunque che vogliamo di volta in volta.
$k_1$ radice sta col peso maggiore dell'array quindi ultimo a destra $n$
$k_2$ primo figlio finistro elemento $n-1$
...etc... foglie con i primi elementi dell'array....
[size=85]Però forse esco proprio dal testo del problema che ho riletto per l'ennesima volta proprio right now....
[/size]
Ciao Giova411
Poiché in un maxheap l'elemento avente chiave massima è posto come radice potremmo ragionare con questa struttura soltanto se le chiavi fossero proprio i pesi dell'albero. Tuttavia le chiavi, tutte diverse tra loro, devono essere poste nell'albero affinché lo stesso sia di ricerca. Lavorare solo secondo i pesi non avrebbe senso poiché le soluzioni ottenute sarebbero "spurie" (delle soluzioni con costo minimo che però non rappresentano alberi binari di ricerca purtroppo non ce ne facciamo nulla). Vi potrebbero essere alcuni (e rari, aggiungo io) casi isolati dove organizzando l'albero come maxheap rispetto ai pesi lo stesso risulta essere anche di ricerca in relazione ai valori delle chiavi ma...come puoi intuire sono pure coincidenze ed il ragionamento applicato è ben lontano dall'essere generale.
Piuttosto proverei a farmi un'idea su quanto può essere complessa a livello temporale e spaziale la soluzione da me proposta.
Poiché in un maxheap l'elemento avente chiave massima è posto come radice potremmo ragionare con questa struttura soltanto se le chiavi fossero proprio i pesi dell'albero. Tuttavia le chiavi, tutte diverse tra loro, devono essere poste nell'albero affinché lo stesso sia di ricerca. Lavorare solo secondo i pesi non avrebbe senso poiché le soluzioni ottenute sarebbero "spurie" (delle soluzioni con costo minimo che però non rappresentano alberi binari di ricerca purtroppo non ce ne facciamo nulla). Vi potrebbero essere alcuni (e rari, aggiungo io) casi isolati dove organizzando l'albero come maxheap rispetto ai pesi lo stesso risulta essere anche di ricerca in relazione ai valori delle chiavi ma...come puoi intuire sono pure coincidenze ed il ragionamento applicato è ben lontano dall'essere generale.
Piuttosto proverei a farmi un'idea su quanto può essere complessa a livello temporale e spaziale la soluzione da me proposta.
Sì chiaro... Dovrei cancellare i post dopo che scrivo impulsivamente... 
Per la complessità ci sono, anche lì, difficoltà nel capirla al volo.
Ordiniamo: quindi non meno di $nlogn$ per quanto riguarda l'array.
Costruire l'albero: con un'elemento mediano (radice) poi sottoalbero sinistro e destro (quindi avremo dimensioni simili sx e dx che differiscono al più di uno) può essere anche non meno di $nlogn$, perché dobbiamo trovare il posto giusto dove inserire. Partendo dalla radice ed avendo elementi distinti, fare l'ABR, non è difficilissimo. Ma arrivare alla complessità temporale totale, al momento, non ci riesco.
Quella spaziale dipende dalla tabella che usiamo per memorizzare i valori dati dalla PD. Ci basta un vettore?
Per la complessità ci sono, anche lì, difficoltà nel capirla al volo.
Ordiniamo: quindi non meno di $nlogn$ per quanto riguarda l'array.
Costruire l'albero: con un'elemento mediano (radice) poi sottoalbero sinistro e destro (quindi avremo dimensioni simili sx e dx che differiscono al più di uno) può essere anche non meno di $nlogn$, perché dobbiamo trovare il posto giusto dove inserire. Partendo dalla radice ed avendo elementi distinti, fare l'ABR, non è difficilissimo. Ma arrivare alla complessità temporale totale, al momento, non ci riesco.
Quella spaziale dipende dalla tabella che usiamo per memorizzare i valori dati dalla PD. Ci basta un vettore?
Più che altro si sommano i costi delle varie complessità per costruire ciascun sottoalbero. E' pur vedo comunque che siccome sappiamo che la radice del nostro albero di volta in volta è l'elemento mediano che selezioniamo nel caso di vettore di dimensione dispari le nostre operazioni non sono altro che "attaccare" i due sottoalberi all'albero la cui radice è appena stata determinata. Il numero di "attaccamenti" che faccio è $O(h)$ (due, sottoalbero sinistro e destro, per ogni livello), dove $h$ è l'altezza dell'albero risultante (che non è altro che il numero di livelli che ci sono nell'albero stesso). Più precisamente ne farò $\Theta(h)$ (so già a priori quanto vado avanti ad "attaccare" senza dover distinguere in caso migliore e peggiore).
Per la complessità spaziale, sì: abbiamo una serie di chiamate ricorsive per cui è necessario memorizzare dei valori (vedremo quali) nello stack. Nota: qui (con le chiamate ricorsive) a dire il vero non ci interessa come memorizzare tali valori ma semplicemente sapere quanto occupano (qui i valori infatti sono memorizzati nello stack, che di fatto è una pila ergo un vettore con operazioni di push/pop, tra l'altro mi sembra sia gestito come LIFO, Last In First Out). In più abbiamo il nostro vettore iniziale in cui sono memorizzati i valori delle chiavi.
Per la complessità spaziale, sì: abbiamo una serie di chiamate ricorsive per cui è necessario memorizzare dei valori (vedremo quali) nello stack. Nota: qui (con le chiamate ricorsive) a dire il vero non ci interessa come memorizzare tali valori ma semplicemente sapere quanto occupano (qui i valori infatti sono memorizzati nello stack, che di fatto è una pila ergo un vettore con operazioni di push/pop, tra l'altro mi sembra sia gestito come LIFO, Last In First Out). In più abbiamo il nostro vettore iniziale in cui sono memorizzati i valori delle chiavi.
Only ma se si fanno ricerche a vuoto si arriva e si supera le foglie? Cioé le ricerche eventuali che non trovano nulla possiamo pensarle come i figli NIL delle foglie? Come tu immagini le cose mentalmente? 
La complesità totale sarà intorno a $O(n^3)$ che è sempre meglio di un $O(2^n)$ come hai ben lasciato intendere all'inizio abbandonando il discorso sul trovare tutte le permutazioni possibili.
Ora, non vorrei dire, ma è uguale al problema della Parentesizzazione!
Hai mai studiato la moltiplicazione a catena di matrici?
Bene, io si e non c'ho capito una mazza!!!! Ma per la costruzione dell'albero sono convinto di proporti una struttura di un ABR Ottimo e di calcolare una matrice 
Se $l_1$ abbiamo dritto per dritto $p_1$
La buttaggiamo giù la formula?
La complesità totale sarà intorno a $O(n^3)$ che è sempre meglio di un $O(2^n)$ come hai ben lasciato intendere all'inizio abbandonando il discorso sul trovare tutte le permutazioni possibili.
Ora, non vorrei dire, ma è uguale al problema della Parentesizzazione!
Hai mai studiato la moltiplicazione a catena di matrici?
Bene, io si e non c'ho capito una mazza!!!! Ma per la costruzione dell'albero sono convinto di proporti una struttura di un ABR Ottimo e di calcolare una matrice
Se $l_1$ abbiamo dritto per dritto $p_1$
La buttaggiamo giù la formula?
"Giova411":
Only ma se si fanno ricerche a vuoto si arriva e si supera le foglie? Cioé le ricerche eventuali che non trovano nulla possiamo pensarle come i figli NIL delle foglie? Come tu immagini le cose mentalmente?
[...]
Il colmo è proprio questo: allo stato attuale con tale approccio da me adottato escludo la possibilità di ricerche a vuoto se vedi come è strutturato l'algoritmo
Mi sto appunto ancora scontrando con questo fatto perché fatico a capire come davanti ad un problema che "attacchiamo" con la programmazione dinamica possa arrivare a tale situazione. Quasi quasi mi viene da pensare che ci sia qualche falla nel mio ragionamento eppure non riesco a trovarla (per ora)."Giova411":
[...]
La complesità totale sarà intorno a $O(n^3)$ che è sempre meglio di un $O(2^n)$ come hai ben lasciato intendere all'inizio abbandonando il discorso sul trovare tutte le permutazioni possibili.
Ora, non vorrei dire, ma è uguale al problema della Parentesizzazione!
[...]
What's that
"Giova411":
[...]
Hai mai studiato la moltiplicazione a catena di matrici?
Bene, io si e non c'ho capito una mazza!!!! Ma per la costruzione dell'albero sono convinto di proporti una struttura di un ABR Ottimo e di calcolare una matrice
Allora proponi pure, sarò lieto di leggere la tua proposta
.
http://www.columbia.edu/~cs2035/courses ... -chain.pdf
A pagina 11 forse c'é una formula simile a quella che vogliamo!
A pagina 11 forse c'é una formula simile a quella che vogliamo!
Confermo, pare proprio che sia coinvolta la moltiplicazione a catena di matrici nella soluzione linkata...
"onlyReferee":
Confermo, pare proprio che sia coinvolta la moltiplicazione a catena di matrici nella soluzione linkata...
Grazie come sempre!!!!
(ma perché l'orso?)
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo