Da li je neko imao prilike da pretvori randomized min cut algoritam u code za kompjuter?
20.07.2005. u 17:20 · pre 258 meseci
#1
Trebao bih da pocnem ovih dana da radim na tome samo se jos nisam odlucio kako da ga pisem da li ima jezik koje ima prednosti u odnosu na druge za resavanje ovakvih problema?
Ko nije upucen o cemu je rec evo krace objasnjenje koje moze da se nadje i na netu:
Algorithm Contract (D. Karger, 1993)
Input: A multigraph G(V, E)
Output: A cut C
1. H <- G
2. while H has more than 2 vertices do:
2.1 choose an edge (x, y) uniformly at random from the edges in H.
2.2 F <- F U {(x , y)}
2.3 H <- H / (x, y)
3. (C, C') <- the sets of vertices corresponding to the two meta-vertices in H = G/F
Svaki savet ili ako vec imate neki postojeci primer je dobrodosao...
Hvala unapred
Ko nije upucen o cemu je rec evo krace objasnjenje koje moze da se nadje i na netu:
Citat:
Algorithm Contract (D. Karger, 1993)
Input: A multigraph G(V, E)
Output: A cut C
1. H <- G
2. while H has more than 2 vertices do:
2.1 choose an edge (x, y) uniformly at random from the edges in H.
2.2 F <- F U {(x , y)}
2.3 H <- H / (x, y)
3. (C, C') <- the sets of vertices corresponding to the two meta-vertices in H = G/F
Svaki savet ili ako vec imate neki postojeci primer je dobrodosao...
Hvala unapred