Pagini: [1] 2 3   În jos
  Imprimă  
Ajutor Subiect: 026 Arbore partial de cost minim  (Citit de 25721 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
filipb
Nu mai tace
*****

Karma: 232
Deconectat Deconectat

Mesaje: 929



Vezi Profilul
« : Decembrie 24, 2008, 12:02:31 »

Aici puteti discuta despre problema Arbore partial de cost minim.
Memorat
philip
Strain
*

Karma: 5
Deconectat Deconectat

Mesaje: 39



Vezi Profilul
« Răspunde #1 : Martie 01, 2009, 09:15:28 »

Cum mai pot optimiza sursa asta http://infoarena.ro/job_detail/268348?action=view-source ?
Asta e algoritmul lui Kruskal, nu?

(E in pascal.)
Memorat
alexthero
De-al casei
***

Karma: 121
Deconectat Deconectat

Mesaje: 129



Vezi Profilul
« Răspunde #2 : Martie 01, 2009, 10:52:21 »

Salut,

In primul rand poti optimiza sortarea. Ce faci tu acolo are complexitate N^2 si poti face o sortare in N*LogN. Iti recomand sa rezolvi problema Sortare prin comparare prima data. O poti gasi aici: http://infoarena.ro/problema/algsort. Algoritmii cei mai buni (pentru implementat de mana) sunt mergeSort si heapSort. QuickSort e si el ok, dar are worst case N^2. Pentru a rezolva aceasta problema a QuickSort, in practica se foloseste un pivot random (cand alegi pivotul alegi unul aleator din sirul tau, si nu un element fix - de obicei primul).
Apoi in procedura minim, tu faci iarasi N^2. Aici se poate face N*Sigma. Sigma e foarte mic (aproximativ 5), deci poate fi aproximat la O(1). O explicatie a acestui Sigma o gasesti si pe Wiki, Sigma reprezentand inversa functiei Ackerman pentru n,n. Iti recomand sa rezolvi prima data: http://infoarena.ro/problema/disjoint
Memorat

Tine minte ca mintea conduce pumnu, nu invers
nparfene2004
Client obisnuit
**

Karma: 22
Deconectat Deconectat

Mesaje: 81



Vezi Profilul
« Răspunde #3 : Ianuarie 31, 2010, 22:14:33 »

Buna seara tuturor!
As vrea sa va intreb daca algoritmul lui Kruskal e bun si pentru determinarea unui ciclu de cost minim intr-un graf (adaugand o muchie in plus), considerand ca toate costurile sunt pozitive.
Memorat
ionutz32
Strain


Karma: 16
Deconectat Deconectat

Mesaje: 18



Vezi Profilul
« Răspunde #4 : Ianuarie 31, 2010, 23:29:53 »

Daca vrei sa gasesti ciclul de cost minim prin parcurgerea muchiilor in ordinea crescatoare a costului, selectand mereu muchiile pana cand se formeaza un ciclu, nu o sa mearga.
Imagineaza-ti un graf de genul:

Cod:
7 8
1 2 4
1 4 4
2 3 4
2 5 10
3 4 4
5 6 5
5 7 5
6 7 5

Prin parcurgerea muchiilor sortate, primul ciclu care se formeaza e cel alcatuit din arcele 1-2, 2-3, 3-4, 4-1, care are costul 16, iar ciclul de cost minim e format din muchiile 5-6, 6-7, 7-5 si are costul 15.
Memorat
nparfene2004
Client obisnuit
**

Karma: 22
Deconectat Deconectat

Mesaje: 81



Vezi Profilul
« Răspunde #5 : Februarie 01, 2010, 16:17:07 »

Nu am vrut sa spun ca adaug chiar prima muchie care formeaza ciclu, ci le verific pe toate care formeaza vreun ciclu. Obtin ciclul de cost minim?
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #6 : Februarie 01, 2010, 16:34:52 »

Nu poti obtine ciclul de cost minim folosind Kruskal.

Contraexemplu:

Cod:
5 6
1 2 5
2 3 5
3 4 5
4 5 5
1 4 6
1 5 6
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #7 : Februarie 01, 2010, 17:47:59 »

Wefgef, cred ca el de fapt se referea ca foloseste kruskalu ca sa construiasca arborele partial de cost minim si apoi lua pe rand fiecare muchie care nu e in arbore si se uita la ciclul facut de aceasta. Chiar si asa nu este corect pentru ca ciclul de cost minim ar putea folosi 2 muchii care nu fac parte din arborele partial de cost minim.
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #8 : Februarie 01, 2010, 18:06:08 »

Pai asta intelesesem si eu Raised eyebrow. Algoritmul explicat in detaliu de tine pica pe contraexemplu.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #9 : Februarie 01, 2010, 19:28:49 »

Da ai dreptate. Nu stiu de ce aveam impresia ca ciclu minim e 1-2-3-4-1. Nu vazusem ca ciclul 1-4-5 e mai mic :-"
Memorat
nparfene2004
Client obisnuit
**

Karma: 22
Deconectat Deconectat

Mesaje: 81



Vezi Profilul
« Răspunde #10 : Februarie 02, 2010, 13:49:05 »

Multumesc pentru ajutor! Am inteles acum.
Totusi cum se obtine ciclul (elementar, evident) de cost minim? E vreun algoritm cunoscut?
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #11 : Februarie 02, 2010, 14:54:55 »

Poti calcula cu Dijkstra cele mai mici doua distante intre oricare doua noduri din graf. Apoi iei fiecare muchie in considerare si aduni distanta corespunzatoare (cea mai mica sau a doua).
Memorat

Am zis Mr. Green
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #12 : Februarie 02, 2010, 16:07:05 »

De fapt se poate si mai simplu. Vei presupune pe rand fiecare nod A din graf ca face parte din ciclul de cost minim. Vei face dijkstra pornind din nodul A. Apoi iei fiecare muchie (B, C) si verifici daca dmin(A, B) + dmin(A, C) < ciclul curent.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #13 : Februarie 05, 2010, 19:59:20 »

Am rescris sursa de 3 ori si tot nu-mi dau seama unde gresesc, pic pe penultimul test. Imi puteti spune unde gresesc, va rog ?
http://infoarena.ro/job_detail/391510?action=view-source ( Prim - folosind Heap-uri )
LE: rezolvat Smile
« Ultima modificare: Februarie 06, 2010, 13:09:06 de către alexandru » Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #14 : Februarie 10, 2010, 19:14:03 »

Ce era? M-am uitat pe sursa ta, dar n-am vazut nimic suspect.
Memorat

Am zis Mr. Green
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #15 : Februarie 10, 2010, 19:33:11 »

Ce era? M-am uitat pe sursa ta, dar n-am vazut nimic suspect.
Initial eu nu introduceam in heap nodul de start ci toate nodurile adiacente cu acesta si se pare ca de aici se tragea greseala.
« Ultima modificare: Februarie 10, 2010, 19:46:55 de către alexandru » Memorat
R.A.R
Strain
*

Karma: -7
Deconectat Deconectat

Mesaje: 37



Vezi Profilul
« Răspunde #16 : Septembrie 05, 2010, 11:21:45 »

Salut ! Am incercat sa rezolv problema insa nu imi dau seama ce gresesc . Folosesc o coada cu prioritati in loc de Heap.Daca ma puteti ajuta : http://infoarena.ro/job_detail/482809?action=view-source
Memorat
vladii
Echipa infoarena
De-al casei
*****

Karma: 32
Deconectat Deconectat

Mesaje: 141



Vezi Profilul
« Răspunde #17 : Septembrie 05, 2010, 12:47:15 »

E ok ideea, insa cred ca gresesti ceva pe la coada de prioritati. Am implementat aceeasi sursa, dar in loc de coada am folosit multiset (pe post de heap) si imi dadea ok.

Oricum, am luat 100 cu sursa ta facind mici modificari (si pastrind priority_queue`ul). Uite aici: http://infoarena.ro/job_detail/482815?action=view-source ! Poate te ajuta cu ceva.
Nu stiu insa ce greseai tu in sursa ta (probabil ca la functia cmp, insa nu stiu sa rezolv).

Bafta!
Vlad.
Memorat
R.A.R
Strain
*

Karma: -7
Deconectat Deconectat

Mesaje: 37



Vezi Profilul
« Răspunde #18 : Septembrie 05, 2010, 13:16:33 »

Este ciudat pt la algoritmul lui Dijkstra am implementat coada in acelasi fel si am luat 100.
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #19 : Octombrie 28, 2010, 20:23:45 »

Am implementat algoritmul lui Prim dupa solutia oficiala. Diferenta dintre 90 de puncte si 100 a fost o mica modificare in procedura downheap (push parca era in cea oficiala). Mai exact, daca cel mai mic dintre fii era egal cu nodul curent nu le mai interschimba pentru ca (dupa parerea mea) nu avea rost. ( if(D[H[son]]>=D[H[k]]) , acum e doar >). Am gasit aceasta "corectura" doar din noroc. Puteti sa-mi dati un exemplu pentru care ar face vreo diferenta?

Sursa: http://infoarena.ro/job_detail/496180?action=view-source
Memorat
david_rauca
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 3



Vezi Profilul
« Răspunde #20 : Ianuarie 21, 2011, 21:45:30 »

Nu mi se evalueaza sursa! :-W
Memorat
niovan
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 7



Vezi Profilul
« Răspunde #21 : Februarie 02, 2011, 20:43:26 »

salut! Care am puteti ajuta si pe mine? La implementare am folosit heapuri si multimi disjuncte. Nu stiu care ar fi problema dar nu iau decat 10p si din cate am citit, problema astfel implementata ar trebui sa ia un punctaj bun. Va sunt recunoscator celor care ma ajutati, mai ales ca am ajuns sa-mi smulg firele albe din cap Brick wall...nu gasesc "buba".

Am atasat la mesaj si sursa mea in format txt.
Memorat
gabitzish1
Moderatori infoarena
Nu mai tace
*****

Karma: 321
Deconectat Deconectat

Mesaje: 926



Vezi Profilul
« Răspunde #22 : Februarie 02, 2011, 21:47:59 »

Accesul la testele problemei este liber. Testele 1 si 2 sunt destul de mici ca sa faci debug pe ele.
Testul 1 il treci, vezi ce are testul 2 - poate aia e "buba" cautata.
Memorat
niovan
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 7



Vezi Profilul
« Răspunde #23 : Februarie 02, 2011, 23:25:08 »

merci gabitzish1! am descoperit asa numita "buba". eu cand uneam arborii din neatentie nu uneam radacinile ci un element dintr-un arbore cu un element din celalalt si evident se "rupeau". merci inca o data:D(ps: chiar uitasem de faptul ca testele sunt vizibile la arhiva educationala....what a bummer)
Memorat
Bit_Master
Vorbaret
****

Karma: -49
Deconectat Deconectat

Mesaje: 159



Vezi Profilul
« Răspunde #24 : Martie 18, 2011, 15:00:07 »

Se poate face si arbore partial de cost maxim tot asa? (de ex la Kruskal sortezi descrescator in loc de crescator)
Memorat
Pagini: [1] 2 3   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines