Programozás

[Redback]

adott egy m*n-es tomb. minden eleme csak 1 vagy 0 lehet. Az 1 jelenti a feketet, 0 a feheret. Hogyan lehet megkeresni leggyorsabban a legnagyobb csak feher (0) mezoket tartalmazó téglalapot? Én úgy gondolkoztam, hogy minden mezőhöz hozzárendeltem egy számot, mégpedig hogy a terület bal felső sarkával alkotott téglalapban hány fekete mező van. Ekkor bármely téglalapban lévő fekete mezők meghatározhatóak mindenféle ciklus nélkül. Ezután meghatározom a terület "területét" (m*n).Mindig csökkentem eggyel a terület értékét, és megkeresem mekkora téglalapoknak annyi a területe, aztán megnézem hogy az eredeti területben belefér-e magassága és szélessége, ha igen, akkor végignézem az összes olyan téglalapot az eredeti területben, és ha csak fehér mezők vannak benne, akkor győzelem. De ez túl lassú 500*500-ra 60 mp alatt kéne lefutni, de csak 3-4 perc alatt fut le

[Redback]

A lényeg lemaradt, szóval aki tud segíteni, akár csak sejtése van, szívesen fogadom

[Cpt Balu]

Mekkora területeket kell keresni? kész van egy algoritmus, mindjárt közlöm az eredményeket...

[Dus]

Én kíváncsi lennék erre az algoritmusra, ha szabad. Érdekelne, mert agyaltam rajta, de nem sok sikerrel.

[Cpt Balu]

Originally Posted by Dus

Én kíváncsi lennék erre az algoritmusra, ha szabad. Érdekelne, mert agyaltam rajta, de nem sok sikerrel.

Addig leírom a jelenlegi algoritmus lényegét:
Elindulok a tábla elején, szépen sorfolytonosan haladok. Ha találok egy aktív területet (1) akkor van legalább egy 1x1-es megoldás.

Ezután megnézem, hogy adott irányban (mondjuk X mentén, tehát vízszintesen) meddig találok aktív területet, legyen ez X, utána másik irányban Y. Így tehát van lehetőségem egy maximum X*Y eredményre. Ezt összehasonlítom a korábbi eltárolt legjobb eredménnyel (ha van). Ha az eredményem nagyobb, fölösleges tovább vizsgálni, nem lesz belőle új eredmény. Ezután esetleg végzek még gyorsteszteket (átellenes sarok, oldalak ellenőrzése), amik érvényteleníthetik a jelenlegi keresést, és a legvégén csinálok teljes vizsgálatot (vagyis hogy teljes-e a téglalapom), mivel ez az legidőigényesebb munka. Ha stimmel, és a téglalap nagyobb mint az eddigiek, akkor végeredményként eltárolom, és legközelebb már csak az ennél nagyobb esélyesek vizsgálata történik meg, ami jelentősen csökkenti a futási időt.
Sok helyen lehet ignore feltételeket alkalmazni, pl. ha van egy 10x10-e eredményem, akkor a 491. sor 491. oszlopnál legjobb esetben egy másik 10x10-est találhatok, az ez utáni oszlopokban meg sokkal kisebbeket, ilyenkor ki lehet hagyni a keresést, és következő sorral folytatni (ahol már az utolsó 11 oszlop elhagyható, mivel az is csak 11x9=99 lehetne)

Egyenes rekurzió helyett ajánlott while ciklusokat használni stack műveletek spórolása miatt, sokszor nagyságrendekkel gyorsabb lehet a progi.

Ez a módszer hasonló a tiédhez, vagyis végignézem a táblát, kiszedek belőle max méretű téglalapokat, és feljegyzem a legjobbat, a többi nagy részét pedig keresés előtt is el tudom vetni. De akad más megközelítés is, a reklám után folytatom...

[Redback]

Originally Posted by Cpt Balu

Addig leírom a jelenlegi algoritmus lényegét:
Elindulok a tábla elején, szépen sorfolytonosan haladok. Ha találok egy aktív területet (1) akkor van legalább egy 1x1-es megoldás.

Ezután megnézem, hogy adott irányban (mondjuk X mentén, tehát vízszintesen) meddig találok aktív területet, legyen ez X, utána másik irányban Y. Így tehát van lehetőségem egy maximum X*Y eredményre. Ezt összehasonlítom a korábbi eltárolt legjobb eredménnyel (ha van). Ha az eredményem nagyobb, fölösleges tovább vizsgálni, nem lesz belőle új eredmény. Ezután esetleg végzek még gyorsteszteket (átellenes sarok, oldalak ellenőrzése), amik érvényteleníthetik a jelenlegi keresést, és a legvégén csinálok teljes vizsgálatot (vagyis hogy teljes-e a téglalapom), mivel ez az legidőigényesebb munka. Ha stimmel, és a téglalap nagyobb mint az eddigiek, akkor végeredményként eltárolom, és legközelebb már csak az ennél nagyobb esélyesek vizsgálata történik meg, ami jelentősen csökkenti a futási időt.
Sok helyen lehet ignore feltételeket alkalmazni, pl. ha van egy 10x10-e eredményem, akkor a 491. sor 491. oszlopnál legjobb esetben egy másik 10x10-est találhatok, az ez utáni oszlopokban meg sokkal kisebbeket, ilyenkor ki lehet hagyni a keresést, és következő sorral folytatni (ahol már az utolsó 11 oszlop elhagyható, mivel az is csak 11x9=99 lehetne)

Egyenes rekurzió helyett ajánlott while ciklusokat használni stack műveletek spórolása miatt, sokszor nagyságrendekkel gyorsabb lehet a progi.

Ez a módszer hasonló a tiédhez, vagyis végignézem a táblát, kiszedek belőle max méretű téglalapokat, és feljegyzem a legjobbat, a többi nagy részét pedig keresés előtt is el tudom vetni. De akad más megközelítés is, a reklám után folytatom...

A megírt programodra kíváncsi vagyok, tesztelnék egy párat

[Cpt Balu]

Originally Posted by Redback

A megírt programodra kíváncsi vagyok, tesztelnék egy párat

Nos, a legtisztább az lenne, ha generálnál néhány alakzatot, megmondanád mennyi idő alatt keresel, és ugyanazt megpróbálom én is megtalálni keveseb idő alatt.

Elkészült a program, még próbálom értelmezni, mit is találtam ki És érthetően beszámolni róla, röviden annyit a teljesítményről, hogy vegyes sűrűségű próbákkal nem tudtam 400ms fölé(!) menni Remélem ez már megteszi, ha érdekel a progi, esetleg elkészíthetem egy kis alkalmazással, mondjuk bittérkép rajzolóval, elkészíted az ábrát, és ráereszted a keresőt...

[Redback]

Originally Posted by Cpt Balu

Mekkora területeket kell keresni? kész van egy algoritmus, mindjárt közlöm az eredményeket...

A legnagyobb területet keressük Kíváncsi lennénk az algoritmusra

[Cpt Balu]

Originally Posted by Redback

A legnagyobb területet keressük Kíváncsi lennénk az algoritmusra

Úgy értem h a várható legnagyobb terület mekkora? majdnem az egészet befedi, vagy ritább területen keresünk? mert van jó algoritmus arra, ha mondjuk 50x50 körüli eredményeket várunk vagy kisebbet (akkor az átlag futási idő olyan 500ms körüli), de nagy eredményeknél nem valami gyors, egy másik pedig pont a nagy eredményeket találja meg hamar, de ha ritkább a kitöltöttség az sok fölösleges kört futtat vele
Viszont most eszembe jutott még valami, máris kipróbálom...
Egyébként egy 15x15-ös területet most átlag 90msec alatt találok meg Sztem ez jó eredmény lesz

[Redback]

Originally Posted by Cpt Balu

Úgy értem h a várható legnagyobb terület mekkora? majdnem az egészet befedi, vagy ritább területen keresünk? mert van jó algoritmus arra, ha mondjuk 50x50 körüli eredményeket várunk vagy kisebbet (akkor az átlag futási idő olyan 500ms körüli), de nagy eredményeknél nem valami gyors, egy másik pedig pont a nagy eredményeket találja meg hamar, de ha ritkább a kitöltöttség az sok fölösleges kört futtat vele
Viszont most eszembe jutott még valami, máris kipróbálom...
Egyébként egy 15x15-ös területet most átlag 90msec alatt találok meg Sztem ez jó eredmény lesz

bármekkora lehet a legnagyobb, akár 1 területű, akár 25000 területű