aiuto: algoritmo per la garanzia del 5
Luca
con il quale scegliere in una serie di combinazioni quelle che mi
garantiscono il 5 (o il 4 o il 3), avendo per base n numeri?
Walter Sabatini
> nello sviluppare le combinazioni per il suoperenalotto qual'è l'algoritmo
> con il quale scegliere in una serie di combinazioni quelle che mi
> garantiscono il 5 (o il 4 o il 3), avendo per base n numeri?
>
Non ho capito.
Serve un riduttore?
Nel quel caso, gli algoritmi che cercano il numero minimo di combinazioni da
giocare è di tipo NP-hard (cioè quasi sicuramente esponenenziale).
Questo significa che per n anche piccoli, la cosa è sufficientemente
intrattabile.
So che esistono comunque programmi che utilizzano propri algoritmi, che non
arrivano alla soluzione ottima ma comunque si avvicinano.
Prima di tutto si può calcolare il quantitativo minimo teorico
(difficilmente raggiungibile), questo serve per non farsi delle illusioni.
Il ragionamento è semplice... vedere il numero di combinazioni che "copro"
giocandone una. Poi divido il totale delle combinazioni possibili per tale
numero ed ho il numero minimo di combinazioni da giocare.
Facciamo l'esempio usando n=90, cioè riportandosi al caso del superenalotto
utilizzando tutti i 90 numeri, considerando che la combinazione è una
sestina e volendo "coprire" fino al 4.
Le combinazioni totali sono c(90,6)=90!/((90-6)!*6!) = 622614630 (com'è
noto).
Allora calcolo quante combinazioni per una sestina giocata copro.
Sestine in cui ho fatto 6: = 1
Sestine in cui ho fatto 5: c(6,5)*c(84,1) = 504
Sestine in cui ho fatto 4: c(6,4)*c(84,2) = 52290
Totale = 52795
Giocate teoriche minime 622614630/52795=11794 (arrotondato per eccesso).
Per sapere come calcola per un n qualsiasi... fare i calcoli precedenti
usando questa forma generale.
Sestine in cui ho fatto x: c(6,x)*c((n-6),(6-x))
Il 6 indica appunto che giochiamo sestine...se fosse qualcos'altro (esempio
ottine per totogol...) usare il numero di pronostici da giocare per ogni
combinazione.
Spero di non essere stato troppo confusionario, nel qual caso sono pronto a
cercare di chiarire i punti più oscuri... se invece erano cose già sapute..
meglio così l'ho ripassate anch'io :Þ.
Facciamo considerazioni sul numero minimo.
Allora giocando 11794 combinazioni (ammesso che abbia trovato proprio il
numero minimo teorico) faccio sicuramente 4 (ed ho un 4% di possibilità di
fare 5). Ma quant'è il rapporto tra costo e guadagno? Se non vado errato il
costo per combinazione è £800 (0,41 Euro) quindi pago £9435200..,paga così
tanto il quattro?
Quindi bisognerebbe giocare non su 90 numeri ma su un'insieme più piccolo di
numeri.
A parte considerazioni personali sull'inutilità di tali giocate (comuque
resta un gioco iniquo e non si può scegliere un insieme di numeri che
"sicuramente" esce..a meno di truffe varie)..un algoritmo per ricercare tale
insieme minimo di giocate deriva dal ragionamento precedente.
Eccolo:
1) Creiamo una lista con tutte le combinazioni possibili di n numeri.
2) Ordiniamo la lista, in modo decrescente, per numero di combinazioni
"coperte" da ciasuna giocata.
3) Scegliamo la combinazione in testa alla lista.
4) Aggiorniamo tutte le combinazioni rimanenenti eliminando dal loro insieme
di "copertura" le colonne coperte dalla sestina scelta al punto 3.
5) Se sono rimaste colonne da coprire, ricominciamo dal punto 2.
Il motivo di perché questa tecnica non arriva sicuramente alla soluzione
migliore, è dato dall'aleatorietà di scegliere la "prima" combinazione della
lista. Infatti spesso si può sceglierne una fra un insieme di combinazioni,
ed ogni scelta fatta non è del tutto equivalente alle altre.
P.S.
Se non ti servivano i riduttori... beh ho scritto invano!!!
Walter
Marco Fabiani
Walter Sabatini ha scritto nel messaggio
<7ki95g$gdp$1...@aquila.tiscalinet.it>...
>Nel quel caso, gli algoritmi che cercano il numero minimo di combinazioni
da
E' dimostato?
Esiste un "benchmark" per valutare la bonta' di euristiche in questo campo
(set covering)?
Grazie, Marco
Walter Sabatini
Non ho trovato documentazione che semplifichi il problema utilizzando le sue
simmetrie...tanto da rendere la ricerca polinomiale...
Oppure la dimostrazione si riferiveva al fatto che Np-Hard = esponenziale?
In tal senso ad oggi non si è dimostratato il contrario... e questo induce a
pensare che lo sia (visto che ci sono una miriade di problemi Np-hard ed è
sufficiente dimostrare la polinomialità per uno solo di questi).
Scusa la mia ignoranza... ma che intendi per "benchmark"?
Walter
Marco Fabiani <fabi...@tin.it> wrote in message
Marco Fabiani
Walter Sabatini ha scritto nel messaggio
>Appunto si riporta ad un problema di Set-covering che è un problema
NP-Hard.
>
>Non ho trovato documentazione che semplifichi il problema utilizzando le
sue
>simmetrie...tanto da rendere la ricerca polinomiale...
Era quello che volevo dire, ci sono alcune simmetrie che (spero!) potrebbero
essere di aiuto.
Sono anni che ci perdo tempo ma finora nulla...
(cmq nel caso generale le simmetrie si perdono, quindi credo che nel caso
generale si tratti proprio di un NP-tosto)
>Scusa la mia ignoranza... ma che intendi per "benchmark"?
Prove per valutare l' "efficacia" di algoritmi per soluzioni approssimate.
Ossia una specie di "albo dei record" per alcuni problemi significativi.
Approfitto per una considerazione: riquoto l'algoritmo che avevi esposto
prima:
>1) Creiamo una lista con tutte le combinazioni possibili di n numeri.
>2) Ordiniamo la lista, in modo decrescente, per numero di combinazioni
>"coperte" da ciasuna giocata.
>3) Scegliamo la combinazione in testa alla lista.
>4) Aggiorniamo tutte le combinazioni rimanenenti eliminando dal loro
insieme
>di "copertura" le colonne coperte dalla sestina scelta al punto 3.
>5) Se sono rimaste colonne da coprire, ricominciamo dal punto 2.
>Il motivo di perché questa tecnica non arriva sicuramente alla soluzione
>migliore, è dato dall'aleatorietà di scegliere la "prima" combinazione
della
>lista. Infatti spesso si può sceglierne una fra un insieme di combinazioni,
>ed ogni scelta fatta non è del tutto equivalente alle altre.
Fai notare che occorrerebbe utilizzare il backtracking perche' spesso si
puo' scegliere fra combinazioni equivalenti (che coprono lo stesso numero di
colonne) ad ogni passo.
Mi sa che nemmeno questo algoritmo arriva all'ottimo. Esempio: (totocalcio,
senza ottimizzazione)
1111
111X
11X1
1X11
211X
21X1
2X11
Al primo passo ho una sola possibilita': la colonna 1111 che ne copre 4 (3
piu' se stessa).
Rimangono da coprire:
211X
21X1
2X11
Da ora in poi ogni colonna ne copre una sola (211X e' coperta, oltre che da
se stessa anche da 111X, che pero' non copre se stessa in quanto gia'
coperta).
Ossia devo prenderle tutte e 3. Totale 4 colonne.
Ma le colonne 111X, 11X1, 1X11 sono un riduttore del sistema (che non
possono mai venire fuori da quell'algoritmo, perche' comunque al primo passo
prendo 1111) composto da 3 colonne (che in questo caso e' l'ottimo).
Conclusione: il backtracking dovrebbe essere totale (la lista che sia
ordinata o meno a questo punto non ha, dal punto di vista teorico,
importanza).
Qualche idea?
Marco
PS: ho notato che, qualsiasi algoritmo si utilizzi, il grosso problema sta
proprio nella scelta delle "prime" colonne del ridotto. Se si parte da un
buon inizio si raggiunge facilmente l'ottimo o quasi (con altri metodi), ma
se si "sbaglia" una colonna che sembrava buona non se ne esce piu'....
Walter Sabatini
problemi...infatti non è detto che arrivi all'ottimo però è polinomiale e
questo permette di poter accontentarci dei suoi risultati (se sono
soddisfacenti).
Sottolineo il fatto che se parto da uno sviluppo totale, le simmetrie mi
permettono di iniziare da una qualsiasi colonna.
Esempio:
1111
111x
11x1
11xx
1x11
1x1x
1xx1
1xxx
x111
x11x
x1x1
x1xx
xx11
xx1x
xxx1
xxxx
16/5=3,2= 4 colonne
Seguendo l'algoritmo una possibile soluzione è:
1111
1xxx
x1xx
xx11
Per i casi generali, ho trovato una tabella che indica la stima (statistica)
della complessità dell'algoritmo del simplesso, in base al numero di
variabili.
n<100 O(3n)
100<n<10000 O(n^2)
n>10000 O(n^4)
In generale O(2^n)
Nel caso del set covering, n è il numero delle combinazioni che si hanno
giocando x numeri.
Riduzione n-1 per:
Superenalotto
90 numeri 622614630
40 numeri 3838380
20 numeri 38760
10 numeri 210
Totocalcio
13 doppie 8192
13 triple 1594323
P.S.
Nel caso del totocalcio ho anche il valore dei risultati migliori
(aggiornato al 94).
Certo non c'è solo l'algoritmo del simplesso (che garantisce l'ottimo)
soprattutto perché è un problema con molte simmetrie...
Qualcuno sa indirizzarci verso fonti di informazioni migliori?
(Mi sono da poco scontrato con l'algoritmo di Karmarkar ma ancora devo farci
la mano...)
Walter
Massimo Mondò
> (Mi sono da poco scontrato con l'algoritmo di Karmarkar ma ancora devo farci
> la mano...)
> Walter
Di cosa si tratta ? Sono curioso di saperlo.
Stasera metto in area alcune cosiderazioni mie sui riduttori.
Ciao,
Massimo
Marco Fabiani
Walter Sabatini ha scritto nel messaggio
>Giusto, e questo conferma che l'algoritmo non è adatto a questo tipo di
>problemi...infatti non è detto che arrivi all'ottimo però è polinomiale e
>questo permette di poter accontentarci dei suoi risultati (se sono
>soddisfacenti).
E' polinomiale se non fai il backtracking (in gergo questo approccio viene
definito "metodo tradizionale"), ma per avere l'ottimo ci vuole il backtrack
totale, non parziale. Almeno nel caso generale non ho trovato nulla di
meglio .. sigh!
>Sottolineo il fatto che se parto da uno sviluppo totale, le simmetrie mi
>permettono di iniziare da una qualsiasi colonna.
Esatto. (solo per gli integrali)
Quindi al primo passo e' indifferente la scelta della colonna. La simmetria
pero' si perde subito dopo quindi il metodo tradizionale non fornisce
risultati ottimi... qua ci vuole qualche idea fulminante.. :)
>Per i casi generali, ho trovato una tabella che indica la stima
(statistica)
>della complessità dell'algoritmo del simplesso, in base al numero di
>variabili.
>
>n<100 O(3n)
>100<n<10000 O(n^2)
>n>10000 O(n^4)
>
>In generale O(2^n)
Bella! come hai fatto ad ottenere questi dati? Stime "sul campo" o dal punto
di vista teorico?
Comunque da solo anche il simplesso (che tra l'altro ha una soluzione
polinomiale) non basta. Bisogna ricorrere alla PLC, cioe' tagli di Gomory e
quant'altro, e ritorniamo nell'NP-tostissimo.
Marco
Walter Sabatini
punto
> di vista teorico?
Dal punto di vista Internet :)) l'ho trovata su un sito, il quale comparava
la tecnica del Simplesso con quella di Karmarkar...
>
> Comunque da solo anche il simplesso (che tra l'altro ha una soluzione
> polinomiale) non basta. Bisogna ricorrere alla PLC, cioe' tagli di Gomory
e
> quant'altro, e ritorniamo nell'NP-tostissimo.
Se non sbaglio invece il Simplesso mi permette di arrivare ad una soluzione
ottima, il problema è che non è stato dimostrato che sia a complessità
polinomiale...altrimenti gli NP-hard non sarebbere NP.
Nel nostro caso specifico si usa il simplesso per problemi di programmazione
lineare intera...cioè, ad esempio, con il metodo del rilassamento e del
Branch-Bound.
Ora qui le informazioni mi mancano ma sono convinto che la dimostrazione
dalla raggiungibilità di una soluzione ottima vale, appunto, anche per
questo tipo di problemi.
La mia conoscenza si ferma qui...uso Lp-solve per risolvere alcuni problemi
con il simplesso, e sto vedendo, appunto, cos'è karmarkar.
P.S.
La domanda sorge spontanea, ma vale la pena questa fatica per il
Superenalotto? Io sono pienamente convinto di no!!!
Per il totocalcio ed il totogol è diverso!!!
Anche se spesso si utilizza molto del proprio tempo solo per arrivare ad
un'obiettivo..anche se poi oltre non c'è nulla :))
In fin dei conti "la vita è un tempo per fare qualcosa"...
Walter
Marco Fabiani
Walter Sabatini ha scritto nel messaggio
>> Comunque da solo anche il simplesso (che tra l'altro ha una soluzione
>> polinomiale) non basta. Bisogna ricorrere alla PLC, cioe' tagli di Gomory
>e
>> quant'altro, e ritorniamo nell'NP-tostissimo.
>
>Se non sbaglio invece il Simplesso mi permette di arrivare ad una soluzione
>ottima, il problema è che non è stato dimostrato che sia a complessità
>polinomiale...altrimenti gli NP-hard non sarebbere NP.
Come fai ad arrivare all'ottimo??
Cioe', all'ottimo ci arrivi, ma se non imponi la condizione che le variabili
siano binarie (o intere, dipende da come modelli) ti da' una soluzione
(ottima) dove ti dice di giocare mezza colonna 1111, un quarto della colonna
111X, 17/215 della colonna X111 e cosi' via..
Per il simplesso ho commesso una imprecisione: non e' il simplesso che ha
una soluzione polinomiale, ma la PL. Non chiedermi quale e' perche' non la
conosco, so che fa uso di "proiezioni interne", ossia non gironzola sugli
spigoli del politipo ma ci passa in mezzo, o qualcosa del genere. Che poi
non venga utilizzata perche', sebbene polinomiale, alla fine costa di piu'
del simplesso e' un altro conto. :)
>Nel nostro caso specifico si usa il simplesso per problemi di
programmazione
>lineare intera...cioè, ad esempio, con il metodo del rilassamento e del
>Branch-Bound.
E si riva' nell'NP-indecente.
Ad esempio il B&B e' palesemente esponenziale.
I vari metodi con i piani di taglio pure (e a ogni passo devi pure applicare
il simplesso... fai un po' i conti..:))
>P.S.
>La domanda sorge spontanea, ma vale la pena questa fatica per il
>Superenalotto? Io sono pienamente convinto di no!!!
>Per il totocalcio ed il totogol è diverso!!!
>Anche se spesso si utilizza molto del proprio tempo solo per arrivare ad
>un'obiettivo..anche se poi oltre non c'è nulla :))
Ah, se e' per questo ti do' perfettamente ragione. Pensa, sono pure
primatista AOSI di alcuni sistemi per Totogol ma, in tutta sincerita',
nonmenepuo'fregaredimeno dei sistemi...
E' solo che come problema e' intrigante e (sopratutto) si applica a tante
altre cose...
Marco 1X2
Massimo Mondò
> Ah, se e' per questo ti do' perfettamente ragione. Pensa, sono pure
> primatista AOSI di alcuni sistemi per Totogol ma, in tutta sincerita',
> non me ne puo' fregare di meno dei sistemi...
AOSI ? Questa si che mi e' nota come sigla. :-) Quali primati ?
Mi fai sapere, mi interessa.
Ok ragazzi, vi ho seguito fin dove potevo, ma poi credo di essermi perso
un pochino...
Io ho provato con algoritmi esaustivi che facevano grosso modo cosi :
1) Elencare uno sviluppo integrale
2) Prendere la prima combinazione utile e inseriscila nel Riduttore
3) Tenere solo le combinazioni che si diffirenziano per almeno 3 numeri
4) Finche' possibile tornare al punto 2.
5) Fine
I risultati sono abbastanza scadenti e cmq confermano che non esistono
Riduttori a massimo rendimento (o anche a massima rappresentitivita')
al SEL oppure al Totogol.
Anzi solo in un caso ho avuto modo di ottenere un riduttore ottimale ma
penso serva a ben poco ( se non a dimostrare l'eccezione che conferma la
regola...).
Si tratta del sistema di 6 numeri presi a 3 a 3 con un integrale di 20
combinazioni ed un risuttore ottimale di 2 sole combinazioni :
1,2,3,4,5,6 Integrale di C(6,3) = 20 comb.
Rapporto di riduzione max = 10 (dato dalle comb. rappresentate da una
qualsiasi combinazione a meno di un numero).
Riduttore = 2 combinazioni
1° comb. ) 1,2,3
2° comb. ) 4,5,6
Infatti le due combinazioni precedenti coprono ad n-1 tutte le 20 dello
sviluppo integrale.
In tanti altri casi ho lottato a lungo con il mio fido PC ma invano. :-(
Uno su tutti volevo farvi riflettere sul caso al Totogol del sistema di 12
numeri
nello sviluppo classico in ottine :
Comb. = C(12,8) = 495 comb.
Rapporto di riduzione max = 33 (valore come indicato precedentemente)
Riduttore ottimale = 495 / 33 = 15 comb.
Valore mai raggiunto e credo mai raggiungibile........
Lo stesso algoritmo usato al totocalcio ed al totosei invece
trova riduttori in pochi secondi, ma ormai di riduttori per questi giochi
ce ne sono da oltre 40 anni e credo che il nome di Roberto di Nasso forse
vi ricorda qualcosa ...?
Saluti,
Massimo
Marco Fabiani
Massimo Mondò ha scritto nel messaggio <376EB0AB...@mclink.it>...
>AOSI ? Questa si che mi e' nota come sigla. :-) Quali primati ?
>Mi fai sapere, mi interessa.
Qualche tempo fa ne avevo di piu', ora me li hanno tolti quasi tutti (anche
perche' ho smesso di perderci tempo). Mi sembra mi sia rimasto qualcosa sui
sistemi piccoli, a 4 o 5 fisse. Se leggi le tabelle quando le pubblicano
ogni tanto mi trovi.
>
>Ok ragazzi, vi ho seguito fin dove potevo, ma poi credo di essermi perso
>un pochino...
>Io ho provato con algoritmi esaustivi che facevano grosso modo cosi :
>
>1) Elencare uno sviluppo integrale
>2) Prendere la prima combinazione utile e inseriscila nel Riduttore
>3) Tenere solo le combinazioni che si diffirenziano per almeno 3 numeri
>4) Finche' possibile tornare al punto 2.
>5) Fine
Non e' esaustivo, e nemmeno fornisce un ridotto. Questo e' un riduttore di
quelli che si dicono MR (che molti prg usano come primo passo della
riduzione).
>Uno su tutti volevo farvi riflettere sul caso al Totogol del sistema di 12
>numeri
>nello sviluppo classico in ottine :
>
>Comb. = C(12,8) = 495 comb.
>Rapporto di riduzione max = 33 (valore come indicato precedentemente)
>Riduttore ottimale = 495 / 33 = 15 comb.
>Valore mai raggiunto e credo mai raggiungibile........
Infatti. Per alcuni sistemi (piccoli) mi sono preso la briga di fare il B&B
completo. Ad esempio il 10 partite N-1 al totogol, teorico 45/17 = 2.64
cioe' 3 NON E' raggiungibile, e il miglior risultato e' 5 (quasi il doppio
del limite inferiore!)
Il 12 partite credo non si possa scendere sotto 26 (trovato in contemporanea
da me e Baldi, ma registrato da quest'ultimo perche' piu' veloce..:))
In realta' i rapporti tra valore minimo attuale e limite inferiore sono
sempre molto elevati
Ad esempio:
10 partite: 1.89
11 partite: 1.51
12 partite: 1.73
13 partite: 1.59
14 partite: 1.59
15 partite: 1.65
16 partite: 1.47
Al contrario del Totocalcio dove invece sono piu' bassi (in alcuni casi pari
a 1).
Questo perche', vedendolo come set-covering, al Totocalcio cerco di coprire
una superficie con tasselli (quasi) regolari, mentre al totogol uso tasselli
molto frastagliati e inevitabilmente ci sono numerose sovrapposizioni che
rendono difficile il calcolo.
>Lo stesso algoritmo usato al totocalcio ed al totosei invece
>trova riduttori in pochi secondi, ma ormai di riduttori per questi giochi
>ce ne sono da oltre 40 anni e credo che il nome di Roberto di Nasso forse
>vi ricorda qualcosa ...?
Tieni conto che ultimamente molti sistemi sono stati ritoccati in meglio
anche al Totocalcio, campo dove si pensava non si potesse dire piu' nulla.
Sopratutto i sistemi a vincite multiple (ogni colonna coperta almeno n>=2
volte).
Ma non ti dico chi ha fatto il programma...eheheh!
Mi sa che stiamo andando leggermente OT... dove ce ne andiamo a continuare??
Marco
A. Caranti
> nello sviluppare le combinazioni per il suoperenalotto qual'è l'algoritmo
> con il quale scegliere in una serie di combinazioni quelle che mi
> garantiscono il 5 (o il 4 o il 3), avendo per base n numeri?
C'e' una certa letteratura su questo problema del "lotto" da parte di
combinatorici e/o studiosi di geometrie finite. Il mio (limitato, quanto
la mia conoscenza) interesse in proposito e' nato da una conferenza nel
novembre scorso di un matematico ungherese, che mostrava come usare
alcune strutture combinatorie (tipo piani proiettivi) per garantirsi
l'ambo giocando cinquine, raggiungendo un risultato molto vicino a
quello di una certa stima teorica.
Adesso c'e' una ragazza qui a Trento che ci sta facendo una tesi. Lo
scopo e' piu' che altro studiare block designs e cose del genere, ma per
esempio ha trovato il modo di usare un certo sistema di Steiner per
coprire decentemente tutti i "3" giocando dei "6". Se qualcuno e'
interessato gli posso far avere una copia della tesi, quando e' finita.
Andreas
Marco Fabiani
A. Caranti ha scritto nel messaggio <3773875F...@science.unitn.it>...
>...
>Adesso c'e' una ragazza qui a Trento che ci sta facendo una tesi. Lo
>scopo e' piu' che altro studiare block designs e cose del genere, ma per
>esempio ha trovato il modo di usare un certo sistema di Steiner per
>coprire decentemente tutti i "3" giocando dei "6". Se qualcuno e'
>interessato gli posso far avere una copia della tesi, quando e' finita.
Inutile dire che te ne sarei immensamente grato :)
Marco
Renato
Marco Fabiani ha scritto nel messaggio <7l025o$29r$1...@nslave1.tin.it>...
>
>A. Caranti ha scritto nel messaggio <3773875F...@science.unitn.it>...
>>...
>>Adesso c'e' una ragazza qui a Trento che ci sta facendo una tesi. Lo
>>scopo e' piu' che altro studiare block designs e cose del genere, ma per
>>esempio ha trovato il modo di usare un certo sistema di Steiner per
>>coprire decentemente tutti i "3" giocando dei "6". Se qualcuno e'
>>interessato gli posso far avere una copia della tesi, quando e' finita.
>
ciao mi chiamo Renato e sono nuovo in questo nsg.
Mi piacerebbe avere una copia della tesi, se è possibile mi faresti un gran
favore.
Se puoi spediscimelo all'indirizzo r.es...@tiscalinet.it
Ti ringrazio
Alla prossima Renato
Mauro Fiorentini
Renato wrote:
> >>Adesso c'e' una ragazza qui a Trento che ci sta facendo una tesi. Lo
> >>scopo e' piu' che altro studiare block designs e cose del genere, ma per
> >>esempio ha trovato il modo di usare un certo sistema di Steiner per
> >>coprire decentemente tutti i "3" giocando dei "6". Se qualcuno e'
> >>interessato gli posso far avere una copia della tesi, quando e' finita.
La cosa interessa anche me. Non e' difficile coprire tutti i 3, ma i problemi
sono due:
trovare una copertura minimale (il minor numero di 6) e dimostrarla minimale.
Mi interessa soprattutto quest'ultimo punto.
Se possibile, una copia a mfior...@etnoteam.it e' gradita.
Grazie
Mauro Fiorentini