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.
|
|
|
26 Jan 2006, 10:27 PM
Mesaj
#2
|
|
Filosof boem Grup: Membri Mesaje: 6.222 Inscris: 10 July 03 Din: Bucuresti Forumist Nr.: 445 |
Ok, problema in varianta redusa, cu o sursa si 2 aspersoare poate fi formulata in felul urmator: avem un triunghi cu varfurile in cele 2 aspersoare si in sursa. Notam laturile cu a, b, c. Trebuie sa gasim punctul O unde conducta mare de la sursa se imparte in 2. Notam cu a1, b1, c1, lungimile segmentelor de la O la cele 3 varfuri.
Problema se formalizeaza in felul urmator Sa se determine min(a1*sqrt(2)+b1+c1) //am presupus ca a1 este conducta care pleaca din sursa cu conditiile triunghi(a,b,c) triunghi(c,a1,b1) triunghi(a,b1,c1) triunghi(b,a1,c1) unde triunghi(a,b,c) se transcrie in a<=b+c, b<=a+c, c<=a+b Aceasta este o problema foarte complexa la prima vedere. In realitate este o problema clasica de optimizare liniara pentru care exista un algoritm, algoritmul simplex (se gasesc implementari ale lui in toate programele mari specializate pe matematica sau statistica si probabil si implementari de sine statatoare pe net). Insa cand se pune problema generalizata... nu stiu, nu mi-a venit inca nici o idee. Poate va vine voua. Totul e sa gasim punctul in care se desparte prima conducta mare cumva. Dup-aia e o simpla problema de inductie generalizata. P.S. Amenhotep, problema asta ai inventat-o tu sau ai gasit-o pe undeva? Edit: nu prea cred sa aiba vreo legatura centrul de masa in toata afacerea asta... asta ar insemna ca din simplexul ala sa ti se simplifice cumva radical din 2-ul ori din experienta mea asa ceva nu are cum sa se intample. Acest topic a fost editat de Catalin: 26 Jan 2006, 11:53 PM -------------------- A nation cannot prosper for long when it favors only the prosperous - Obama
|
|
|
Versiune Text-Only | Data este acum: 15 May 2024 - 08:44 AM |