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:24 PM
Mesaj
#2
|
|
Cronicar Grup: Moderator Mesaje: 2.132 Inscris: 16 June 04 Din: Bucuresti Forumist Nr.: 3.862 |
Grr... S-a blocat taman când postasem şi eu... Scriu din nou:
Ecuaţia o putem înmulţi cu versorii axelor şi după ce adunăm vedem că se simplifică nişte chestii şi ajungem la o ecuaţie vectorială simplă: 0 = sqrt(Q1+Q2)*versor(PS) + sqrt(Q1)*versor(PD1) + sqrt(Q2)*versor(PD2) Deci în punctul P ducem vectori către cele trei puncte, de lungimi egale cu sqrt(Q1), sqrt(Q2) şi sqrt(Q1+Q2). Aceşti trei vectori trebuie să-şi facă echilibru (suma lor să facă zero). De-aici regăsim uşor concuzia mesajului precedent: cei trei vectori respectând teorema lui Pitagora, rezultă că ei formează un triunghi dreptunghic -- deci direcţiile PD1 şi PD2 fac unghi de 90 de grade (deci P se află pe sfera/cercul de diametru D1D2). Soluţia completă este: Adică: Desenăm cercul de diametru D1D2. Apoi, pe partea opusă lui S, construim triunghiul dreptunghic cu catete proporţionale cu sqrt(Q1), respectiv sqrt(Q2), ca în figură. Astfel determinăm punctul P'. Din S pornim cu conducta groasă către P', iar când întâlnim cercul ne oprim şi ramificăm în două conducte subţiri. Observaţie: S-ar putea ca această construcţie geometrică să ne conducă "prin spatele" unui punct (adică să întretăiem diametrul D1D2 în afara cercului). Nu e bine. În astfel de cazuri, soluţia de cost minim e următoarea: mergem cu conducta groasă până la punctul cel mai apropiat, apoi continuăm cu conductă subţire până la următorul punct (e deci un arbore degenerat). Asta e interpretarea geometrică a soluţiei pentru doi consumatori. Algoritmul general va trebui deci să grupeze consumatorii doi câte doi în diverse moduri şi să calculeze punctele P' corespunzătoare. A, şi mai trebuie făcut un lucru: să determinăm "lungimea echivalentă de conductă groasă". Adică să determinăm un punct P'', aflat pe segmentul PP', astfel încât costul unei conducte groase de la P la P'' să fie egal cu costul conductelor subţiri de la P la D1 şi la D2... a -------------------- Trebuie să facem ceea ce credem că e bine, dar nu trebuie să credem că ceea ce facem e bine.
|
|
|
Versiune Text-Only | Data este acum: 15 May 2024 - 08:16 AM |