O forse intendi questo ordine???BlaisorBlade ha scritto:Beh, Mind, sei sicuro che quello non vada in tempo ottimo?
Ma quell'algoritmo, che esplorerà tutte le possibili combinazioni, ovvero tutti i sottoinsiemi di tartarughe, non sarà di ordine O(2^n)? O forse no... forse sei stato eccessivamente sintetico ma hai già detto quello giusto.
[...]
Inaugurazione con tartarughe...
- gip
- Messaggi: 86
- Iscritto il: 01 gen 1970, 01:00
- Località: Pisa, Scuola Superiore Sant'Anna
- Contatta:
- gip
- Messaggi: 86
- Iscritto il: 01 gen 1970, 01:00
- Località: Pisa, Scuola Superiore Sant'Anna
- Contatta:
Fermo restando il fatto che rimango dubbioso su come lo si possa dimostrare "rigorosamente", io vedrei necessario memorizzare un vettore di lunghezze massime e uno dei pesi raggiunti fino a quel momento, con un elemento per tartaruga; dopodiche' si ripete n volte, ed al piu' su n elementi, una procedura che (qualora la sequenza di tartarughe selezionata non si sia gia' interrotta precendentemente, il che' e' verificabile cofrontando la lunghezza raggiunta con il numero di iterazioni gia' effettuate) controlla se la capacita' della tartaruga successiva (che ha indice k-i, se k e' l'indice della sequenza in questione e i e' il numero di iterazioni gia' effettuate) e' maggiore del peso raggiunto e che in base al risultato del confronto aggiorna i vettori. Alla fine l'elemento con lunghezza massima vince. Non va?MindFlyer ha scritto:Un'altra cosa: bisognerebbe anche dimostrare che l'algoritmo di BlaisorBlade funziona, che è un fatto non ovvio (e del quale non sono nemmeno convinto)...
Bisognerebbe dimostrare che, aggiungendo una nuova tartaruga "dal basso", la sequenza massimale che parte con questa tartaruga si ottiene a partire dalle sequenze massimali finora trovate per le altre tartarughe.
Allora BlaisorBlade, come lo dimostri?
- gip
- Messaggi: 86
- Iscritto il: 01 gen 1970, 01:00
- Località: Pisa, Scuola Superiore Sant'Anna
- Contatta:
Per induzione (due volte)?MindFlyer ha scritto:L'algoritmo è chiaro.
Come dimostri che funziona??
Con una tartaruga funziona, poiché non c'è niente da verificare; se poi funziona con n tartarughe, immagino di aggiungerne una sopra tutte le altre, nella sequenza data come input; a questo punto ho che per ogni ciclo l'andamento dei vettori per le tartarughe che stanno sotto di essa va esattamente come se non ci fosse; gli elementi che la riguardano si evolvono invece in base ad un algoritmo più semplice, volto a trovare la più lunga sottosequenza con una certa tartaruga in testa.
**
Un simile algoritmo si può a sua volta dimostrare per induzione: con una tartaruga funziona banalmente; se poi funziona con n tartarughe si ha che aggiungendone una sotto tutte le altre, l'algoritmo si comporta come se avesse n tartarughe per le prime n-1 iterazioni e all'ultima (qualora non si sia interrotto prima) non fa altro che verificare se la nuova tartaruga può sostenere il peso e aggiorna così peso e lunghezza, come è corretto che faccia.
**
A questo punto, avendo per ogni tartaruga un numero che ci dice quanto è lunga la sottosequenza massima che la vede sopra le altre, si vede quale tra queste sottosequenze è la maggiore, ottenendo il risultato finale, visto che tale sottosequenza deve essere una delle suddette, poichè dovrà avere una qualche tartaruga in testa.
The end.
Può funzionare??
Ciao!
Marino
Sarò breve: se sono riuscito a capire quello che avete detto, voi memorizzate ad ogni passo soltanto la lunghezza della sequenza più lunga che ha per base ciascuna tartaruga, ed il relativo peso. Poi aggiungete una nuova tartaruga sotto tutte le altre (non sopra, come mi sembra di capire dal discorso di gip), e vedete se può estendere le pile trovate precedentemente. E ok.
Ma la mia domanda è: se voi non considerate tutte le sequenze che si possono formare a partire da una pila non massima nell'iterazione precedente, come garantite di trovare ugualmente il massimo? Insomma, voi usate un algoritmo "greedy", supponendo che dei passaggi localmente ottimi ottimizzino anche il risultato finale. Ma non mi pare ovvio che funzioni, in questo caso.
Ma la mia domanda è: se voi non considerate tutte le sequenze che si possono formare a partire da una pila non massima nell'iterazione precedente, come garantite di trovare ugualmente il massimo? Insomma, voi usate un algoritmo "greedy", supponendo che dei passaggi localmente ottimi ottimizzino anche il risultato finale. Ma non mi pare ovvio che funzioni, in questo caso.
un algoritmo greedy, per essere applicato, richiede (come diceva Mind Flyer) la dimostrazione che la scelta dell'ottimo locale ad ogni iterazione garantisca il raggiungimento della soluzione ottima globale (come ad esempio si può fare per costruire l'albero di copertura minimo di un grafo). credo che questo problema vada risolto mediante programmazione dinamica... purtroppo non sono ferrato nell'argomento, ma seguirò le discussioni con curiosità
Anzitutto non fate caso al mio nick ridicolo, quando mi stavo registrando non sapevo proprio cosa inventarmi
Spero di cavarvi di impaccio da dimostrazioni inutili se vi dico che si tratta di un problema di zaino a due dimensioni e che ogni approccio greedy non puo' funzionare...
Va utilizzata una programmazione dinamica in due dimensioni circolare, ma visto che il problema non ha dimensioni eccessive (l'ho trovato su "Programming Challenges") e' possibile due array separati. Non capite quello che dico? Non vi preoccupate, sono dettagli implentativi che interessano agli informatici
Comunque, bisogna ciclare attraverso tutte le tartarughe dall'ultima alla prima tenendo aggiornato un array pesomin[l] che indica il peso minimo che deve avere una sequenza di l tartarughe. Una volta finito di ciclare le tartarughe, trovare il massimo l tale che esista pesomin[l] (gia' perche' puo' anche non esistere).
Mi fermo qui, vi do' solo degli indizi... Se volete vi posto il codice ma vi avverto che non e' molto comprensibile... di certo non perche' scrivo male codice ma perche' certi passaggi e' difficile capirli solo dal programma, specie se non commentato.
Ciao
P.S.: visto che ci sto vi propongo un problemino informatico/matematico: dato un numero 1<=n<=10^9, determinare la cifra piu' significativa di n^n.
Spero di cavarvi di impaccio da dimostrazioni inutili se vi dico che si tratta di un problema di zaino a due dimensioni e che ogni approccio greedy non puo' funzionare...
Va utilizzata una programmazione dinamica in due dimensioni circolare, ma visto che il problema non ha dimensioni eccessive (l'ho trovato su "Programming Challenges") e' possibile due array separati. Non capite quello che dico? Non vi preoccupate, sono dettagli implentativi che interessano agli informatici
Comunque, bisogna ciclare attraverso tutte le tartarughe dall'ultima alla prima tenendo aggiornato un array pesomin[l] che indica il peso minimo che deve avere una sequenza di l tartarughe. Una volta finito di ciclare le tartarughe, trovare il massimo l tale che esista pesomin[l] (gia' perche' puo' anche non esistere).
Mi fermo qui, vi do' solo degli indizi... Se volete vi posto il codice ma vi avverto che non e' molto comprensibile... di certo non perche' scrivo male codice ma perche' certi passaggi e' difficile capirli solo dal programma, specie se non commentato.
Ciao
P.S.: visto che ci sto vi propongo un problemino informatico/matematico: dato un numero 1<=n<=10^9, determinare la cifra piu' significativa di n^n.
Ho dimenticato di dire che se avete qualche problema di informatica, se volete, c'e' il forum delle Olimpiadi di Informatica. E' appena nato e non c'e' molto traffico, ma crescera'
http://81.208.32.83:8889/ioi-site/pn/ht ... file=index
Ciao e scusate l'intromissione, il forum matematica non e' posto che mi spetterebbe[/url]
http://81.208.32.83:8889/ioi-site/pn/ht ... file=index
Ciao e scusate l'intromissione, il forum matematica non e' posto che mi spetterebbe[/url]
Ciau Pyv, e benvenuto nel forum!Pyv ha scritto:P.S.: visto che ci sto vi propongo un problemino informatico/matematico: dato un numero 1<=n<=10^9, determinare la cifra piu' significativa di n^n.
Dovrei chiederti di aprire un nuovo topic se vuoi proporre un nuovo problema (è per tenere ordinato il forum).
A presto!
- gip
- Messaggi: 86
- Iscritto il: 01 gen 1970, 01:00
- Località: Pisa, Scuola Superiore Sant'Anna
- Contatta:
Io veramente intendevo memorizzare, per ciascuna tartaruga, la lunghezza della sequenza più lunga che ha sopra tutte le altre quella determinata tartaruga, aggiungendo le successive poi una alla volta dal basso; quando non ce la si può più fare, perchè la nuova tartaruga di base non regge il peso della pila, allora la pila precedente era la più lunga, con quella determinata tartaruga posta alla sommità... siccome poi la pila massima dovrà avere alla sommità una delle tartarughe, e io per ogni tartaruga ho calcolato la pila massima con essa in cima, il massimo lo trovo tra quelli calcolati...MindFlyer ha scritto:Sarò breve: se sono riuscito a capire quello che avete detto, voi memorizzate ad ogni passo soltanto la lunghezza della sequenza più lunga che ha per base ciascuna tartaruga, ed il relativo peso. Poi aggiungete una nuova tartaruga sotto tutte le altre (non sopra, come mi sembra di capire dal discorso di gip), e vedete se può estendere le pile trovate precedentemente. E ok.
Ma la mia domanda è: se voi non considerate tutte le sequenze che si possono formare a partire da una pila non massima nell'iterazione precedente, come garantite di trovare ugualmente il massimo? Insomma, voi usate un algoritmo "greedy", supponendo che dei passaggi localmente ottimi ottimizzino anche il risultato finale. Ma non mi pare ovvio che funzioni, in questo caso.
Io non vedo il bug nel ragionamento, ma ci sta benissimo che mi sbagli... sono però curioso di sapere cosa in particolare fa acqua...
P.S.: un dubbio atroce pervade ora la mia mente: non è che si intendesse sequenze nell'ordine dato, ma formate anche da tartarughe non adiacenti nella configurazione di partenza??????? Se sì ritiro tutto quanto, poiché avevo inteso il contrario...
Oooooh, esatto!!!gip ha scritto:P.S.: un dubbio atroce pervade ora la mia mente: non è che si intendesse sequenze nell'ordine dato, ma formate anche da tartarughe non adiacenti nella configurazione di partenza??????? Se sì ritiro tutto quanto, poiché avevo inteso il contrario...
Altrimenti il problema sarebbe banalmente O(n), senza programmazione dinamica e altre diavolerie.
- gip
- Messaggi: 86
- Iscritto il: 01 gen 1970, 01:00
- Località: Pisa, Scuola Superiore Sant'Anna
- Contatta:
Amen. Ma qual è il modo banale per avere O(n)?MindFlyer ha scritto:Oooooh, esatto!!!gip ha scritto:P.S.: un dubbio atroce pervade ora la mia mente: non è che si intendesse sequenze nell'ordine dato, ma formate anche da tartarughe non adiacenti nella configurazione di partenza??????? Se sì ritiro tutto quanto, poiché avevo inteso il contrario...
Altrimenti il problema sarebbe banalmente O(n), senza programmazione dinamica e altre diavolerie.