Problema Optiuni

[Amenhotep]

Salutare!

Nu sunt sigur că aici e locul potrivit să postez (dacă nu e... rog moderatorul să mute acest topic; sau sa-l închidă). Am următoarea problemă:

Într-o grădină sunt n aspersoare. Pentru fiecare aspersor cunoaştem poziţia lui (x[i],y[i]) şi debitul de apă Q[i] (i = 1..n). Robinetul de alimentare cu apă se află la (x[0],y[0]) şi de-acolo trebuie să tragem o reţea arborescentă de conducte care să distribuie apa la toate cele n aspersoare. Dar trebuie să minimizăm costurile reţelei. Ştim că metrul liniar de conductă are un cost c proporţional cu radicalul debitului pe care-l suportă acea conductă: c = k*sqrt(Q). Deci dacă pe o anume distanţă două tronsoane de debite Q1 şi Q2 se pot contopi într-un singur tronson de debit Q1+Q2, costul va fi mai mic (radicalul sumei e mai mic de cât suma radicalilor).

Întrebarea e: care ar fi un algoritm pentru determinarea arborelui de cost minim?

Iată o schiţă explicativă:



În imagine se văd conductele mai groase (şi mai scumpe) care cumulează mai mult debit, pe care apoi îl împart către conducte tot mai subţiri, către consumatorii finali. Am considerat că toţi consumatorii au acelaşi debit -- e o simplificare OK pentru o primă abordare.

(Evident, problema e teoretică -- aspersoarele şi grădina sunt doar metafore.)

Are cineva ceva idei?

a

[Clopotel]

Pentru debite egale, parerea mea este ca avem de-a face o o problema clasica de drum minim (cost minim)
Se rezolva cu grafuri, mai exact cu arbori...
Cred totusi ca la sfarsit drumul va arata cam asa (cu verde), caci in opinia mea acesta este mai eficient, si evident conducta va pleca cu un anumit diamentru si pe masura ce va lasa in urma un nod, se va reduce cu un coeficient, oarecum usor de determinat..(in functie de numarul nodurilor ramase)

In cazul unor debite neegale (de valori diferite mult), atunci este o idee cu calcularea centrului de greutate...

Niste teorie si algoritmi, care e posibil sa te ajute, gasesti aici:
Link1
Link2