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.
|
|
|
30 Jan 2006, 02:25 PM
Mesaj
#2
|
|||
Vornic Grup: Membri Mesaje: 382 Inscris: 11 May 05 Forumist Nr.: 6.278 |
Cred ca nu am fost suficient de clar la punctul 2. Sa presupunem ca avem date: 1. pozitia sursei S(Xs, Ys, Zs) si pozitiile destinatiilor Di(Xi, Yi, Zi), i=[1..n]; 2. nodurile intermediare Pj(Sj, Dj1, Dj2), j=[1..m] (pentru nodurile intermediare se specifica numai conexiunile - sursa si cele doua destinatii - care pot fi chiar noduri intermediare la randul lor). Dupa modelul din Fig.2 se scrie expresia pentru costul arborelui: C(P1, ..., Pm) = |SP1| (Q1 + Q2 + ... + Qn)^(1/2) + ... unde Pi este dat de coordonatele (ce trebuie calculate) Xi, Yi, Zi. Deci, avem expresia costului ca fiind: C(X1, Y1, Z1, ..., Xm, Ym, Zm) = ... Apoi calculam derivatele partiale ale costului in raport cu Xi, Yi, Zi i=[1..m] si le egalam cu zero. Se obtine un sistem de 3xm ecuatii cu 3xm necunoscute: dC/dX1 = 0 dC/dY1 = 0 dC/dZ1 = 0 ... dC/dXm = 0 dC/dYm = 0 dC/dZm = 0 Se pune problema rezolvarii acestui sistem. Ecuatiile de forma dC/dUi = 0 seamana cu sistemul din Fig.5. Daca gasim o metoda de rezolvare a lui sau, mai bine, o interpretare geometrica a lui (si vad ca Amenhotep face progrese ), atunci putem spera in gasirea unei metode de rezolvare a sistemului general, si este posibil si probabil ca aceasta metoda sa fie una intuitiva, geometrica, pornind de la destinatii catre sursa. Acest topic a fost editat de bonobo: 30 Jan 2006, 02:26 PM |
||
|
|||
Versiune Text-Only | Data este acum: 10 June 2024 - 03:08 AM |