Csapófa algoritmus

Szeretek kitalálni dolgokat.....

(Tegnapelőtt láttam az egyik kedvenc ötletemet kivitelezve.... A Cargónak dolgoztam néhány éve és egyik reggel autóval befelé menet hallgattam egy riportot a mentősökről, tűzoltókról, mozdonyvezetőkről, ütközésekről. Különösen az ütött szöget a fejembe hogy a galád "késsen el mindenki ma, mert úgy döntöttem hogy megküzdök a mozdonnyal" versenyző még integetett is a mozdonyvezetőnek, aki persze nem tudott megállni... Nosza, szereljünk légzsákot a mozdonyra. Az egyik mozdonyvezető meg is  ütközött ezen? Minek légzsák? Ja? Kívülre? Na szóval másoknak is járt ezen az agya és kísérletképpen szereltek is fel egyet, igaz ők autóval ütköztették.....) 

Ritkán adódik meg az hogy  nem csak a magam szórakoztatására ötlök ki valamit, hanem parancsszóra kell ezt megtenni.

Amikor másodjára a MÁV-hoz kerültem (még a múlt évezredben, 1995-ben vala ez), rögtön belecsöppentem egy érdekes, igaz félig külsős projektbe. Ma már nincsen olyan megkötés amivel akkor szembe kellett néznünk, de két számlán kellett keresztül menjen szinte minden utalás, mivel az önelszámoló egységek külön könyveltek, a tetejébe eléggé sztochasztikusan voltak elosztva a bankok az egységek között. 

Itt csinálj te egyszerűen cash pool technikát :). 

Adva volt a feladat, hogy az utalásokat úgy kell csoportosítani, hogy a sorrendiség maradjon, de úgy történjenek meg a kifizetések, hogy lehetőleg ne legyen az ellátmány adásnál bankközi átutalás.

Te vagy a matematikus, ez a te dolgod :D.

Szimplex algoritmus, Gomory módszer, tanultam én ezt, ráhúzzuk a feladatra és kész.

No de nem tudtam ráhúzni. Egyre többet gondolkoztam a dolgon, egyre kevéssé éreztem hogy haladnék előre. "Idő telik, becsület fogy", édesapám kedvenc mondása, és ebben az esetben ez sajna erősen aktuális volt... 

Volt persze más dolgom is, a rendszerrel kapcsolatosan egyébként is, a napi munka is, meg iskolába is jártam épp, no meg a Autóklubos programmal is törődni kellett... De egyre több erőforrást allokáltam erre a feladatra, lassan olyan voltam mint egy alvajáró. Remélem nem motyogtam :).

Ami ebből érdekes, az az amikor a tudatalattim "átadta" az eredményt. Liftben mentem felfelé a BEIG-ben amikor is beugrott. Egyszerűen tudtam hogy megvan a megoldás, és jó is. Azt az eufórikus érzést kívánom hogy próbálja ki mindenki :D. 

Persze azért miközben leprogramoztam, néha elkapott a kétely, amivel Csabit a sírba kergettem. Időnként felkiáltottam hogy nem jó az egész, majd néhány perc múlva azt hogy de, mégiscsak.... 

Elmagyarázni akkor még végképp nem tudtam, pedig roppant egyszerű az egész.

A probléma ugye az volt, hogy meghatározott sorrendben kellett kielégíteni az igényeket amelyek feljöttek a központba - ez is érdekes egyébként, mert nem nagyon csináltak addig olyat az országban amit mi míveltünk, kettős privát kulcsos auth, és egyéb nyalánkságok, arról nem is beszélve hogy 3 pénzügyi rendszert szolgáltunk ki úgy hogy nem állt egy napot se az egész 10 év alatt, ami nem kis szó - és úgy elosztani őket hogy lehetőleg a telephelyek saját bankszámláin keresztül "folyjon' a pénz.

Az ötlet a következő volt:

• Először nézzük meg hogy mennyi pénz van összesen.

• Aztán első körben addig menjünk sorrendben a tételeken, ameddig el nem érjük, illetve meghaladjuk ezt az összeget, és mindegyik számlához "írjuk" hozzá ezt, ahol ösvény van. Ez lesz majd a "csapófa".

• A második körben ugyanezt tesszük, csak ekkor az összes ösvényhez tartozó lehetőséget levonjuk, és kiválasztjuk azt az egyet, ahol a csapófa a legközelebb van a kupac tetejéhez.

Később persze nem értettem hogy ezen miért gondolkodtam annyi ideig :D.

Ábrákban vázolva (az akkori banknevekkel ;-), de nem volt odaírva mind egyébként se....):

Az első menet már lefutott, ennek hatását a színes téglalapok elhelyezkedéséből láthatjuk. Az éppen utalható pénz nagyságát a lila négyzetek mutatják.

 Az osztható pénz a DAEWOO banknál csökkent ( a fehér téglalap).

 A szürke téglalapok az ideutalt - osztható pénz nagyságát mutatják.

 A választás mindíg a kisebb szám alapján történik.

 Egyenlőség esetén az osztható pénz nagysága dönt.

 Ez érvényes a pénz elfogyása esetén is ( a nullánál minden nagyobb...).

 A zöld és világoskék téglalapokkal jelölt utalások az MHB-n keresztül mennek el, egy tétel kimarad.

Ennyi :D.

A nüanszokra  nem térek ki nyilván, az messze vezetne, például alkalmazható ez a módszer dinamikusan is, gubancot okoz ha nagyok az eltérések az összegek között, etcetera, etcetera...

Hátha valakit inspirál ez, szerintem nem csak erre a feladatra jó, pláne hogy az eredeti feladat már nem is létezik. Integrált rendszernél nem érdekes a telepi utalás például.....