Hódító / Queosia forum
Hódító / Queosia forum
http://queosia.com
http://hodito.hu

Go Back   Hódító / Queosia forum > Hódító / Queosia forum > Általános beszélgetések > PC (hardver, szoftver, játékok stb.)

PC (hardver, szoftver, játékok stb.) Minden, ami számítógép. Kedvenc játékod megbeszélése, segítségkérés hardverügyben stb.

 
 
Thread Tools Search this Thread Display Modes
Prev Previous Post   Next Post Next
  #20  
Old 11-11-2011, 16:38
Cpt Balu Cpt Balu is offline
Junior Member
 
Join Date: Mar 2011
Posts: 47
Activity: 0%
Longevity: 73%
Default

Quote:
Originally Posted by Dus View Post
É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...
Reply With Quote
The Following User Says Thank You to Cpt Balu For This Useful Post:
 


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +1. The time now is 19:16.


Powered by vBulletin®
Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
Design partly based on Hódító's design by Grafinet Team Kft.

Contents and games copyright (c) 1999-2020 - Queosia, Hódító

Partnerek: Játékok, civ.hu