 Problema |
 |
|
Bine ati venit ca musafir! ( Logare | Inregistrare )
HanuAncutei.com - ARTA de a conversa > Odaia Dezbaterilor: Stiinta si Cultura > Exploratorium > Stiinta si Tehnica
 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.
|
 |
 
|
 |
Raspunsuri
|
28 Jan 2006, 04:10 PM
Mesaj
#2
|
|||||
 Umil servitor la Han Grup: Moderator Mesaje: 4.051 Inscris: 2 December 03 Forumist Nr.: 1.345 |
Draga Amenhotep, Dupa cum vezi nu am talent la explicatii ca nu ma pot face inteles...  O sa reformulez altfel...
Nu, nu vei inmulti cu zero niciodata cand vei calcula coordonatele, caci acolo nu intervine consumul ci doar debitul ce trece prin nod... Poate doar cand calculezi debitele urmatoare, pentru simplitatea algoritmului cand e vorba de calculul consumului in centrul de masa inmultesti cu zero... Din contra, in punctele "sursa" debitul D= suma debitelor nodurilor nealimentate inca.... Deci in cazul simplu al triunghiului tau avem formulele: D0= d1+d2 Xcm = (d0*x0+d1*x1+d2*x2)/(d0+d1+d2) Ycm = (d0*y0+d1*y1+d2*y2)/(d0+d1+d2) si astfel avem pozitia centrului de masa... Aici trebuie sa punem un distribuitor cu reductiile respective...pentru ca in directia lui N1 pleaca o conducta de debit d1, iar catre N2, pleaca o conducta cu debit d2.. Desigur in care avem mai multe puncte, si acestea se continua din centrul de masa spre N2, atunci conducta va avea debitele d2 + suma debitelor nodurilor ramase..., iar Xcm,Ycm este CM-ul intregului sistem... Si se reiau calculele la fel numai ca Xcm si Ycm calculat la pasul anterior devine acum sursa... Adica poate fi facuta o functie cu parametrii ...  Oricum trebuie mai intai stabilite niste principii, de ex. Xcm si Ycm sa fie coordonatele intregului sistem de noduri, inclusiv nodul sursa, sau in calculul coordonatelor CMului sa fie luate in calcul doar nodurile cu d>D/4 ori ceva de acest gen... Apoi trebuie stabilit daca pe segmentul de dreapta ce uneste Xcm cu X'cm nu exista nici o perpendiculara pe acesta de la vreun nod... In acest caz care ar fi procedura? Fie ne oprim si mutam X'cm in acest punct si trasam de aici perpendiculara, fie lasam X'cm acolo unde cade si ne intoarcem cu o teava catre acel nod... Asta se implementeaza in algoritm si poate fi optiune de utilizator... Deci modelul matematic este putin mai complex datorita numarului de factori ce priveste eficienta costurilor care pot intreveni, si nu neaparat, de calcul geometric... De asemenea, costurile sunt iar o problema de optimizare, care pot sa dea totul peste cap, caci daca racord, manopera etc sunt foarte scumpe in raport cu teava, atunci poate e mai simplu sa trecem teava direct prin noduri si sa nu mai folosim racorduri..., folosind doar algoritmul de la calculul drumului minim.... Evident, chiar programul poate sa sugereze varianta optima dupa ce a facut o evaluare in prealabil... Daca aplicatia devine "industriala", si avem timp si motivatia  sa o complicam, putem sa folosim tot felul de algoritmi, inclusiv retele neuronale, care sa tina cont de tot felul de factori cum ar fi clima, perioada de functionare, pozitia Soarelui in momentul functionarii etc..  Ca idee e interesanta si provocatoare... Daca trebuie sa te apuci efectiv de lucru trebuie sa stabilesti din capul locului unde vrei sa te opresti... Ce pot eu sa fac acum, este sa-ti recomand niste site-uri, care e posibil sa-ti foloseasca: http://mathworld.wolfram.com/ http://www.basegroup.ru/ http://www.math.com/ Si multe altele, dar iata unul in care sunt puse in practica niste treburi interesante: http://www.liquidjourney.com/ Mai vorbim... PS: nu am pretentia ca varianta asta ar fi buna de ceva... Merita doar sa vedem de ce nu e buna, ca sa gasim alta mai buna
Acest topic a fost editat de Clopotel: 28 Jan 2006, 04:17 PM -------------------- 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... |
||||
|
|
|
||||
Mesaje in acest topic
Amenhotep Problema 26 Jan 2006, 02:58 PM
Amenhotep Problema poate fi reformulată şi astfel:... 26 Jan 2006, 03:48 PM Ovidius QUOTE O fi echivalentă formularea asta cu cea... 26 Jan 2006, 03:59 PM Ovidius Pentru rezolvare, cred ca ar fi bine sa reducem pr... 26 Jan 2006, 04:34 PM Amenhotep "Călătoria" e pe o câmpie unde... 26 Jan 2006, 04:34 PM actionmedia Si centrul de masa cum il afli? 26 Jan 2006, 04:41 PM Amenhotep Păi... media coordonatelor.
a
EDIT: Media p... 26 Jan 2006, 04:43 PM Clopotel Pentru debite egale, parerea mea este ca avem de-a... 26 Jan 2006, 05:15 PM Amenhotep Da Clopoţel, ai dreptate, există algorit... 26 Jan 2006, 07:24 PM Catalin Ok, problema in varianta redusa, cu o sursa si 2 a... 26 Jan 2006, 10:27 PM Catalin Cred ca am gasit si o solutie la cazul general:
A... 27 Jan 2006, 12:57 AM Amenhotep QUOTE (Catalin @ 26 Jan 2006, 10:27 PM)Sa se ... 27 Jan 2006, 01:05 AM axel Suna a problema de optimizare. In nici un caz a pr... 27 Jan 2006, 08:59 AM Amenhotep Ce înseamnă LP sau QP?
QUOTE (Căt... 27 Jan 2006, 05:25 PM Catalin LP e programare liniara, m-as miza!
Adica ce ... 27 Jan 2006, 05:35 PM Amenhotep Errr... Şi QP atunci ce să fie? Quick Pr... 27 Jan 2006, 06:25 PM axel LP = linear programming
Ai sistem de ecuatii linia... 27 Jan 2006, 06:35 PM Amenhotep Dar care sunt ecuaţiile liniare? Am arăt... 27 Jan 2006, 06:42 PM Clopotel Dragii mei,
Personal, mie problema mi se pare inte... 27 Jan 2006, 08:45 PM Amenhotep QUOTE (Clopotel @ 27 Jan 2006, 08:45 PM)- dup... 28 Jan 2006, 01:25 AM axel QUOTE (Amenhotep @ 27 Jan 2006, 07:42 PM) Dar care... 28 Jan 2006, 02:20 AM Clopotel Draga Amenhotep,
Imi cer scuze ca nu am fost prea ... 28 Jan 2006, 10:59 AM Amenhotep QUOTE (Clopotel @ 28 Jan 2006, 10:59 AM)Imi c... 28 Jan 2006, 12:55 PM Amenhotep QUOTE (axel @ 28 Jan 2006, 02:20 AM)Ai fii ui... 28 Jan 2006, 01:46 PM Amenhotep Of Clopoţel... Daca mi-ai raspunde la întreba... 28 Jan 2006, 06:16 PM axel QUOTE (Amenhotep @ 28 Jan 2006, 02:46 PM) Astfel, ... 29 Jan 2006, 08:08 AM bonobo Cred ca trebuie luate in calcul urmatoarele situat... 30 Jan 2006, 03:09 AM axel Sa presupunem ca ati reusit sa gasiti formulele pe... 30 Jan 2006, 04:22 AM Amenhotep QUOTE (bonobo @ 30 Jan 2006, 03:09 AM) Singura pro... 30 Jan 2006, 11:50 AM Amenhotep Grr... S-a blocat taman când postasem şi eu..... 30 Jan 2006, 02:24 PM bonobo QUOTE (axel @ 30 Jan 2006, 04:22 AM)Sa presup... 30 Jan 2006, 02:25 PM Amenhotep Iată ce frumos arată treaba pentru trei ... 30 Jan 2006, 03:41 PM Amenhotep QUOTE (Catalin @ 27 Jan 2006, 12:57 AM)Cati a... 31 Jan 2006, 04:16 PM Amenhotep Am implementat algoritmul! (Cu echilibrul celo... 8 Feb 2006, 04:49 PM
Erwin problema e deja veche acum, dar poate nu stric... 16 Dec 2007, 11:43 PM |
|
Versiune Text-Only | Data este acum: 15 May 2024 - 07:02 PM |