Calculator on-line ca o muscă face un elefant

Secvențial convertește un cuvânt de 4 litere într-o altă prin schimbarea o literă a cuvântului precedent la fiecare pas.

Recent, un copil adus acasă de la școală sarcina. În clasa a cincea, la lecțiile de literatură rusă pentru copii set astfel de sarcini: a crea un lanț de cuvinte, din care fiecare ulterioare diferă de cea anterioară printr-o singură literă. stabilit inițial primul și ultimul cuvânt în lanț. Determinată pentru a opri chinul fiica iubit, care timp de mai multe ore în zadar au încercat să facă muhislona. Am scris următorul calculator:

Descrierea soluției

Din prima dată, desigur, câștiga nimic - algoritmul meu recursiv înecată rapid javascript stivă limitat. Conversia unui algoritm recursiv ciclic a dat un rezultat mai bun - muscă a fost transformat într-un elefant în acest fel timp de 10 minute.

Rezultatul obținut a fost potrivit pentru fiica mea, dar nu pentru mine. În plus, în timp ce programul se execută, am avut suficient timp pentru a reflecta asupra îmbunătățirii algoritmului și posibilitatea ipotetic de muște evolua într-un elefant. Acest nonsens-software-ul biologic în cele din urmă m-au condus la un algoritm genetic. care a venit la îndemână pentru această sarcină și a degenerat într-o muscă elefant timp de câteva secunde.

algoritm genetic

Algoritmul genetic a fost numit astfel din cauza asemănării soluțiilor procesului de căutare cu evoluția biologică. soluție a problemei este vectorul de cuvinte care îndeplinesc anumite criterii (cromozomiale). La fiecare pas, vom genera mai multe astfel de vectori (populație), urmată de selectarea celui mai adaptat variantelor (specimene viabile), r. E. Efectuați selecția. Într-o etapă ulterioară, variantele modificate obținute anterior generat din nou noi variante (mutație apare), și atât de mult, până când criteriul de oprire format al algoritmului (în acest caz, este convertit în elefant zbura).

De fapt, algoritmul meu inițial, de asemenea, pot fi atribuite genetice (de selecție prin verificarea unui dicționar), dar din moment ce numărul de variante generate a crescut la fiecare pas, apoi în cele din urmă întreaga populație a noilor specii pentru supraviețuirea a avut nici un spațiu de locuit (CPU ).

În algoritmul îmbunătățit de selecție caracteristică modificată a fost utilizată, care selectează doar cele mai similare cu opțiunile cuvânt. Numărul de opțiunile cele mai viabile este specificată în funcție de mărimea populației. Inferioară numărul, mai rapid algoritmul, cu atât mai multe - cu atât mai bine rezultatele.

Ca o restricție suplimentară criteriu de oprire a fost introdus pe dimensiunea maximă a lanțului, o altă opțiune a fost introdusă în acest scop. Algoritmul se oprește dacă, după un număr predeterminat de generații de reproducere se obține rezultatul dorit.

Funcția de fitness (similaritatea cuvântului curent în final) a evaluat fiecare opțiune pe scara de 12 puncte.

• pentru fiecare literă, care coincide în poziția și valoarea rezultatului final, care urmează să fie alocate 3 puncte
• în cazul în care cuvântul vocalelor a fost în același loc ca și celălalt cuvânt de căutare vocală - 2 puncte
• și unul de puncte sunt acordate numai pentru prezența unei vocale.
  Astfel, ultimul cuvânt ELEPHANT estimat la 12 puncte, iar FLY inițial doar 2.

Unul dintre utilizatorii noștri este înșelat construirea unor astfel de lanțuri, am cerut să fac conversia cuvintelor din 5 litere și permutări o singură literă. Acest calculator on-line ia cuvinte 5 litere din manualul: Cuvinte de 5 litere și