Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - aiutoo
Forum - C/C++ - aiutoo

Avatar
miranda (Normal User)
Newbie


Messaggi: 1
Iscritto: 26/11/2007

Segnala al moderatore
Postato alle 14:13
Lunedì, 26/11/2007
salve a tutti...ho un problema da risolvere in c++, ma per me è impossibile!!! volete darmi una mano?
Il problema è definito come segue:
Sia P={p1,p2,…pn} un insieme di postazioni. Sia D un insieme di triple del tipo <px, py, dxy>, con px e py in P, e dxy un intero positivo che indica la distanza tra px e py. Per le coppie di postazioni per le quali non è definita la distanza si assume che essa sia infinita.
Una stazione meteo è costituita da un sensore di temperatura, uno di pressione ed uno di umidità, posizionati in tre postazioni px, py e pz tali che min{(dxy+dxz), (dxy+dyz), (dxz+dyz)} ≤ K, con K una costante. Ogni sensore può appartenere al più ad una stazione meteo.
Si determini, se esiste, una soluzione al problema di collocare M stazioni meteo nella rete.

PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6109
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 13:28
Martedì, 27/11/2007
Così ad occhi mi sembra rientri in una categoria dei problemi np-complete.

http://it.wikipedia.org/wiki/NP-Completo

Solo che non riesco bene ad identificare quale (sto ancora studiando quest'argomento e non lo padroneggio bene). Se lo trovi comunque poi risolverlo è facile, ci sarà sicuramente qualcuno che ha già fatto l'implementazione in C++ per quell'algoritmo.


Seguimi su Twitter: http://www.twitter.com/pierotofy

Fai quello che ti piace, e fallo bene.
PM Quote