gurkjis Posted August 21, 2013 Report Share Posted August 21, 2013 Man javeido spēle, kurā šādi nosacījumi: * spēlētājam ir doti 12 burtu salikumi (vārdu daļas), katrs satur no 1 līdz 3 burtiem * līmenim fonā ir izrēķināts noteikts minimālais daudzums atbilstošo vārdu, no kuriem spēlētājs var kādu uzminēt * spēlei ir dota vārdu datubāze (~190 tūkstoši vārdu) * katru salikumu var izmantot vairāk kā vienu reizi, piem. vārdu banana var salikt no 2 daļām: "ba" un "na" Kā man randomā atrast šos burtu salikumus tā, lai no tiem būtu iespējams salikt minimalo noteikto daudzumu ar matching vārdiem ? Performance patreiz nav svarīga, vajag risinājumu, kas darbojas. Pēc tam varēs domāt, vai vajag un kā optimizēt. Vakar pačakarējos bez rezultātiem, bet nu šodien man patreiz tāda ideja: * ņemu random vārda daļu (atrod random vārdu, atrod random daļu no tā) 1. ņemam nākamo random daļu no cita vārda, pieliekam potenciālo daļu sarakstā 2. uztaisam permutāciju šim potenciālo daļu sarakstam, lai iegūtu visas daļu kombinācijas http://en.wikipedia.org/wiki/Permutation 3. čekojam cik pilnus matching vārdus atradām. Ja daži atrasti, tad vārda daļa vairs nav potenciāla, bet reāli lietojama, pievienojam lietojamo daļu sarakstā 4. ciklējam uz soli 1., līdz atrasts minimālais matching vārdu daudzums. Ja sasniegts 12 reālu daļu limits un matching vārdu skaits nav sasniegts, tad izmetam kādu no reālām daļām un tā vieta meklējam citu random daļu * kā nākamo random daļu atrast: ņemam kādu iespējamo daļu kombināciju no permutētā array, piem. "ba", "na", varam atrast visus vārdus,kas satur "bana" substringu un tad paņemt kādu no šiem vārdiem, skatīties,kāda daļa iet pa kreisi vai pa labi, piem: "labanana", pa kreisi: "la", pa labi: "na". Bet liekas, ka šāds algo varētu baigi ilgi ciklet līdz atradīs matching vārdus. Quote Link to comment Share on other sites More sharing options...
martins256 Posted August 21, 2013 Report Share Posted August 21, 2013 Varbūt var šādu risinājumu: 1. Tiek izveidots iespējamo zilbju (vārdu daļu) saraksts no tadas vārdu datubāzes. 2. Tiek apskatītas visas iespējamās 1-4 zilbju kombinācijas un tiek pārbaudīts vai no tām var iegūt kādu vārdu. Tiek iegūta datubāze ar zilbēm un to vārdu skaitu. 3. no zilbju datubāzes izvēlies 12 zilbes un izmantojot kopu teoriju noskaidro cik vārdus var izveidot. Šeit varētu jau izmantot tavu aprakstīto permutāciju variantu. Visas iespējamās kombinācijas nebūtu ieteicams apskatīt ;) Man ir tieši tagad pieejams hadoop skaitļošanas puduris. Varbūt vēlies uzrakstīt kādu Map-Reduce darbiņu? Quote Link to comment Share on other sites More sharing options...
codez Posted August 21, 2013 Report Share Posted August 21, 2013 (edited) Pirmais triviālais heurestiskais algoritms, kas nāk prātā ir: Uztaisam sarakstu ar visiem fragmentiem. Ja ir 26 burti, tad attiecīgi 26^3+26^2+26 = 18'278 varianti. Ejam cauri katram vārdam, ņemam no vārda visus iespējamos fragmentus un pieskaitam katram fragmentam +1, ja tas ir atrodams vārdā. Tādā veidā tiek iegūts, cik vārdos ir katrs fragments. Šis jāizdara vienu reizi - iegūst 18k fragmentus un vārdu skaitu, kuros tie ir. 1. Tālāk randomā izvēlas 12 fragmentus. 2. Iet cauri visiem vārdiem un saskaita, cik vārdus var salikt no šim 12 zilbēm. 3. Ja viss ok, tad beidz 4. Ja vārdu skaits ir par mazu, tad nomaina kādu fragmentu pret kādu ar lielāku piesaistīto vārdu skaitu. (Šī darbība viennozimīgi negarantē, ka vārdu skaits palielināsies, bet, jo lielāka bus starpība starp fragmenta piesaistito vārdu skaito, jo statistiski par lielāku vārdu skaitu palielināsies saliekamo vārdu skaits) 5. Ja vārdu skaits ir par lielu, tad nomaina kādu fragmentu pret kādu ar mazāku piesaistito vārdu skaitu. 6. Atgriežas 2. punktā. P.S. Pilnīgāku variantu varētu izveidot, būvējot no zilbēm un vārdiem grafu, bet 100% risinājums uzreiz nenāk prātā. Edited August 21, 2013 by codez Quote Link to comment Share on other sites More sharing options...
codez Posted August 21, 2013 Report Share Posted August 21, 2013 2. Tiek apskatītas visas iespējamās 1-4 zilbju kombinācijas un tiek pārbaudīts vai no tām var iegūt kādu vārdu. Tiek iegūta datubāze ar zilbēm un to vārdu skaitu. 18'278 ^ 4 = 1.1 * 10^17 Quote Link to comment Share on other sites More sharing options...
gurkjis Posted August 21, 2013 Author Report Share Posted August 21, 2013 ok, tagad jau ir vairākas idejas, ko varu pamēģināt. marrtins256 - kas ar mapreduce ? Ir dzirdēts par to, bet man risinājums vajadzīgs Javascriptā. Par graph - arī man bija par to aizdomas, skatījos uz http://en.wikipedia.org/wiki/Suffix_tree bet nu domāju ka kādu vienkāršāku bruteforce variantu varētu ātrāk ieimplementēt. Quote Link to comment Share on other sites More sharing options...
martins256 Posted August 21, 2013 Report Share Posted August 21, 2013 Codez, tev taisnība, ka man sanāk par daudz rēķināt. Varētu apskatīt, piemēram, tikai 1000 zilbes, kas tiek kombinētas pa 4. vai 10k zilbes pa 3. Šādi sanāktu 10e11. Quote Link to comment Share on other sites More sharing options...
codez Posted August 21, 2013 Report Share Posted August 21, 2013 (edited) Paildinot: Ja ir N vārdi un vidējais vārda garums G, tad šīs darbības algoritma sarežģītība ir: 2. Iet cauri visiem vārdiem un saskaita, cik vārdus var salikt no šim 12 zilbēm. O(N*G) - respektīvi ejam cauri katram vārdam un katram burtam. Tā kā tas būs jādara vairākas reizes, bet meklēšana būs kaut kas lidzigs binārajai meklēšanai staro 0 vārdiem un max vārdu skaitu, tad algoritmu var uzbūvēt O(logN) Tātad kopā O(N*G*logN) Pat rakstot C, šis algoritms šķietami var aizņemt pāris sekundes, kas priekš spēlītes algoritma būtu par lēnu, tāpēc vajag izdomāt kā optimizēt O(N*G) daļu. Tam izmanto šādu datu strukturu: http://en.wikipedia.org/wiki/Trie Tā tiek izveidota no visiem vārdiem un katra šķautne ir burts, bet virsotne ir kopējais vārdu skaits, kurš ir izveidojams ejot cauri no saknes līdz šij vietai. Max koka izmērs O(N*G), taču apskatot to ar 12 iespējamiem fragmentiem, apskatīto koka zaru daudzums būs daudz, daudz mazāks. P.S. Trie ds jābuvē tikai vienu reizi un var vienmēr tikt izmantota jau gatava. man risinājums vajadzīgs Javascriptā.Ja tā, tad īsti pirms tam sagatavots Trie ari nederēs, jo diezgan paliels, lai sutītu klientam, bet tādā gadijumā ari 190k vārdu datubāze ir paliela, lai to sutītu klientam. Vai ari tomēr risinājums būs backendā un klients to varēs parasīt? Edited August 21, 2013 by codez Quote Link to comment Share on other sites More sharing options...
gurkjis Posted August 21, 2013 Author Report Share Posted August 21, 2013 (edited) Varu arī backend sataisīt un tad tikai rezultējošos fragmentus + word list nosūtu. Skatīšos kā labāk. Sanāca sataisīt risinājumu, kas spēles max 30 matching vārdus atrod vidēji 1-2 sekunžu laikā. Visvairāk iespaidojos no codez pirmā varianta. Pamatdoma, ka tiek izmantoti visbiežāk lietotie fragmenti ar visvairāk vārdiem datubāzē, tādējādi palielinot iespēju, ka tiks atrasta atbilstoša kombinācija. * visus vārdus sadalu pa fragmentiem un saskaitu, cik vārdi izmanto katru fragmentu, sasortēju šo listi - biežāk lietotie fragmenti -> retāk lietotie * iegūstu 12 random fragmentus (izvēlos tikai no top100 biežāk lietotajiem fragmentiem) * iegūstu visus vārdus, kurus var uzkonstruēt no šiem 12 fragmentiem * ja vārdu skaits atbilst minimālajam prasītajam, tad beidzam * ja nē, tad iegūstu piesaistīto vārdu skaitu katram no šiem 12 fragmentiem * izdzēšu to, kuram vismazāk vārdi piesaistīti. Ja 0 vārdi, tad tikai fragmentu dzēšam ārā, ja > 0, tad gan fragmentu, gan visus piesaistītos vārdus * pievienoju jaunu fragmentu, kas tiek ņemts no biežāk lietoto fragmentu saraksta augšgala * šādi, pa vienam dzēšam un pa vienam pievienojam, līdz ir vajadzīgais vārdu skaits atrasts ------- teorētiski, algo var iebraukt bezgalīgajā loopā, bet pagaidām, testējot, neesmu tam uzdūries. Jāizveido automātisks tests, kas nonstopā testē, ja būs problēma tad redzēšu. source: http://pastebin.com/x5XEdZJP Edited August 22, 2013 by gurkjis Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.