| [142] | 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 | |
|---|
