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