Funzione complessa, (si può descrivere?)

Ho una richiesta da fare:

ho ottenuto alcuni valori numerici e vorrei capire qual è la formula che descrive questa funzione (a 5 variabili).
Leggendo diverse pagine tramite Google ho orientato le mie ricerche su quella che in matematica viene chiamata 'regressione' e sulla 'interpolazione'.

Detto in altri termini sto cercando la formula della funzione f a partire dai valori puntuali (noti) di essa con alcuni parametri delle variabili (x1, x2, x3, x4, x5).

Per maggior chiarezza uso v,k,t,m e b al posto di x.

I valori che ho estrapolato dalla mia funzione sono i seguenti :

(v,	k,	t,	m,	b)	---->	f(), f(), f(), f(), f(), f(), f(), f(), f(), f(), f(), f()
4	3	2	2	3		1, 2, 3, …
5	4	2	2	3		1, 2, 3, …
6	5	2	2	3		1, 2, 3, …
7	6	2	2	3		1, 2, 3, …
8	7	2	2	3		1, 2, 3, …
5	3	2	2	4		1, 6, 7, 8, …
6	3	2	2	6		1, 2, 10, 16, 17, 18, …
8	4	2	2	6		1, 10, 34, 55, 56, 61, …
8	5	2	2	4		1, 20, 21, 53, …
10	5	2	2	6		1, 47, 87, 180, 223, 236, …
7	3	2	2	7		1, 10, 15, 21, 24, 28, 29, …
9	4	2	2	8		1, 12, 19, 26, 51, 90, 94, 96, …
10	4	2	2	9		1, 65, 84, 93, 98, 102, 179, 192, 199, …
12	5	2	2	9		1, 86, 179, 321, 540, 576, 597, 722, 771, …
12	6	2	2	6		1, 65, 460, 588, 841, 860, …
8	3	2	2	11		1, 2, 12, 16, 21, 32, 35, 40, 43, 44, 50, …
9	3	2	2	12		1, 14, 23, 28, 36, 42, 48, 54, 56, 60, 72, 77, …
11	4	2	2	11		1, 16, 91, 120, 140, 203, 236, 244, 274, 278, 280, …
12	4	2	2	12		1, 110, 121, 165, 178, 258, 272, 343, 355, 390, 400, 407, …
14	5	2	2	12		1, 137, 596, 630, 699, 802, 852, 867, 1567, 1580, 1593, 1980, …

Ho anche trovato conferma della fattibilità di tale ricerca utilizzando un programma in versione dimostrativa
Per maggiori informazioni sull'uso di questo software inserisco alcuni dettagli qui sotto:

Potrei provare a lasciarlo funzionare anche tutta la notte,
ma ho pensato di chiedere prima un parere, qui nel forum, per non vanificare energie.


La mia ricerca apparirà un po' astrusa, ma ha un fondamento e posso descrivere in maniera più esaustiva da cosa deriva e da dove provengono i valori numerici di cui sopra (anzi, bravo chi lo ha già capito! ).

Qualunque consiglio per riuscire a svolgere questo compito mi aiuterebbe.
Stefano

Sì Nino, i valori sono gli indici delle combinazioni.
Le matrici della tabella è vero che rappresentano uno dei tanti possibili riduttori,
ma non sono scelte a caso. Le ho prese da LaJolla scegliendo tra quelle indicate in grassetto (quelle non migliorabili).
Non conosco quali siano i primati irriducibili su Weefs, altrimenti avrei attinto anche da lì.

Sarebbe utile riuscire a trovare una regola che accomuna almeno una piccola parte dei sistemi.
Ad esempio, se si riuscisse a trovare la formula che fornisce le combinazioni dei ridotti di un certo tipo;
Che so!? Quelli con V il doppio di K, oppure con V e K numeri primi, allora si potrebbe provare a calcolare un ridotto dello stesso tipo, con V molto grande (cosa che i software non permettono di fare per via dei limiti di memoria)

Se non ho visto male una piccola regola, in fondo già esiste, ma è un caso particolare che non ci è molto d'aiuto:
osservando le matrici con v=k+1 si nota che la copertura si può ottenere con le prime t+1 combinazioni in ordine lessicografico
infatti 10,9,2,2=3 (la 1, la 2 e la 3) e così per gli altri dello stesso tipo..
11,10,2,2=3
12,11,2,2=3
...
10,9,3,3=4 (sempre le prime in ordine vanno bene)
11,10,3,3=4
...
10,9,4,4=5 (sempre le prime t+1 nell'ordine lessicografico)
11,10,4,4=5

quindi si può ipotizzare, il
200,199,50,50=51


Trovare una formula per sistemi più interessanti è un'utopia, ma per passatempo, proverò a isolare alcuni un certo tipo di matrice e vedo se per fortuna salta fuori qualcosa.

Certamente si tratta di un caso elementare e poco utile dal punto di vista pratico,
ma sto facendo progressi.

Sto osservando le matrici del tipo
v,k,t,m con v=k+2
e mi sembra che oltre un certo v, precisamente con
V>(2*t)+1 (v: strettamente maggiore del doppio di t, + 1)

si possano costruire le matrici col minimo numero di combinazioni
scegliendo gli indici lessicografici secondo la seguente relazione

indice n = 2 * n^2 - n



e fermandosi quando si sono generate t+1 combinazioni.

Dico mi sembra perchè ho generato diverse matrici con questa procedura senza trovare neanche un caso che dimostri il contrario e tutte coprono al 100%.
I loro inversi sono registrati su Weefs con lo stesso numero di combinazioni.
Come ad esempio:
il 32,30,15,15 = 16 inverso di 32,2,2,17 (Colin Barker)
il 36,34,16,16 = 17 inverso di 36,2,2,20 (Alessandro Jurcovich)
il 38,36,18,18 = 19 inverso di 38,2,2,20 (Alessandro Jurcovich)
il 19,17,8,8 = 9 inverso di 19,2,2,11 (Colin Barker)
il 24,22,9,9 = 10 inverso di 24,2,2,15 (Colin Barker)


Per costruire quest'ultimo, il 24,22,9,9 ho preso le prime b= t+1=9+1 =10 combinazioni i cui indici
sono ottenuti come da tabela seguente:

comb. n -> indice comb.
1 -> 1
2 -> 6
3 -> 15
4 -> 28
5 -> 45
6 -> 66
7 -> 91
8 -> 120
9 -> 153
10 -> 190
11 -> 231
12 -> 276
13 -> 325
14 -> 378
15 -> 435
16 -> 496
17 -> 561
18 -> 630
19 -> 703
20 -> 780
21 -> 861
22 -> 946
23 -> 1035
24 -> 1128
25 -> 1225
26 -> 1326
27 -> 1431
28 -> 1540
29 -> 1653
30 -> 1770


quindi, in pratica, il 24,22,9,9=10 è ottenuto come segue

n -> f(n) -> combinazione f(n) presa dal c(24,22)
1 -> 1 -> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
2 -> 6 -> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 23 24
3 -> 15 -> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 21 22 23 24
4 -> 28 -> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 19 20 21 22 23 24
5 -> 45 -> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 17 18 19 20 21 22 23 24
6 -> 66 -> 1 2 3 4 5 6 7 8 9 10 11 12 15 16 17 18 19 20 21 22 23 24
7 -> 91 -> 1 2 3 4 5 6 7 8 9 10 13 14 15 16 17 18 19 20 21 22 23 24
8 -> 120 -> 1 2 3 4 5 6 7 8 11 12 13 14 15 16 17 18 19 20 21 22 23 24
9 -> 153 -> 1 2 3 4 5 6 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
10 -> 190 -> 1 2 3 4 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24


Questo mi sembra meno ovvio.

Infatti, se mi servisse il 50,2,2,30 calcolerei l'inverso dopo aver costruito il 40,48,20,20 =21 combinazioni con la formuletta sopra
(non conosco altri strumenti in grado di farlo, forse solo il WUC)

Stefano

Grazie sistematore,

non ho certo la pretesa di dimostrare che la classe NP=P
I matematici cercano almeno una smentita da...secoli..si può dire!
Però mi rendo anche conto che le soluzioni per gli spazi sui cui lavorano i sistemisti non sono esattamente la stessa cosa di uno spazio vettoriale puro. Nel senso che per i sistemi devono essere soddisfatte delle condizioni (la garanzia per la copertura con un determinato numero di estratti) che, in fondo vincolano e perciò riducono lo spazio delle soluzioni possibili.

Vedo che conosci bene i problemi NP, quindi posso dirti che ho effettuato diverse ricerche per la soluzione di quello che è conosciuto come 'minimum set cover' perché mi sembra sia esattamente la definizione formale del problema delle lotterie, anche se i matematici si accontentano di soluzioni a lunghezza mista, per dirlo nel gergo sistemistico.

Ho trovato un programmino ben fatto che risolve un problema equivalente NP: il cosiddetto 'Vertex cover'.
Solo che non riesco (e non so se sia fattibile) a convertire il 'minimum set cover' nel 'vertex cover', altrimenti credo si possa usare questo strumento per cercare sistemi ridotti a copertura ottimale.

Se può interessare posso postare il programma che ho trovato.


Stefano.



PS=
quelli sotto sono i valori puntuali della funzione che, secondo me, descrive i v,k,t,m con v=k+4 (come ad esempio 29,25,6,6 oppure 24,20,3,3..).
Non sono riuscito a risalire alla funzione che regola questa successione, forse qualcuno col solo intuito è più bravo di me col computer:

n -> f(n)
1 -> 1
2 -> 70
3 -> 495
4 -> 1820
5 -> 4845
6 -> 10626
7 -> 20475

Ecco, vedi
la relazione Held-Karp (che non conoscevo), è relativa ad un altro problema della classe dei problemi NP, quello del 'commesso viaggiatore' (Travel Salesman Problem o brevemente TSP).
Infatti il 'Lottery Problem' non è molto diverso dal TSP, dal punto di vista della complessità. Cioè, se troviamo una soluzione per uno dei due, allora l'abbiamo trovata anche per l'altro...

Per tentare di risolvere il TSP (che mi pare il più gettonato dalle case di software per via del fatto che aiuta nella vita quotidiana, vedi il navigatori tipo TomTom che indicano il percorso più breve oppure la pianificazione dei trasporti di merci con la minore spesa di carburante) si può usare, tra gli altri, questo potente e famoso programma: Concorde (che io ho anche scaricato e provato. Funziona egregiamente).

La difficoltà sta nel trasformare una soluzione al TSP adattandola e interpretarla come un sistema ridotto col minor numero di combinazioni.

Come dicevo, allo stesso modo, ho provato un software che risolve il 'vertex cover problem' sperando di poter sfruttare le soluzioni per migliorare un sistema a garanzia.
Però non riesco a descrivere un sistema di partenza in forma di grafo (che il programma riuscirebbe ad ottimizzare).




Non capisco,
il software che hai prodotto prende una matrice già pronta come base e la adatta coi numeri da mettere in gioco?

Esatto ,

f(n) =COMBINAZIONE(n*4;4)


Io ho lasciato girare il programma Eurequa per una notte intera, ma non è arrivato alla soluzione anche perché non prevede l'utilizzo della funzione Combinazione.
Perciò la formula corretta che hai trovato dice che la successione continua così:

n -> f(n)
1 -> 1
2 -> 70
3 -> 495
4 -> 1820
5 -> 4845
6 -> 10626
7 -> 20475
8 -> 35960
9 -> 58905
10 -> 91390
11 -> 135751
12 -> 194580
13 -> 270725
14 -> 367290
15 -> 487635
16 -> 635376
17 -> 814385
ecc...

Quindi, adesso che ho gli indici lessicografici successivi, posso calcolare le combinazioni
ad esempio del 40,36, 9,9 che dovrebbe essere di 10 combinazioni (t+1), queste

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 37 38 39 40
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 33 34 35 36 37 38 39 40
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 29 30 31 32 33 34 35 36 37 38 39 40
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
1 2 3 4 5 6 7 8 9 10 11 12 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
1 2 3 4 5 6 7 8 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
1 2 3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

Questo sistema non è presente su LaJolla (è l'inverso di 40,4,4,31).

Perché funziona ??