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

[bonobo]

Cred ca trebuie luate in calcul urmatoarele situatii:

1. Pentru un nod simplu (sursa S, aspersoare D1(Q1) si D2(Q2), distribuitor P):
Fig.1

Costul total al ansamblului este:
Fig.2

Dupa cum se vede, costul depinde de cele 3 (sau 2) coordonate ale lui P (nodul intermediar). Minimul se obtine acolo unde derivatele partiale ale costului in functie de coordonate se anuleaza:
Fig.3

Explicitand ecuatia costului in functie de coordonate, obtinem:
Fig.4

In final, pentru conditia de minim, obtinem urmatorul sistem de ecuatii (3 ecuatii, 3 necunoscute):
Fig.5


2. Pentru un arbore definit topologic (pentru fiecare nod Pi este definita sursa si cele doua aspersoare care, toate pot fi noduri intermediare la randul lor): se obtine un sistem de mai multe ecuatii de genul celor din Fig.5 (cate un set pentru fiecare subansamblu - sursa, distribuitor, doua aspersoare).


3. Pentru cazul in care sunt specificate numai sursa si aspersoarele se iau in calcul toate variantele topologice de conectare a lor si pentru fiecare se aplica pct 2. Avand in vedere ca numarul variantelor creste exponential cu N (numarul aspersoarelor), problema este nedecidabila in timp rezonabil de la un N incolo.


Singura problema care ramane este urmatoarea: cum se rezolva in cazul general sistemul de ecuatii din Fig 5 ?
Este un sistem destul de interesant (la prima vedere)... Daca se ridica la patrat cele doua (sau trei) ecuatii si se aduna, se obtine un loc geometric petru P care nu depinde nici de S, nici de Q1 si Q2, ci numai de pozitia celor doua aspersoare.

Acest topic a fost editat de bonobo: 30 Jan 2006, 03:17 AM