Problema |
Bine ati venit ca musafir! ( Logare | Inregistrare )
Problema |
26 Jan 2006, 02:58 PM
Mesaj
#1
|
|
Cronicar Grup: Moderator Mesaje: 2.132 Inscris: 16 June 04 Din: Bucuresti Forumist Nr.: 3.862 |
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 -------------------- Trebuie să facem ceea ce credem că e bine, dar nu trebuie să credem că ceea ce facem e bine.
|
|
|
27 Jan 2006, 08:45 PM
Mesaj
#2
|
|||||
Umil servitor la Han Grup: Moderator Mesaje: 4.051 Inscris: 2 December 03 Forumist Nr.: 1.345 |
Dragii mei, Personal, mie problema mi se pare interesanta si utila, deoarece in curand vine primavara si trebuie sa ud si eu gradina...
Parerea mea este ca totusi, ideea cu centrul de masa este buna, numai ca trebuie putin adaptata..... Iata la ce ma refer: - in loc de masa, evident avem debit, notam aceasta valoare cu d - sursa are valoarea = suma tuturor debitelor punctelor - sursa este nod in arbore si este chiar nodul 1 - propun urmatoarele notatii: n - numarul de noduri x,y - coordonatele SX=suma de la i=1 la n din xi*di SY=suma de la i=1 la n din yi*di D = suma de la i=1 la n din di X = SX/D Y = SY/D - dupa ce calculam asta, trasam (prelungim) conducta (cu diametrul initial) din nodul 1(sursa) in acest punct de coordonate X,Y - calculam distanta de la acest punct la nodul cel mai apropiat (excluzandu-l pe 1 evident) (nodul 2) - trasam o conducta de debit d2 la la (X,Y) la nodul 2 - se recalculeaza: D=D-d2 punctul de coordonate (X,Y) devine acum nodul 1, adica sursa, si se exclud din calcule atat sursa initiala cat si nodul 2 prin urmare se recalculeaza X si Y in noile conditii Banuiesc ca in doua cicluri for sau while avem coordonarele tuturor punctelor conductei Evident ca la pasul n-2 (asa mi se pare la prima ochire) algoritmul se opreste caci toate datele sunt obtinute... Cred ca va merge... Adica acum nu vad nici un motiv sa nu mearga... Daca gasiti voi vreunul, sa-mi spuneti si mie, sa nu tai tevile degeaba...
E...aici e alta treaba, ca ce am vorbit noi mai sus nu are treaba cu frumosul ci cu eficientul Daca vrei frumos, atunci iti recomand cu caldura sa generezi acest "neuron arborescent frumos" cu ajutorul fractalilor... O sa ai posibilitatea sa setezi si unghiuri si multe alte chestii... Parerea mea... -------------------- Gandurile Mele nu sunt ca gandurile voastre si caile Mele ca ale voastre, zice Domnul.
Si cat de departe sunt cerurile de la pamant, asa de departe sunt judecatile Mele de judecatile voastre si cugetele Mele de cugetele voastre. (Isaia 55:8.9) Ortodoxia - Calea intru Hristos - pe pagina 1 indexarea tematica a subiectelor pt. o usoara urmarire... |
||||
|
|||||
Versiune Text-Only | Data este acum: 9 June 2024 - 06:13 PM |