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, 11:50 AM
Mesaj
#2
|
|||||
Cronicar Grup: Moderator Mesaje: 2.132 Inscris: 16 June 04 Din: Bucuresti Forumist Nr.: 3.862 |
Analiza mi se pare impecabilă.
Da, locul geometric e suprafaţa: 0 = (x1 - x)(x2 - x) + (y1 - y)(y2 - y) + (z1 - z)(z2 - z), care se scrie mai simplu ca produsul scalar al celor doi vectori D1P şi D2P: 0 = D1P * D2P. Adică suprafaţa respectivă e locul geometric al punctelor P astfel īncāt segmentele PD1 şi PD2 fac unghi de 90 de grade īntre ele. Aceasta e exact o sferă avānd diametrul D1D2. (Pentru problema plană e cercul de diametru D1D2.) Rezultatul e foarte folositor, căci mai rămāne să determinăm direcţia lui SP -- dacă o ştim, soluţia sună aşa: "Pornim cu conducta groasă din S şi mergem pe direcţia 'cutare' pānă īntālnim suprafaţa sferei de diametru D1D2; acolo ne oprim şi despărţim conducta īn două." Direcţia lui SP o putem preciza prin punctul P' care se obţine prelungindu-l pe SP pānă īntālneşte segmentul D1D2: Nu am făcut calculele īncă, dar soluţia va suna aşa: "Īn funcţie de Q1 şi Q2, determinăm un punct P' pe segmentul D1D2; pornim cu conducta groasă din S şi mergem spre acest punct P' pānă īntālnim suprafaţa sferei de diametru D1D2; acolo ne oprim şi despărţim conducta īn două." Putem trage deja o concluzie interesantă: dacă S se află īn interiorul cercului de diametru D1D2, atunci soluţia e īn formă de V (conductele subţiri pornesc direct spre consumatori). O altă concluzie interesantă: privind din exteriorul cercului D1D2, cei doi consumatori pot fi "reduşi" īn punctul P' (care depinde doar de debitele Q1 şi Q2 -- acest punct ar putea fi numit "centrul de debit" al celor doi consumatori). Observaţia asta cred că ne dă cheia algoritmului: reducerea succesivă a unor perechi de puncte īn "centrul lor de debit"... 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 - 10:49 AM |