 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, 10:59 AM
Mesaj
#2
|
|||||||||||||||||||||
 Umil servitor la Han Grup: Moderator Mesaje: 4.051 Inscris: 2 December 03 Forumist Nr.: 1.345 |
Draga Amenhotep, Imi cer scuze ca nu am fost prea clar in exprimare....
Da, asta am spus, caci in sursa nu se reduce debitul..., acolo neavand consumator...
Corect, caci acela este minimul local si trebuie profitat de el  Atentie: Te rog sa observi, ca, coordonatele punctului sursa sunt foarte importante, si deci trebuie luate in calcul....
Corect, si algoritmul se reia plecand acum de la faptul ca noul "centru de debit" este acum sursa, si se reduc consumatorii cu 1. Atentie: daca de la "centrul de debit" exista mai multi consumatori, aflati la distante egale de el, atunci se traseaza toate(casi sunt minime locale), si apoi se reduce numarul consumatorilor corespunzator..., la fel si debitele...
Pai nu devine noul punct, noua sursa pentru punctele ramase? Ce ai lasat in urma este deja trecut...
Scuze... am omis ca ai notat sursa cu 0... E chestiune de notatie... Poti la fel de bine sa pleci si cu sursa ca fiind nodul 1  , sau 10..., sau a, x... (oricum definesti siruri de genul n[i])
Eu m-am gandit, ca pentru o implementare mai usoara a algoritmului, sa consideri si sursa ca nod, pentru calcularea centrului de masa...Iar in calculul consumului, consumul acesteia ar fi =0...deci debitul ramane neschimbat dupa el...
Eu nu am propus deloc ca, conducta groasa sa mearga pana in "centrul de debit" al consumatorilor... Ar fi o eroare matematica.... Deci, mie mi se pare ca treaba e foarte simpla: In figura ta, avem un triunghi in care varful de jos e sursa... Nu trebuie decat sa-i calculezi centrul de masa ca la geometrie, dar modificat putin cu formulele ce ti le-am dat, caci intervine debitul....(adica, ca si cum, distantele ar fi influentate de ponderile consumului)
Nu, e cam gresit ce spui... Matematic, ca sa fie eficient, sa plece ambii consumatori chiar din sursa, in forma de "V", ar trebui ca acestia sa fie situati la infinit unul de altul... Cand centrul de masa al unui triunghi este chiar intr-un varf al lui? Cand celelalte doua varfuri ar fi situate pe aceeasi dreapta cu el, dar de parti diferite? Cand centrul de masa al unui triunghi cade chiar la mijlocul segementului dintre doua varfuri? Cand doua varfuri sunt situate in acelasi punct, adica suprapuse... Algoritmul,asa cum l-am dat eu, functioneaza si in cazul general si in cazuri particulare, cu debite egale, dar si cu debite exagerat de diferite... Te rog sa-l analizezi mai atent... Observatie: Algoritmul este teoretic...Practic, evident, mai intervin multe lucruri, cum ar fi: numarul de imbinari (reductii), coturi, suporti, prinderi etc, care sunt foarte scumpe... Deci e alta mancare de peste... Evident, se pot introduce si acestea in algoritm si atunci o sa avem (poate), un traseu cu totul diferit decat cel ce nu le ia in calcul...
Eu nu am mai lucrat cu fractalii de vreo 8 ani... Reusisem sa fac lucruri destul de complexe cu ei... Sunt buni la modelarea unor forme naturale, cum ar fi chiar arborii sau neuronii, si permit chiar reglaje sensibile... O sa ma uit pe documentatiile mele si o sa-ti trimit ceva, chiar si niste surse in Pascal/Delphi...Dar, ai putea sa cauti pe internet, sunt convins ca vei gasi mult mai multe documentatii de fractali, chiar surse de programe si chiar generatoare de fractali, gata facute... E fantastic... Eu m-am rupt de ceva ani de treaburile astea si mi-am pierdut indemanarea ...  Vorbesc din aduceri aminte.... 
Ok...daca nu e foarte urgent, o sa ma straduiesc sa-ti fac un program in Delphi, care sa genereze forme asa cum le vrei tu... Acest topic a fost editat de Clopotel: 28 Jan 2006, 11:05 AM -------------------- 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 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 Clopotel Draga Amenhotep,
Dupa cum vezi nu am talent la exp... 28 Jan 2006, 04:10 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:38 PM |