|
1 Heurisztikak: |
|
2 |
|
3 gap: ha egy 0<i<n szint kiurul, az [i+1,n-1] szinten levoket felrakjuk az |
|
4 n szintre, ezzel nem sertve a tavolsagcimke tulajdonsagot |
|
5 |
|
6 highest label: a legnagyobb szintu aktivon pumpalunk (2 phase eseten |
|
7 persze az n alattiak kozul a legnagyobb szintun) |
|
8 |
|
9 bound_decrease: nem highest label. Egy b valtozoval lepegetunk lefele |
|
10 mig 0-hoz erunk, amikor megemeljuk n-ig (vagy k-ig ha |
|
11 az nyilvan volt tartva). Mindig egy b szintu aktivon |
|
12 pumpalunk (ha van ilyen, ha nem: --b). Relabel utan tehat |
|
13 nem megyunk a csucs utan, ot majd csak b ujboli felemelese utan |
|
14 tudjuk pumpalni. Meglepoen hatekony. |
|
15 |
|
16 highest label + bound_decrease: preflow.h-ban H0*n relabel-enkent a |
|
17 bound_decrease, mig H1*n relabel-enkent a highest label valtozatot |
|
18 futtatjuk az 1. fazisban (a masodik fazis igen gyors az elsohoz |
|
19 kepest, igy itt sima highest label fut). Ez igen hatekonynak |
|
20 tunik, ugy latszik, hogy egyesul a ket eljaras elonye. Teszteles |
|
21 alapjan a H0=20, H1=1 valasztas elfogadhatonak tunik. |
|
22 |
|
23 2 phase: az elso fazisban csak az [1,n-1] szintu aktivokon pumpalunk, |
|
24 es alkalmazzuk gap-et. Ha alul nincs aktiv, fentrol kifujjuk |
|
25 s-bol a fenti csucsokat a segedgraf egy vissza bfs-evel, es |
|
26 visszacsurgatunk ugyanugy, mint az elso fazisban. Az elso fazis |
|
27 utan az n. szint alatti csucsok egy min vagast adnak, es t |
|
28 excesse a max folyamertek. |
|
29 |
|
30 level_list: kezzel irunk egy listat minden szintre az ottani csucsokrol. |
|
31 Ha meg egy k valtozoban nyilvantartjuk a legnagyobb nemures |
|
32 szintet az [1,n] intervallumban, akkor nagyon gyorsan tudunk |
|
33 gap eseten a gap feletti csucsokat az n szintre tenni. Ilyenkor |
|
34 arra sincs szukseg (ami maskor igen hasznos), hogy nyilvantartsuk |
|
35 melyik szinten hany csucs van. |
|
36 |
|
37 |
|
38 A LEDA flowja |
|
39 |
|
40 max_flow.t tartalmazza a LEDA flowjait, a legutolso fuggveny, |
|
41 MAX_FLOW_T a default. Semmi kulonoset nem csinal, 2 fazisu highest label, |
|
42 gap eseten bfs-sel szivja fel a csucsokat az n szintre (ez igen rossz |
|
43 megoldas suru grafnal). Nyilvan tartja az aktivokat egy valamilyen stackben, |
|
44 es hogy melyik szinten hany pont van. 5*m lepesenkent (h=5 defaultbol) |
|
45 csinal egy bfs-t vagy t-bol (1. fazis) vagy s-bol (2. fazis). Van benne |
|
46 par rossz megoldas, pl. az elsorol a 2. fazisra valo atteresnel nem kell |
|
47 egy bfs a t-bol. |
|
48 |
|
49 |
|
50 |
|
51 Egy erdekes tapasztalat: |
|
52 |
|
53 Meglepo modon nagyon sokat gyorsitott amikor az stl stack-jet kezzel |
|
54 megirtam. Ez talan a G.id(NodeIt v) hatekonysaganak koszonheto. |
|
55 |