Programozás

[Dus]

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

[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ű

[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

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...

Milyen nyelven írtad? Ha C,C++,Java vagy Pascal akkor e-mail-ben küldd már el a forráskódot, mert van itt jóhényán forrásom, aztán megnézem, és azt is, hogy helyes-e

[Cpt Balu]

Originally Posted by Redback

Milyen nyelven írtad? Ha C,C++,Java vagy Pascal akkor e-mail-ben küldd már el a forráskódot, mert van itt jóhényán forrásom, aztán megnézem, és azt is, hogy helyes-e

C#...
De sok programnyelvre át tudom írni, java, c++, delphi, pascal, asm, php amit akarsz.

Közben megálmodtam mégegy algoritmust, ami nem brute-force, csak sajna elég nehéz optimalizálni. Sajna képek nélkül elég nehéz lenne elmagyarázni, majd kitalálok valamit, addig is elküldtem a progit, az egyszerűség kedvéért 500x500-as képre korlátoztam, de bármekkora területen működik (1000x1000-nél sem nagyon ment 4-5sec fölé)
Itt egy táblázat 500x500-ra, hogy adott telítettség mellett milyen futási idők jöttek ki. Az oszlopok:
1. Telítettség: az a valószínűség, amivel a terület fel lett töltve, tehát nem a pontos területarány, ettől lehet kis eltérés
2. Minimális futási idő
4. Átlagos futási idő
3. Maximális futási idő
(adott valószínűséggel legenerált 100 egyedi térképen való futtatás alapján)

A 3 érték mindegyike millisec, jól látható, hogy kis telítettségnél (1-esek aránya <95%) a sok 0 elszórva a térképen megakadályozza, hogy nagy eredmény jöhessen létre, a kicsi lehetőségek vizsgálata hamar megtörténik [a futási idő O(n^3) közelítésű], valamint nagyon nagy telítettségnél (csak néhány 0 található) a kevés variáció vizsgálata tart rövid ideig (pontosabban, mivel nagyon nagy eredmények hamar születhetnek, sok vizsgálatot el tudunk dobni):

10,000% 17 21 31
20,000% 21 28 50
30,000% 24 30 35
40,000% 32 38 60
50,000% 35 37 41
60,000% 37 41 49
70,000% 42 47 63
80,000% 50 56 74
90,000% 73 79 93
91,000% 80 85 98
92,000% 78 87 109
93,000% 89 99 117
94,000% 106 110 130
95,000% 115 126 145
96,000% 138 146 164
97,000% 170 178 196
98,000% 242 255 274
99,000% 369 391 433
99,100% 388 411 434
99,200% 416 436 520
99,300% 457 518 648
99,400% 481 548 617
99,500% 503 582 798
99,600% 501 567 615
99,700% 518 589 649
99,800% 441 490 662
99,900% 314 395 456
99,910% 298 334 429
99,920% 276 307 336
99,930% 256 296 406
99,940% 231 269 327
99,950% 198 211 225
99,960% 162 204 271
99,970% 133 151 194
99,980% 115 126 160
99,990% 85 104 130
99,991% 78 91 111
99,992% 70 92 124
99,993% 61 69 93
99,994% 54 70 113
99,995% 53 66 90
99,996% 41 54 84
99,997% 40 47 71
99,998% 24 29 36
99,999% 18 26 43

A keresés bizonyíthatóan a legjobb eredményt hozza ki.

[Cpt Balu]

készítettem egy oldalt ahol leírtam az új algoritmus elvi fejtegetését (sajna itt nem működtek a képek, azok nélkül esélytelen megérteni):
users.atw.hu/cptbalu
ide fogom írni a jelenlegi progi működését is.

(ps: ha moderátoroknak kifogásuk van linkelés miatt, várnék javaslatot hogy tudnám megoldani a képes postokat, img tagek behozták a képeket oszt el is tüntették rögtön, gondolom tiltva van külső hivatkozás bbc-ben)