Precedente :: Successivo |
Autore |
Messaggio |
ulisse Dio maturo
Registrato: 02/03/05 01:09 Messaggi: 1531 Residenza: Bagnone (MS)
|
Inviato: 21 Gen 2007 19:37 Oggetto: |
|
|
Taifu ha scritto: | Essendomi stufato di aspettare, ho interrotto il programma ancora fermo ad esplorare l'albero delle 27 mosse e ho ripensato completamente l'algoritmo passando da una versione a forza "brutta" ad una realmente a forza bruta.
Adesso, con un leggerissimo fattore di miglioramento, in 87 centesimi di secondo ho trovato una soluzione in 16 mosse.
Mi sono dato per metà dell'asino per non averci pensato prima e per metà mi sono beato del programmino...
Per gli uomini di buona volontà questa è la nuova versione:
P.S. Il codice non è commentato ma sono assolutamente disponibile a spiegarlo riga per riga a chi me lo chiedesse. |
Ti prendo in parola e chiedo spiegazioni.
Prima, però, sottopongo a conferma quello che penso di aver capito.
Entrambi gli algoritmi partono da un nodo (una configurazione delle taniche) e provano a fare tutti i travasi possibili tra i 12 formalmente eseguibili, verificano se il nodo al quale ognuno di essi conduce è già presente nell'albero (segno inequivocabile che l'algoritmo è già passato da quel nodo in precedenza) e, in caso non lo sia lo aggiungono all'albero.
Questo sino a che il nodo raggiunto non coincide con quello finale richiesto dal problema.
Il primo algoritmo però è ricorsivo-condizionale: la ricorsione viene eseguita solo se il nuovo nodo raggiunto non è ancora censito nell'albero; viceversa la ricorsione si chiude.
La condizione di uscita dalla ricorsione è data o dal raggiungimento della soluzione o dal raggiungimento della massima profondità dell'albero (prevista a priori fuori dal programma).
Quando l'algoritmo esce da una ricorsione, risale l'albero a ritroso (ogni uscita dalla ricorsione è un passo indietro) fino a che non ritorna ad un nodo che non ha finito di esplorare.
Ciò vuol dire, sostanzialmente, che l'algoritmo gironzola sistematicamente per tutto l'albero fino a che non trova una soluzione.
Il secondo algoritmo, invece, è composto da due parti.
La prima è iterativa (ciclo while) e scrive sistematicamente l'albero a partire dal nodo iniziale indicato dal problema.
L'uscita dal ciclo while avviene solo quando l'ultimo ciclo eseguito non è stato in grado di aggiungere nuovi nodi all'albero.
Poi l'algoritmo,o dopo aver scritto tutto l'albero, controlla se la soluzione è presente tra i nodi individuati.
In più rispetto al primo algoritmo, il secondo tiene anche traccia, per ogni nodo, del numero di passi necessari al suo raggiungimento.
Fermo restando che abbia analizzato correttamente ed esaustivamente gli algoritmi, non riesco a capire cosa determini l'efficienza del secondo. |
|
Top |
|
|
Taifu Semidio
Registrato: 24/10/06 10:13 Messaggi: 203
|
Inviato: 21 Gen 2007 23:01 Oggetto: |
|
|
ulisse ha scritto: | Ti prendo in parola e chiedo spiegazioni.
Prima, però, sottopongo a conferma quello che penso di aver capito.
...
Fermo restando che abbia analizzato correttamente ed esaustivamente gli algoritmi, non riesco a capire cosa determini l'efficienza del secondo. |
Innanzitutto hai capito e interpretato perfettamente entrambi gli algoritmi.
Ti faccio i miei più sinceri complimenti!
Detto ciò, siccome io capisco di più così, provo a spiegarmi con un esempio.
Immaginiamo un grafo di possibilità siffatto:
Codice: |
B---E--F
/ \ /
A D--G
\ /
C
|
Dove A è il punto di partenza, B, C, D ed E sono nodi intermedi, F e G sono delle possibili configurazioni finali.
Vediamo come esplorano l'albero i due algoritmi:
Codice: |
Primo algoritmo:
ABEF 3
ABEDG 4
ABEDC 4
ABDEF 4
ABDG 3
ABDC 3
ACDBEF 5
ACDEF 4
ACDG 3
Secondo algoritmo:
AB 1
AC 1
BE 2
BD 2
EF 3
DG 3
|
Il primo percorre gli stessi segmenti più volte per il solo fatto che vi giunge attraverso cammini diversi sprecando così un sacco di tempo inutilmente. Il segmento EF varrà sempre 1 sia che arrivo da AB sia che arrivo da ACD: inutile calcolarlo due volte.
Il secondo invece si allarga a "macchia d'olio" individuando subito i cammini più rapidi verso ogni nodo. In questo modo, in maniera molto più rapida, esploro subito ogni possibile punto del grafo e posso permettermi di non dare nessuna profondità massima. Inoltre posso rispondere a domande come "quante sono le configurazioni raggiungibili?", "quanto è distante la più lontana" etc. etc.
E` chiaro che, per un grafo così poco profondo (o per un problema di tre taniche) i tempi dei due algoritmi sono comunque accettabili (pochi secondi contro pochi centesimi). Con un grafo molto più profondo (o per un problema di quattro o più taniche) allora le cose cambiano.
Visti i tempi, con la seconda versione posso permettermi di scoprire dei problemi tosti. Magari provare a individuare il problema a tre taniche minori di 10 litri con la profondità maggiore...
Spero (ma non credo) di essermi spiegato meglio. Se così non fosse ti prego di dirmelo perchè ci tengo a ricambiare, almeno in parte, il tempo che hai dedicato ai due algoritmi.
Ciao.
Marco. |
|
Top |
|
|
Taifu Semidio
Registrato: 24/10/06 10:13 Messaggi: 203
|
Inviato: 22 Gen 2007 01:58 Oggetto: |
|
|
Detto, fatto!
Questo è il più "lungo" con taniche di massimo 8 litri:
Partenza (4,4) - (5,0) - (8,4)
Arrivo (4,0) - (5,2) - (8,6)
Vi interessa sapere qual'è il più lungo in assoluto con taniche più capienti?
Ciao.
Marco. |
|
Top |
|
|
Taifu Semidio
Registrato: 24/10/06 10:13 Messaggi: 203
|
Inviato: 22 Gen 2007 08:37 Oggetto: |
|
|
Per risolvere questo servono un bel po' di mosse:
Da (9,0) - (13,4) - (14,14)
A (9,9) - (13,2) - (14,7).
Ciao.
Marco. |
|
Top |
|
|
ulisse Dio maturo
Registrato: 02/03/05 01:09 Messaggi: 1531 Residenza: Bagnone (MS)
|
Inviato: 22 Gen 2007 10:13 Oggetto: |
|
|
Taifu ha scritto: | Innanzitutto hai capito e interpretato perfettamente entrambi gli algoritmi.
Ti faccio i miei più sinceri complimenti!
|
Non era difficile: sono scritti bene!
L'unica difficoltà è nelle istruzioni specifiche di Python e nella comprensione delle variabili per le quali, deduco, Python non impone la dichiarazione.
Ma con un po' di immaginazione ci si arriva.
Ciò che non doveva sfuggirmi, invece, era l'interpretazione!
Ora è chiaro.
Pensando ai cuccioli che giorno per giorno esplorano il territorio circostante la tana.
Il primo algoritmo li farebbe partire radialmente: corro corro corro...
Il secondo, invece, li farebbe muovere a spirale con raggi sempre più grandi: giro giro giro...
Per la cronaca, i cuccioli usano il secondo algoritmo!
Ottima strategia! Ora che ho capito posso confermare che la seconda strategia è decisamente più efficiente!
Mi chiedo se sono possibili ottimizzazioni.
Ci rifletterò un pochetto. Se mi riesce provo a imbastire un programmino anch'io (lavorerò in VBA, però, che conosco già. Anche se ho visto che Python non è per nulla difficile).
Grazie per le spiegazioni chiare e illuminanti.
Hai mai pensato di darti all'insegnamento? (lo dico seriamente)
Chiudo con qualche domandina specifica di Python
Ma le variabili non si dichiarano?
A cosa serve il metodo (si chiama così, vero?) __EQ__ ?
Lo inserisci per completezza o è indispensabile dichiararlo?
Un'ultima cosa. Secondo me c'è uno sfrido nel codice: la prima istruzione del ciclo while ( aggiunto = False ) |
|
Top |
|
|
Taifu Semidio
Registrato: 24/10/06 10:13 Messaggi: 203
|
Inviato: 22 Gen 2007 11:33 Oggetto: |
|
|
ulisse ha scritto: | Grazie per le spiegazioni chiare e illuminanti.
|
Prego, prego. Dovere
ulisse ha scritto: | Hai mai pensato di darti all'insegnamento? (lo dico seriamente) |
Urka! Detto da te questo è davvero un bel complimento! Grazie!
In realtà per due settimane molti anni fa ho insegnato matematica al mio vecchio liceo e ricordo ancora lo stress dei momenti prima di entrare in classe. Ricordi a parte ho già 42 anni e oramai la mia strada lavorativa è già tracciata almeno per un po' di anni. Per ora il mio sforzo "insegnativo" è dedicato ai miei due figli. Poi si vedrà
ulisse ha scritto: | Chiudo con qualche domandina specifica di Python
Ma le variabili non si dichiarano? |
No. Però se usi una variabile senza averla dichiarata otterrai un'eccezione. Python è un linguaggio a forte tipizzazione dinamica. E` assolutamente eccezionale in questo.
Ti consiglio di dedicare un'oretta al tutorial di Python: io ci sono cascato così anni fa e da allora lo uso e diffondo a più non posso (il dominio www.python.it fu registrato da me tempo fa e il sito è ospitato gratuitamente nella azienda in cui lavoro). Tieni conto che ho usato nella mia vita lavorativa almeno una quindicina di linguaggi (e ne ho studiati altri quattro o cinque) per cui se ti dico che per me è di gran lunga il miglior linguaggio di programmazione esistente, lo dico a ragion veduta (ripeto: parere personale ovviamente).
Il tutoral in inglese: http://www.python.org/doc/tut/
Il tutoral in italiano: http://www.python.it/doc/Python-Docs/html/tut/tut.html
ulisse ha scritto: | A cosa serve il metodo (si chiama così, vero?) __EQ__ ?
Lo inserisci per completezza o è indispensabile dichiararlo? |
Due istanze di una classe normalmente non sono confrontabili perchè vengono, giustamente, ritenute diverse dal linguaggio in quanto oggetti distinti. Definendo il metodo __eq__ posso dire a Python cosa deve fare per considerare uguali due oggetti. Per esempio con il codice seguente stabilisco che due taniche sono uguali se hanno stessa capacità e stessa quantità di acqua:
Codice: |
def __eq__(self, tanica):
return self.capacita == tanica.capacita and self.litri == tanica.litri
|
Se non lo definisco nel seguente codice l'ultimo test ritornerebbe False:
Codice: |
a = Tanica(5, 3)
b = Tanica(5, 3)
a == b
|
ulisse ha scritto: | Un'ultima cosa. Secondo me c'è uno sfrido nel codice: la prima istruzione del ciclo while ( aggiunto = False ) |
Bellissima la definizione di sfrido: mi piace!
Sì, è chiaramente uno sfrido. Solo in un secondo momento mi sono accorto di poter usare last e nextLast come condizione di uscita ma mi sono dimenticato di togliere l'assegnamento della variabile "aggiunto".
Hai mai pensato di dedicarti alla programmazione?
Ciao.
Marco. |
|
Top |
|
|
ulisse Dio maturo
Registrato: 02/03/05 01:09 Messaggi: 1531 Residenza: Bagnone (MS)
|
Inviato: 22 Gen 2007 12:45 Oggetto: |
|
|
Taifu ha scritto: | Urka! Detto da te questo è davvero un bel complimento! Grazie! |
L'ho detto perché si vede che provi piacere nel "travasare" (visto che parliamo di taniche!) le tue competenze.
Taifu ha scritto: | Python è un linguaggio a forte tipizzazione dinamica. | Ohi! Mi serve una traduzione!
Taifu ha scritto: | Ti consiglio di dedicare un'oretta al tutorial di Python: io ci sono cascato così anni fa e da allora lo uso e diffondo a più non posso (il dominio www.python.it fu registrato da me tempo fa e il sito è ospitato gratuitamente nella azienda in cui lavoro). |
Ma dai! Sto parlando al signor Python.it in persona!
Taifu ha scritto: | Due istanze di una classe normalmente non sono confrontabili perchè vengono, giustamente, ritenute diverse dal linguaggio in quanto oggetti distinti. |
Eh, si. Quando definisci un nuovo insieme di oggetti devi definire anche le operazioni che puoi eseguire con essi altrimenti il pc che ne sa?
La verità è che avevo cercato dove, nel codice, facessi uso dell'operatore == non trovandolo. Che idiota! Ho cercato l'operatore "uguale" ma non l'operatore "diverso" !!!
Taifu ha scritto: | Bellissima la definizione di sfrido: mi piace! |
Eheh. Chi pensa che sia nato con carta e matita in mano si sbaglia!
Mio padre lavorava in fabbrica e io mi divertivo a rompere le scatole ai suoi operai con tremila domande del tipo "cos'è questo?" "cos'è quello?" "come funziona?" "a cosa serve?" e quindi prima di dire "radice quadrata" ho imparato a dire "sfrido" !
Citazione: | Hai mai pensato di dedicarti alla programmazione? |
Eheheh. Che fai, ricambi le lusinghe?
Dedicarmi interamente no.
Non credo potrei mai svolgere una singola attività a tempo pieno. Mi annoierei dopo un giorno.
La programmazione è uno dei miei hobbies (come hai notato se ti sei scaricato i miei programmini postati nel forum), è anche uno dei miei lavori (sviluppo software gestionale) e una delle materie di insegnamento (tengo un piccolo corso - veramente all'acqua di rose - di algoritmi di teoria dei numeri). |
|
Top |
|
|
Taifu Semidio
Registrato: 24/10/06 10:13 Messaggi: 203
|
Inviato: 23 Gen 2007 01:16 Oggetto: |
|
|
ulisse ha scritto: | Taifu ha scritto: | Python è un linguaggio a forte tipizzazione dinamica. | Ohi! Mi serve una traduzione!
|
Tipizzazione statica: il programmatore deve dichiarare prima le variabili.
Tipizzazione dinamica: il programmatore non deve dichiarare prima le variabili.
Tipizzazione forte: (qui uso un esempio) il programmatore non può sommare tra di loro variabili di tipo diverso (per esempio una stringa ad un numero come si può fare in javascript) senza convertire esplicitamente una delle due variabili.
Tipizzazione debole: il contrario della precedente...
Python unisce il meglio: forte tipizzazione dinamica.
Inoltre previene la stragrande maggioranza degli errori in questo campo impedendoti di usare una variabile non inizializzata.
Ciao.
Marco. |
|
Top |
|
|
Taifu Semidio
Registrato: 24/10/06 10:13 Messaggi: 203
|
Inviato: 23 Gen 2007 09:14 Oggetto: |
|
|
[quote="ulisse"]Eheh. Chi pensa che sia nato con carta e matita in mano si sbaglia!
Mio padre lavorava in fabbrica e io mi divertivo a rompere le scatole ai suoi operai con tremila domande del tipo "cos'è questo?" "cos'è quello?" "come funziona?" "a cosa serve?" e quindi prima di dire "radice quadrata" ho imparato a dire "sfrido" !
[quote]
Dimenticavo, anche io conosco il significato del termine sfrido per lo stesso tuo motivo: anche mio padre ha lavorato in fabbrica. Solo che io le scatole le rompevo a lui e non ai suoi operai...
Ciao.
Marco. |
|
Top |
|
|
Taifu Semidio
Registrato: 24/10/06 10:13 Messaggi: 203
|
Inviato: 25 Gen 2007 11:15 Oggetto: |
|
|
Taifu ha scritto: | Siccome non credo che tutti leggeranno sino in fondo, aggiungo subito alcuni nuovi sotto-indovinelli per il problema delle quattro taniche:
1) quante sono le differenti configurazioni raggiungibili dalla partenza 0/8/13/0 ?
2) quanto è distante la configurazione più lontana dal punto di partenza ?
3) e quante sono?
4) e quali sono? (ne basta una)
|
Ok, visto il grande interesse, vi do le risposte
Citazione: |
1) 395
2) 17
3) 4
4) 5/1/1/14 , 1/6/0/14 , 1/1/0/19 , 0/1/1/19
|
|
|
Top |
|
|
ulisse Dio maturo
Registrato: 02/03/05 01:09 Messaggi: 1531 Residenza: Bagnone (MS)
|
Inviato: 31 Gen 2007 23:04 Oggetto: |
|
|
Taifu ha scritto: | Ok, visto il grande interesse... |
Per forza!
E chi è che si mette a cercare e contare 345 soluzioni con carta e penna???
Senza il tuo programmino (o un altro equipollente) è quasi impossibile trovarne una, figuriamoci trovarle tutte! |
|
Top |
|
|
Taifu Semidio
Registrato: 24/10/06 10:13 Messaggi: 203
|
Inviato: 31 Gen 2007 23:51 Oggetto: |
|
|
ulisse ha scritto: | Taifu ha scritto: | Ok, visto il grande interesse... |
Per forza!
E chi è che si mette a cercare e contare 345 soluzioni con carta e penna???
Senza il tuo programmino (o un altro equipollente) è quasi impossibile trovarne una, figuriamoci trovarle tutte! |
Ovvio, ovvio, era solo una battuta perchè nessuno aveva chiesto le soluzioni, non certo perché nessuno si era messo a riempire 200 fogli di carta
In realtà pensavo che giocando con il tetraedro si riuscisse a capire qual'era la configurazione più lontana e in seconda istanza speravo che qualcuno si scaricasse Python e provasse il programmino. |
|
Top |
|
|
ulisse Dio maturo
Registrato: 02/03/05 01:09 Messaggi: 1531 Residenza: Bagnone (MS)
|
Inviato: 01 Feb 2007 00:16 Oggetto: |
|
|
In effetti il tetraedro mi è rimasto sul gargarozzo.
Volevo fare qualche disegnino ma non ho trovato il tempo.
E sinceramente mi ruga perché volevo provare a verificare se è solo una velleità teorica o se effettivamente si riesce a gestire e usare concretamente.
Perché il libro, fetente, descrive il metodo del tetraedro ma poi ne fa solo un uso parziale e riporta, invece, una quantità spropositata di tabelle... |
|
Top |
|
|
|
|
Non puoi inserire nuovi argomenti Non puoi rispondere a nessun argomento Non puoi modificare i tuoi messaggi Non puoi cancellare i tuoi messaggi Non puoi votare nei sondaggi
|
|