Grazie a noiseFromAmerika.
martedì 3 febbraio 2009
Ecco perché le compagnie aeree ci fregano
argomenti: economia, matematica
Iscriviti a:
Commenti sul post (Atom)
Patacche
Sono anche su
|
I contenuti di questo blog sono pubblicati sotto una Licenza Creative Commons. Se riprodotti altrove, la loro paternità deve essere attribuita specificando il titolo di questo blog e inserendo un link alla sua home page o al post originale. |
Capisco benissimo cosa vuoi dire...
RispondiEliminaEcco! Se mi tiri fuori il concetto di NP-Completo ste vignette le capiamo io, te e il signor De Gregorio.
RispondiEliminaCon tutto il rispetto :)
Concordo con Mont; e in quanto Concordo, precipito e mi ritiro dal mercato (giusto per restare in tema...)
RispondiElimina@Mont & IMA
RispondiEliminaAvete ragione, detta così sembra un po' esoterica. Senza ripetere qui la definizione rigorosa di problema NP-completo, in modo molto pratico (e mi scuso con i puristi) si può dire che un problema NP-completo è un problema computazionale in cui il tempo richiesto per arrivare alla soluzione aumenta in modo esponenziale (più precisamente: Non Polinomiale) con l'aumentare del numero di parametri.
Un esempio concreto è il problema del commesso viaggiatore: trovare il tragitto più breve per visitare N punti su una mappa, passando una e una sola volta per ciascun punto. Gli spedizionieri internazionali di merci hanno a che fare quotidianamente con questo problema, nel tentativo di ottimizzare i loro costi di trasporto.
Si può provare con carta e matita, tanto per divertirsi. Scaldatevi con quattro punti, trovate il miglior tragitto, poi aggiungete un quinto punto, e così via. Vedrete che ogni volta che aggiungete un punto (cioè un parametro del problema) il numero di percorsi da provare aumenta vertiginosamente (con il fattoriale di N, ossia il numero 1 x 2 x 3 x...x N). Ben presto (prima di N=10) il compito diventerà improbo per un essere umano. Allora i più volonterosi scriveranno un programma che faccia le prove per loro. Su un buon PC, si riesce a testare in tempi ragionevoli tutti i tragitti fino a circa N=15. Ragionevoli nel senso che per N più grandi serviranno migliaia di anni. Su un supercalcolatore di ultima generazione ci si attesta dalle parti di N=25. Possiamo affermare con certezza che il caso N=50 non sarà mai risolvibile da qualunque computer del futuro. La DHL dovrà quindi accontentarsi per sempre di soluzioni approssimate.
Beh, sulla rete si trovano facilmente soluzioni per un numero di punti molto più grande, anche se non sono soluzioni esatte. C'è perfino qualcuno che decenni fa scrisse della roba in Visual Basic che raggiungeva soluzioni accettabili utilizzando un algoritmo genetico per N=80.
RispondiElimina@Miki
RispondiEliminaSapevo che questa non ti sarebbe sfuggita. ;-)
Comunque, ho raggiunto soluzioni accettabili anche per N superiori a 80. Ancora ci campo su quell'algoritmo, ma le applicazioni cui vado dietro oggi sono top secret.
Scusate se sparo una minchiata, ma per N superiore a 25 i risultati verranno fuori tipo intervalli di confidenza, no?
RispondiEliminaAlessio
@Alessio
RispondiEliminaGli algoritmi genetici, come le altre tecniche di tipo stocastico, generano internamente un gran numero di soluzioni tentative che possono essere riguardate come una popolazione statistica. Su di essa, in linea di principio si possono calcolare intervalli di confidenza e fare altre misure. Ma sottolineo "in linea di principio", perché non sono sicuro della validità del metodo: le soluzioni tentative infatti, non sono distribuite casualmente (es. su una distribuzione gaussiana), ma tendono ad addensarsi rapidamente sui minimi locali della funzione obiettivo. Per cui, andremmo a fare una statistica su un campione magari ampio ma comunque molto particolare dell'intera popolazione delle possibili soluzioni tentative.
Ricordiamo che Jurgen cercava il miglior prezzo, e non "circa un prezzo che a occhio pare conveniente".
RispondiEliminabello! Ma non e' lo stesso problema. La distanza tra punti non e' in questo caso paragonabile ai prezzi dei voli. Per esempio il prezzo diminuisce all'aumentare della distanza in alcuni casi. E poi n e' sempre molto piccolo, diciamo minore di 5 perche' giá dopo 3 i prezzi non tornano piu' giu'. Non e' davvero davvero NP-Completo, suvvia.
RispondiEliminai processi di berlusconi sono NP-COMPLETI!!
RispondiEliminahttp://cristianbelcastro.blogspot.com
@Adriano
RispondiEliminaIl problema del commesso viaggiatore era solo un esempio di problema NP-completo, solo una variazione sul tema. Il problema del ticket pricing per i voli è più complesso e, come dice Jurgen, è simile a quello della soddisfacibilità booleana, che è anch'esso NP-completo. Per approfondire, ti consiglio di seguire il link a noiseFromAmerika sotto la striscia.
@Symbian
RispondiEliminaBuona questa! :-)
Ho seguito il link che hai sugegrito, veramente interessante. Anch'io ho comprato diverse volte un biglietto andata e ritorno e poi non sono ritornato.
RispondiEliminaNon mi sembra però NP-Completo, troppo pochi passaggi. Ma non sono un esperto.
Adriano,
RispondiEliminache sia rigorosamente NP-Completo è chiaro che sia una suggestione, e non è di certo stato dimostrato. Ma la "completezza" si riferirebbe comunque non al mero fatto che andata e ritorno costino di meno che sola andata, ma che per scendere ancora di prezzo possano inserirsi (per il viaggio da "buttare") altre destinazioni diverse da quella di origine; e di queste destinazioni (e relative date), e quindi potenziali opzioni, ve ne è un numero enorme. Se finisse là poi certo, basta tentare tutti gli aeroporti per il viaggio di ritorno, problema oneroso ma non esponenziale. Ma se valgono anche le multitratte in numero maggior di due per risparmiare? E il ruolo delle date ottimali? E cosa dire della scelta se mettere il proprio viaggio come prima o seconda tratta? Insomma, non è detto che bastino "pochi passaggi". Meglio accontentarsi di un minimo molto locale una volta trovatolo e fermarsi lì, anche perché "il tempo è denaro" e se ci mettiamo dentro anche quella variabile le cose si complicano.
Certo che è un bel casino.
RispondiEliminaPerò, introducendo vincoli di tipo economico forse ce ne usciamo prima (perché realisticamente, se il tempo è denaro, non credo si possa procedere a cercare la soluzione all'infinito).
Alessio
@Alessio
RispondiEliminaMa infatti alla fin fine, i biglietti li compriamo. Perché non abbiamo a disposizione tempi, informazioni e pazienza infiniti. Usiamo i motori di ricerca su Internet, o le agenzie di viaggi, magari portiamo anche a casa un buon prezzo. Ma dal punto di vista strettamente matematico, non abbiamo risolto il problema, ci siamo accontentati di una soluzione approssimata.
Probabilmente c'erano voli migliori che al momento della nostra prenotazione avevano già esaurito i posti disponibili. O che al momento della nostra prenotazione non avevano ancora aperto l'acquisto di certi posti (tipo last minute).
Quel che è peggio, sullo stesso nostro aereo viaggerà qualcuno che per lo stesso biglietto ha speso meno di noi. Perché magari ha prenotato in un giorno (o in un orario) diverso, perché fa parte di un gruppo, perché ha la tessera del club tal dei tali, perché ha una combinazione volo+hotel, eccetera.