Programozás

[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

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]

Update: mialatt írtam a cikket, észrevettem egy dolgot, amit beletettem a progiba
Az új eredmény (csak a kritikus rész):

99,200% 393 415 463
99,300% 402 423 444
99,400% 430 450 474
99,500% 444 462 471
99,600% 440 459 471
99,700% 432 442 456
99,800% 399 420 438

Egyértelmű a javulás, lám egyetlen integerrel mi mindent lehet tenni... (A becslés szerint a javulás mértéke a tábla méretével arányos)

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

[Kutyuleee]

egy forráskódot nekem is küldenél??? elsőre én is hasonló algoritmusban gondolkodtam csak nem volt időm még foglalkozni vele.

Még annyi a kérdés, hogy az eredeti feladatban használható-e rekurzió vagy nem?

[Dus]

Originally Posted by Cpt Balu

(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)

Elvileg nincs, és img tagek jól működnek. Legalábbis eddig jól működtek. Nem lehet, hogy inkább a külső linkelés van letiltva annál az oldalaknál, ahonnan behúztad a képet? Mert olyat szoktak. Bár képmegosztó oldalaknál nem, de pl. az ingyenes tárhelyszolgáltatók ezt csinálják, hogy ne használd a tárhelyüket "háttértárolónak" egy másik oldalhoz.