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, 04:34 PM
Mesaj
#2
|
|
Cronicar Grup: Moderator Mesaje: 2.132 Inscris: 16 June 04 Din: Bucuresti Forumist Nr.: 3.862 |
"Călătoria" e pe o câmpie unde nu există trasate drumuri (înaintarea în orice direcţie costă la fel de mult, contează doar asocierea sau nu cu alţi călători).
Între timp, cred că am găsit singur soluţia la problema cu "călătoria". Algoritmul ar fi aşa: Pornesc cei N oameni în grup, pe direcţia "centrului de masă" al punctelor de destinaţie. Direcţia aceasta împarte destinaţiile (şi deci călătorii) în două categorii: unele destinaţii se află la dreapta direcţiei curente, altele la stânga. În fiecare moment determinăm ce-i mai ieftin: a. subgrupurile "de dreapta" şi "de stânga" rămân unite şi mai fac împruenă un pas ds pe direcţia centrului comun de masă, sau b. subgrupurile "de dreapta" şi "de stânga" se despart şi fiecare o ia spre centrul de masă al destinaţiilor "de dreapta", respectiv "de stânga", înaintând cu câte un pas ds pe aceste direcţii. Dacă b e mai ieftin, se produce ruptura. Şi algoritmul se reia pentru fiecare subgrup în parte. Pentru ponderi egale ale destinaţiilor (debite egale în prima formulare), am impresia că totul se reduce la o socoteală de unghiuri: când direcţia către centrul de masă "de dreapta" (sau "de stânga") face un anume unghi cu direcţia către centrul de masă comun, atunci se produce ruptura: Ei? 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 - 12:41 AM |