Ricerca non euristica di lunghette vergini per minimo fissato

Hai ancora ragione, i numeri elencati sono quelli che hai indicato tu, sono 45 in totale quelli selezionabili dopo la terza scelta. Il resto del ragionamento mi pare non cambi.
Non so perché mi sia confuso così. È molto difficile mantenere la concentrazione quando selezioni le colonne, cambi il colore di sfondo delle celle, applichi i filtri e poi li togli…
Alla fine non ti ricordi neanche quello che stavi facendo.
Per questo sarebbe comodo avere un programma sul quale: a) selezioni il file delle estrazioni, b) imposti la lunghezza di ricerca (novine) e c) scegli il punteggio per il quale ne cerchi una (o più di una) vergine. Poi per il resto delle funzionalità ci sarebbe da sbizzarrirsi.

.
.
.

Ho provato a fare delle considerazioni sulla complessità di questo algoritmo.

Ho considerato i passi descritti sopra fino a completare manualmente le fasi di scelta (in questo primo passaggio, come abbiamo visto, ci si ferma a 6 numeri e non si arriva alla novina).
Ho quindi preso il nostro come caso medio, e non so se ho fatto bene, ma il range di estrazioni è certamente casuale, quindi se non è la quantità (2093) che trae in inganno, mi risulta che:
- nello scegliere il primo numero l'algoritmo ha 90 possibilità (non c'è nessun numero da escludere né in verde né in arancione);
- Per il secondo numero la scelta deve escludere il numero scelto in precedenza + i numeri in arancione (ma ancora non ce ne sono), quindi ne sceglierà uno su 89;
- Per il terzo numero può scegliere tra 90 - i due in verde già scelti - quelli in arancione coinvolti dai primi due in verde e in totale avrà 68 possibili numeri in bianco tra cui scegliere;
e così via...Come riporta questa tabellina:


Perciò la mia valutazione, (anche se la definirei davvero sommaria), mi fornisce i seguenti valori indicativi:

questo nuovo algoritmo effettuerà 90 * 89 * 68 * 45 * 18 * 6 = 2.647.144.800 (2 miliardi e 600 milioni circa) di tentativi
Che non sono certo una bazzecola, ma vista la natura del problema credo che sia assolutamente ragionevole.

Se, come termine di paragone, consideriamo gli altri algoritmi esaminati nei giorni scorsi vediamo che:
- Verificare tutte le possibili novine dell'integrale effettua C(90;9) = 706.252.528.630 (706 miliardi e 200 milioni) di tentativi
- Similmente abbiamo anche visto che seppure al massimo dell'efficienza (sia per l’hardware moderno, sia dal punto di vista del codice), verificare moltiplicando tutte le sestine vergini con tutti i terni vergini, per poi scartare quelli che non sono novine e controllando i punteggi di quelli rimanenti
costringe a effettuare (892.126 * 82.334) = 73.452.302.084 (73 miliardi e 400 milioni) di tentativi

Quindi sembrerebbe (ancora il condizionale è d'obbligo) che:
- se a questo algoritmo diamo indice di velocità pari a 1,
- allora provare tutte le C(90;9) novine: 706.252.528.630 / 2.647.144.800 = 266,7978452 più lento
- provare, invece, a moltiplicare sestine verg. per terni verg: 73.452.302.084 / 2.647.144.800 = 27,74774621 è più lento

Perciò, in termini di tempo potrebbe voler dire che se l'algoritmo della moltiplicazione ha impiegato 12 ore, questo nuovo dovrebbe terminare in circa 25 minuti

Naturalmente un calcolo preciso della complessità terrebbe conto del fatto che tra i tentativi di ogni algoritmo ci sono sotto procedure differenti. Ovvero:
Il primo genera tutte le novine e le controlla una per una fino trovare tre punti (con costo computazionale lineare pari alla lunghezza delle novine)
Il secondo genera 10 volte meno novine, ma aggiunge il controllo su ciascuna di queste sulla presenza di numeri ripetuti (con costo computazionale lineare pari alla lunghezza delle novine)
Questo nuovo effettua un numero veramente ridotto di tentativi, ma per ciascuno di essi deve verificare la presenza di concorsi che totalizzano tre punti con l'ultimo numero aggiunto (si applicano i filtri Excel a due a due col nuovo numero introdotto assieme ai precedenti)
e questo è un po' più complicato da calcolare e non dipende dalla lunghezza delle novine, ma dalla quantità dei concorsi e il costo, nel caso peggiore è pari alle possibili coppie tra 9 numeri C(9,2)=36, ma il caso medio è molto inferiore.

Infine, però, penso che anche se alla fine i due algoritmi trasformati in programma impegnassero la macchina allo stesso modo e quindi se impiegassero lo stesso tempo per terminare, è anche vero che il funzionamento interno è completamente differente. Quindi arriverebbero alla prima soluzione in tempi diversi
Per cui, se si lanciassero due istanze contemporaneamente, una basata sul un algoritmo e l'altra su questo, e se esiste una novina vergine per il tre, siccome seguono un percorso di ricerca diverso, allora uno dei due ci arriverebbe prima dell'altro e la ricerca potrebbe considerarsi conclusa.

Quindi la curiosità di vedere realizzato un software che applichi questo algoritmo non è ancora soddisfatta.

Rispondo a Silop2005 (che ringrazio per la segnalazione)


ho dato uno sguardo al programma che hai citato e a giudicare dalle impressioni che hanno gli utenti di quel forum sembrerebbe un lavoro ben fatto.
ma mi pare che la funzione di ricerca delle lunghette, nonostante il nome del software, sia solo una funzione marginale. Mi sembra orientato più alla statistica di ritardi di ambi, terni e frequenze di formazioni
che appunto al fine della ricerca descritta in questo post.
Dicevo ho provato il programma e se chiedo di cercare una novina vergine per tre punti (come stiamo facendo noi) a stima del tempo necessari è di circa 3 giorni.
Il proposito di questo algoritmo è appunto cercare di ridurre questi tempi fino a dei limiti più normali (come avrai letto, nei primi test la ricerca è stata portata a termine in meno di 2 minuti.)
Posto qui di seguito le immagini del mio collaudo del programma di terze parti e se avessi sbagliato qualcosa comunicatemelo.

(clicca sulle miniature per ingrandire)

fig.1 Carica Archivio -------------------- fig.2 Parametri di ricerca (novine per 3 pts) --------------- fig.3 Finestra dei risultati di ricerca ------------------- fig.4 Elaborazione in corso
-------------------------- ---------------------------------------------- ---------------------------------------

Questa comunque era un parentesi e anche se fa piacere confrontarsi con gli altri, dobbiamo proseguire per la nostra strada per tentare di progredire.
.

.

.

.

.

Rispondo qui anche a Sventra Papere (che ho un leggero sospetto di chi possa essereci dietro a questo nickname)


Credo la stessa utilità che ne traggono gli utenti dell'altro forum tanto entusiasti del programma citato da Silop2005.
Oppure, guardando il problema da un'altra prospettiva ci si rende conto che questo problema in fondo è equiparabile in altri problemi in cui spesso qui dentro ci si imbatte.
Puoi rigirare la minestra, ma la sostanza è sempre quella...Qui comunque tempo fa avevamo accennato alla trasformazione formale di un problema in un altro problema apparentemente distinto, ma le cui soluzioni possono essere adattate quelle dell'uno con l'altro. Se il lavoro necessario per questa sorta di "traduzione" delle soluzioni avviene in tempo accettabile (polinomiale), allora i due problemi si possono considerare "riducibili" e quindi cercare di risolvere quello che si preferisce con l’intento di fornire invece una soluzione all'altro problema equivalente:
<discussione sulla riduzione polinomiale>

.

.

.

.


Infine a Giovanni A. (a.k.a. krypta) rispondo che ci devo pensare un attimo. Però il meccanismo è identico anche se cambi i punti cercati da tre a quattro.

Cambia il fatto che, lavorando col foglio excel, se vuoi cercare le novine vergini per 4 punti, invece che applicare i filtri a coppie per vedere dove capitano i 'terzi' 1 nelle colonne bianche,


Dovrai, invece, applicare i filtri a tre a tre sulle colonne verdi (per vedere in quali colonne bianche capita il quarto 1....visto che se capitano 4 punti saltiamo oltre.
Certamente sarà leggermente più lento, ma davvero in maniera quasi ininfluente. perché questo parametro incide in maniera quasi lineare (per ogni passo invece che fare C(9,2)=36 scansioni dei 2093 concorsi ne farai C(9,3)=84 )
Ciò che incide di più sulla velocità è la lunghezza delle lunghette (se da novine chiedi decine, undicine, ecc) e poi è importante anche il range dei concorsi esaminati (noi ne abbiamo preso un campione di 2093, ma si spera di poter fare esperimenti su altri intervalli anche maggiori)



Poi vorrei anticiparti una domanda
Quando il software sarà più in ordine (e a meno che non provi pure io a fare qualcosa, per cui me lo faccio da solo) vorrei darti un file con un migliaio circa di sestine (Il file si chiama "sistema90060306=1093.txt"), perché tu possa usarlo al posto delle 2093 estrazioni.
E come parametri dovresti vedere se trovi delle lunghette, non di nove, ma di lunghezza sei (cioè sestine) che non hanno mai fatto 3 punti.
- Se le trovi sai anche dirmi quali?
- Però mi interesserebbe di più se invece non ne trovi neanche una

Ciao Krypta,
se stai incontrando difficoltà a farlo girare con 4 punti e invece con 3 funziona bene è probabile che abbia interpretato diversamente la mia descrizione e chissà, magari stai portando avanti una variante.
Perché se hai scritto il codice che funziona con 3, davvero non dovrebbe essere difficile farlo funzionare con altri punteggi. cambia solo la procedura che stabilisce quali e quante colonne deve confrontare.

Due domande riferirete al primo screenshot:
Il valore "Tests" è riferito ai test che prevede di fare oppure a quelli che ha compiuto sino a quel momento?
In 01min e 28sec ha terminato l'esecuzione di tutti i cicli e quindi si è fermato oppure sta ancora cercando?

Daccordo, puoi usare 10 computers, ma il paragone facciamolo con dei punti fermi.
Io userei 1 solo thread per fare tutte le prove. Questo mi permette di fare un confronto equilibrato.
Anche l'algoritmo che stiamo studiando qui puoi dividerlo in quanti threads ti pare. E il tempo naturalmente si dimezza ogni volta che aggiungi due threads.

Ho chiesto perché mi sa che hai preso una strada diversa.
Per esserne certo dovrei vedere le prime lunghette che prova (1,2,3,7...; 1,2,3,7,8,24. ecc...)

Come mai impiega di più a fare le settine e le ottine piuttosto che le novine, quando le novine sono di più?

m C(90,m)
7 7.471.375.560 ----> 11'08"
8 77.515.521.435 ----> 03'56"
9 706.252.528.630 ----> 01'28"

Forse stai applicando un altro algoritmo

Forse è ininfluente, ma il percorso lo immaginavo diverso.
Nel senso che se prova il 24 e determina che non va bene, facendo un passo indietro per seguire la strada alternativa, dovrebbe l'asciare l'8 e provare il successivo al 24. invece nella tua sequenza Ha tolto anche l'8, per mettere il 7 e il 15.
Guardando l'immagine si riesce a seguire meglio (però potrei aver sbagliato io..Come è già successo! Quindi, magari domattina ricontrollo ancora una volta).

Si vede che 1 2 3 7 e 8 sono in verde, il 24 lo sta per scegliere.
Ora sceglie il 24. Ma si accorgerà immediatamente che è una mossa che chiude tutte possibilità di proseguire...
Perciò deve fare un passo indietro. Allora toglierei il 24 e metterei il 36.
E al posto della tua "01 02 03 07 15" io proverei "01 02 03 07 08 36". Giusto?

Poi, per la velocità ti darei un consiglio: vedo che hai implementato le list box per l'output. Ma quando deve elencare 106.000 settine, le list box rallentano notevolmente. Credo che per le prove prima della versione beta potresti usare un file di testo che visionerai facendoci doppioclick, se serve (facendoglielo lasciare aperto in scrittura fino al termine dell'esecuzione e chiudere una volta solo alla fine).
Credo che la differenza di tempo sia proprio dovuta al fatto che deve perdere tempo a comunicare ogni output che nel caso delle settine porta via un sacco di tempo. Per le novine avviene solo tre volte.

Ciao, notte