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.
|
|
|
28 Jan 2006, 01:25 AM
Mesaj
#2
|
|||||||||||
Cronicar Grup: Moderator Mesaje: 2.132 Inscris: 16 June 04 Din: Bucuresti Forumist Nr.: 3.862 |
Deci ducem o conductă groasă pānă īn "centrul de debit" (centrul de masă ponderat cu debitele). OK, īnţeleg.
Deci ducem apoi o conductă subţire pānă la cel mai apropiat consumator. Pe urmă probabil că ne īntoarcem īn "centrul de debit"... cred (că altfel n-am mai avea de unde să dăm debit celorlalţi consumatori). Corect?
Aici m-ai pierdut complet. Cum o să devină (X,Y) sursa? Şi de ce ai notat sursa ca fiind nodul 1 şi nu nodul 0, cum am formulat eu problema? Dacă sursa e nodul 1 atunci ai doar n-1 aspersoare...
Nu ştiu dacă merge sau nu, pentru că nu am īnţeles propunerea ta. Poţi te rog să exemplifici pe cazul acesta foarte simplu? Eu am găsit că costul minim pentru instalaţia din figură este 42,42 lei (cānd conducta groasă merge 10 metri şi apoi se ramifică). Dacă tu propui ca această conductă groasă să meargă pānă īn "centrul de debit" al consumatorilor (care se află la jumătatea distanţei dintre cei doi consumatori)... vei obţine un cost mai mare (48,28 lei). Īncă o īntrebare: īn figura de mai sus, algoritmul propus de tine este influenţat de distanţa orizontală dintre cei doi consumatori? Adică, dacă de exemplu cei doi consumatori de īndepărtează simetric cu īncă 10 metri fiecare (distanţa dintre ei ajungānd 40 de metri), ce rezultat dă algoritmul tău? Eu spun că īn acest caz cel mai mic cost se obţine cu un "arbore" īn formă de V: adică din sursă pleacă direct conducte subţiri către cei doi consumatori, fără să mai existe conductă groasă -- şi costul minim este 56,56 lei. Algoritmul tău ce zice?
Sunt foarte interesat de orice sugestii. Cum crezi că pot genera cu ajutorul fractalilor un arbore ale cărui frunze să fie cele din figura de mai jos, de exemplu? Īnchipuie-ţi că acolo a fost desenat un arbore (neuron) frumos şi cineva a şters ramurile, lăsānd doar sinapsele şi nişte indicii despre direcţia din care veneau ramurile. Şi eu acum trebuie să refac arborele, pornind din rădăcina albastră şi ajungānd īn fiecare sinapsă roşie, conform direcţiilor indicate. Īncāt să arate cāt mai natural. Cum rezolv asta cu ajutorul fractalilor? 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: 16 May 2024 - 01:35 AM |