„Boogle“ generatoriaus algoritmas

Neseniai susidūriau su įdomiu „Boogle“ sprendimo algoritmo uždaviniu. Nors esu susipažinęs su jos sprendimo būdais, dabar norėčiau sukurti gerą „Boogle“ lentos generatorių ir ieškoti efektyvaus algoritmo.
Pirmieji du žingsniai yra paprasti:

 1) Boogle board is 5x5, so I will have an array of 25 chars. Randomly generate an array of 25 chars. 2) Shuffle the array obtained in the step 1 

Kas toliau? Turiu optimizuoti gautą masyvą, kad galėčiau gauti kuo daugiau prasmingų žodžių. Vienas dalykas, kuris ateina į galvą, yra palikti visus trijų identiškų raidžių derinius iš eilės. Pavyzdys: [bbbacc] nėra labai gera. Arba turėčiau du kartus apriboti kiekvieną maksimalų laišką?

Be to, kuriant skaičius, raidės turi būti sveriamos. Pavyzdžiui, mes nesame daug X ir Ys, bet balsiai gali pasirodyti daug kartų.

Kažkas kita?

Visos rekomendacijos yra sveikintinos.

0
17 янв. Maggie nustatė 17 sausį 2014-01-17 10:02 '14 ne 10:02 2014-01-17 10:02
@ 2 atsakymai

Bet kokio tipo ne žodynų platformos generatorius gali turėti tik keletą faktinių žodžių.

Norėdami išspręsti šią problemą, šis gana paprastas (bent jau aukšto lygio) požiūris į galvą:

  • Yra galiojančių žodžių žodynas.

  • Pakartotinai atsitiktinai pasirinkę nepanaudotą žodį iš žodyno (jei ketinate pasirinkti didelę procentinę dalį žodžių, maišymas padės jums tai padaryti efektyviai, kitaip galite tiesiog išsaugoti jau pasirinktų žodžių rinkinį - tai reiškia, kad tikrai nenorite kopijuoti žodžių vienoje lentoje) ir atlikite šį žodį:

    • Pasirinkite laive atsitiktinę atvirą >

    • Pakartotinai eikite atsitiktine kryptimi (atviroje ląstelėje) kitai raidei. Jei viena iš kaimyninių ląstelių jau turi kitą laišką, mes galime eiti į šį >atgal ir pasirinkite kitą kryptį į ankstesnę raidę.

Galbūt galėjote išstumti ląsteles iš įsitikinimų, jei pasirinkote jį ir negalėjote sudaryti žodžio. Taip pat galite ištrinti visas ląsteles, kurias aplankėte proceso metu, norėdami priskirti šiam žodžiui ląsteles. Nors tai nėra idealus - jei negalite pakeisti 10 raidžių, tai nereiškia, kad trijų raidžių žodis neveiks.

Akivaizdu, kad nustosite, kai lenta iš esmės bus pilna, arba jūs jau turite keletą žodžių ant lentos.

Tai vis dar palieka daug galimybių įgyvendinti, tačiau tai tik aukšto lygio idėja.

0
17 янв. atsakymas duotas Dukeling 17 sausio. 2014-01-17 10:38 '14, 10:38, 2014-01-17 10:38

Pažvelkite į Markovo grandines ir n-gramus (manau, kad skaitmenys tinka šiai problemai), kad sukurtumėte raidžių derinius su didele tikimybe žodžio

0
17 янв. atsakymas pateiktas MBo 17 sausio. 2014-01-17 10:25 '14, 10:25 2014-01-17 10:25

Žr. Kitus klausimus apie kalbos agnostikų žymas arba Užduoti klausimą