Online számológép, mint egy légy, hogy egy elefánt

Szekvenciálisan átalakítja egy 4 betűs szót egy másik megváltoztatásával egy levelet az előző szó minden egyes lépésnél.

Nemrégiben egy gyermek hozta haza az iskolából feladat. Az ötödik osztályos tanulságok az orosz irodalom a gyermekek számára meghatározott feladatokat, például: hozzon létre egy lánc, azaz minden későbbi amelyek eltér az előzőtől csak egy levelet. Eredetileg az első és utolsó szó a láncban. Azzal a szándékkal, hogy hagyja abba a gyötrelem szeretett lánya, aki több órán keresztül hiába próbálta muhislona. Írtam az alábbi kalkulátor:

Leírás A megoldás

Az első alkalommal, persze, keresni semmi - én rekurzív algoritmus gyorsan túlcsordult korlátozott verem javascript. Konvertálása egy rekurzív algoritmus ciklikus adta a jobb eredményt - légy már át egy elefántot, hogy így 10 percig.

A kapott eredmény alkalmas volt a lányom, de nem nekem. Ezen túlmenően, miközben a program fut, volt elég ideje, hogy az tükrözze az algoritmus fejlesztésén és az elvi lehetőséget legyek fejlődni egy elefánt. Ez a szoftver-biológiai képtelenség végül elvezetett a genetikus algoritmus. ami jól jött a feladat, és fajult egy elefánt fly néhány másodpercig.

genetikus algoritmus

Genetikus algoritmus így nevezték, mert a hasonlóság a keresési folyamat megoldások a biológiai evolúció. megoldás a problémára a vektor a szavak bizonyos előírásoknak megfelelő (kromoszóma). Minden lépésben generáljuk több ilyen vektorok (lakosság), majd kiválasztani a legalkalmasabb variánsok (életképes példányok), r. E. végre a kiválasztást. Az ezt követő lépésben, a korábban kapott módosított változatok újra generált új variánsok (mutáció), és olyan hosszú, amíg a képződött állj feltétel az algoritmus (ebben az esetben, alakítjuk fly elefánt).

Tény, hogy a kezdeti algoritmus is tudható be, hogy a genetikai (kiválasztás ellenőrzésével egy szótár), de mivel a száma generált változatok nőtt minden egyes lépésnél, majd végül a teljes népesség, az új faj túlélése nem volt élettér (CPU ).

A módosított algoritmus továbbfejlesztett funkció kiválasztása használunk, amely kiválasztja csak a leginkább hasonlít a végső szót lehetőségeket. Száma a leginkább megvalósítható lehetőségek által megadott populációmérettel. Minél kisebb a szám, annál gyorsabb az algoritmus, annál -, annál jobb az eredmény.

Mint egy további állj feltétel korlátozást vezettek be a maximális méret a lánc, a másik lehetőség került be erre a célra. Az algoritmus leáll, ha, miután egy előre meghatározott számú generáció reprodukciós kapjuk a kívánt eredményt.

fitness funkció (a hasonlóság a szót a végleges) értékeltük az egyes lehetőségek a 12 pontos skálán.

• Minden levél, amely egybeesik a pozícióját és értékét a végeredmény, el kell osztani 3 pont
• ha a magánhangzó szó volt azon a helyen, mint a többi magánhangzó kereső szó - 2 pont
• és egy pont jár csak a jelenléte egy magánhangzó.
  Így a végső szót ELEPHANT becsült 12 pontot, és a kezdeti FLY csak 2.

Az egyik felhasználó megtévesztette építési ilyen láncokat, azt kérte, hogy ne átalakítását 5-betűs szavak és permutációja egy levelet. Ez az online kalkulátor úgy 5-betűs szavak a kézikönyvből: Words of 5 betű és