CITAZIONE (kabila @ 6/4/2016, 11:02)
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).
CITAZIONE (sistematore @ 6/4/2016, 11:13)
sempre di soluzioni approssimate parliamo giusto?
....
Ho cosi realizzato ad uso personale un software da superenalotto di costruizione di sistemi dove i wheels sono quelli di LaJolla (di tipo Turan) e quelli del sito Weefs.
....
Non capisco,
il software che hai prodotto prende una matrice già pronta come base e la adatta coi numeri da mettere in gioco?
