Онлайн калкулатор като муха правят слон

Последователно превръща един 4-буквена дума в друга, като промените една буква на предишната дума при всяка стъпка.

Наскоро едно дете донесе вкъщи от училище задача. В пети клас в уроците на руска литература за деца се поставят такива задачи: създаване на верига от думи, всеки следващ от които се различава от предишната само с една буква. Първоначално задаване на първата и последната дума във веригата. Решен да спре мъчение любимата дъщеря, които в продължение на няколко часа в напразно се опита да направи muhislona. Написах следната калкулатора:

Описание на разтвора

От първия момент на, разбира се, печелят нищо - моят рекурсивни алгоритми бързо преля ограниченото стека JavaScript. Преобразуване рекурсивен алгоритъм в цикличен даде по-добър резултат - муха се е превърнал в слон по този начин в продължение на 10 минути.

Полученият резултат е подходящ за дъщеря ми, но не и за мен. В допълнение, докато се изпълнява програмата, имах достатъчно време, за да се отрази за подобряване на алгоритъма и хипотетична възможност за мухи се развива в един слон. Този софтуер-биологична глупости в крайна сметка ме доведе до генетичен алгоритъм. който влезе в удобен за тази задача и дегенерира в слон муха в продължение на няколко секунди.

генетичен алгоритъм

Генетичен алгоритъм е наречен така, защото на сходството на решения на процеса търсене с биологичната еволюция. решение на проблема е векторът на думи, които отговарят на определени критерии (хромозомни). На всяка стъпка, ние генерира множество такива вектори (населението), последвано от подбор на по-силния варианти (жизнеспособни образци), R. Е. Извършване на селекцията. В следващ етап, по-рано получените модифицирани варианти отново генерират нови варианти (мутация се среща), и толкова дълго, докато образува ограничител критерий на алгоритъма (в този случай, се превръща в летлива слон).

Всъщност, първоначалната ми алгоритъм също може да се дължи на генетична (избор чрез проверка на речника), но тъй като броят на генерираните варианти увеличава на всеки етап, а след това в крайна сметка цялото население на новите видове за оцеляването не е имал жизнено пространство (CPU ).

При модифицирания алгоритъм подобрява подбора функция се използва, което избира само най-близките до окончателните варианти на думи. Номер от най-добрите варианти, като се определя от размера на населението. Долната е числото, толкова по-бързо на алгоритъма, толкова повече - толкова по-добри резултати.

Като допълнителен стоп критерий ограничение е въведено по максималния размер на веригата, друг вариант е въведена за тази цел. Алгоритъмът спира, ако след предварително определен брой поколения възпроизвеждане се получава желания резултат.

фитнес функция (приликата на текущата дума на финала) оценява всяка опция по скалата на 12 точки.

• за всяко писмо, което съвпадна с позиция и стойността на крайния резултат, да се разпределят 3 точки
• ако гласна думата е на същото място, както и останалите търсене гласна думата - 2 точки
• и една точки се присъждат само за наличието на гласна.
  По този начин, последната дума ELEPHANT възлиза на 12 точки, а първоначалната може да лети само два.

Един от нашите потребители се увлича изграждането на такива вериги, аз помолих да направи превръщане на 5-писмо думи и пермутация на една буква. Този онлайн калкулатор отнема 5-писмо думи от наръчника: Думи на 5 букви и