 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
|
27 Jan 2006, 01:05 AM
Mesaj
#2
|
|||||||
|
Cronicar Grup: Moderator Mesaje: 2.132 Inscris: 16 June 04 Din: Bucuresti Forumist Nr.: 3.862 |
Da, aşa e pt. 2 puncte. Cu observaţia că dpdv geometric condiţiile se reduc la: punctul O să fie în interiorul triunghiului (pentru orice soluţie cu O în afara triunghiului, se poate arăta că există o soluţie mai bună cu O în interiorul triunghiului). Am exprimat în funcţie de coordonatele x şi y ale lui O, am derivat şi am găsit minimul. Nu mai ştiu soluţia analitică, dar parcă-i găsisem şi o interpretare geometrică frumoasă.
Păi eu m-am gândit aşa: dacă cele n puncte sunt grupate în două aglomerări distincte şi pornim de undeva departe, acele două aglomerări pot fi aproximate prin centrele lor de masă (din origine "se văd" ca două puncte). Şi tratăm problema ca şi cum am avea doar două aspersoare (de debite diferite, date de numărul de aspersoare din fiecare aglomerare). După ce ţeava cea mare s-a despărţit în două, pentru fiecare ţeavă repetăm algoritmul -- până când se apropie suficient de mult de aglomerare încât "să distingă" două sub-aglomerări diferite, una de-a stânga şi una de-a dreapta centrului lor comun.
Nu am găsit-o nicăieri. Mi-e şi jenă să spun de unde provine...  Am vrut să generez automat nişte poze cu neuroni. Şi mi-am pus problema cum construiesc automat un neuron arborescent "frumos" care duce la n sinapse poziţionate aleator prin spaţiu. Studiind eu poze de neuroni pe web, am observat că dintr-un trunchi gros se desprind ramuri mai subţiri, din care se desprind ramuri şi mai subţiri şi tot aşa. Am căutat un fenomen fizic care să semene cu aşa ceva şi mi-a venit ideea unui sat ale cărui case trebuie alimentate cu apă (aici am formulat cu aspersoare în grădină, dar iniţial aşa mă gândisem, cu case într-un sat). Condiţia cu sqrt(Q) provine din aceea că ceea ce plăteşti la conductă e metalul din care-i făcută -- deci proporţional cu perimetrul secţiunii, nu cu aria ei (dar debitul e proporţional cu aria). Cam asta-i geneza problemei...OK, acum, dacă tot v-am zis de unde provine... ar mai fi o restricţie: în fiecare "aspersor" ştim nu doar debitul, ci şi unghiul (direcţia) sub care trebuie să sosească apa. Iar conductele trebuie să aibă curburi cât mai line (nu bruşte). Şi conductele mai groase sunt mai puţin flexibile decât alea subţiri. Asta face ca traseele să nu mai fie linii drepte. Trunchiul principal va porni pe o anume direcţie din sursă şi se va curba greu ("încăpăţânat") înspre sinapse. Fiecare rămurică se va curba mai uşor. Şi ele se vor sfârşi în aşa fel încât să facă buton sinaptic frumos, perpendicular pe diverse suprafeţe date (care suprafeţe... aparţin unor neuroni deja construiţi, aţi ghicit! ).a PS: Iată, o imagine de genul ăsta aş vrea să generez:  Sau poate aşa:  Sau:   EDIT: Deci problema cea mai generală e: Dată fiind o rădăcină (ca versor: poziţie + direcţie) şi n frunze (tot ca versori: poziţie + direcţie), cum construim un arbore care să arate cât mai "organic", cât mai natural, cât mai frumos? Care să sugereze cât mai bine ideea că "ceva" este distribuit în mod economic la cele n frunze? Acest topic a fost editat de Amenhotep: 27 Jan 2006, 01:16 AM -------------------- Trebuie să facem ceea ce credem că e bine, dar nu trebuie să credem că ceea ce facem e bine.
|
||||||
|
|
|
||||||
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 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 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: 9 June 2024 - 02:12 PM |