Слон из мухи
Содержание
Александр Пиперски
«Квантик» №2, 2019 и №3, 2019
В повести известного писателя Юрия Трифонова (1925–1981) «Долгое прощание» рассказывается, как герой проводит время в поезде: «Третьи сутки Ребров, лёжа на верхней полке, мучил себя — делал из мухи слона. На листке бумаги писал: муха — мура — кура — кора — корт — торт — торс…».
Правила игры очень просты: надо построить цепочку слов от начального (МУХА) до конечного (СЛОН), на каждом шаге меняя только одну букву. При этом могут использоваться только русские 4-буквенные нарицательные существительные в начальной форме: например, слова БАЗА, НОЧЬ, САНИ допускаются, а слова ЛИТЬ, ХОТЯ, РУКУ, НОЧИ, САНЯ, ОСЛО, АБВГ, ФЦНМ — нет (первые два — не существительные, следующие два — не в начальной форме, следующие два — собственные, а не нарицательные, а два последних вовсе не существуют в языке).
Эта игра под названием «Дублеты» приобрела известность благодаря Льюису Кэрроллу — не только автору книг про Алису, но ещё и замечательному математику. В марте 1879 года он начал раз в неделю публиковать в журнале «Ярмарка тщеславия» по три задания в форме броских фраз: «Turn POOR into RICH» — «Преврати бедного в богатого», «Evolve MAN from APE» — «Выведи человека из обезьяны», «Make TEA HOT» — «Сделай чай горячим». В том же году он выпустил брошюру «Дублеты», подробно описал в ней правила и предложил читателям попрактиковаться на нескольких десятках примеров.
Вот и вам пять пар для тренировки — попробуйте построить для них цепочки. Сразу предупреждаю, что в одном случае, скорее всего, не получится: БОРЩ → ПОСТ; ЛИПА → ЖАРА; КИНО → ВАТА; КЛЕН → ЕЛКА; ПАУК → ЛОСЬ.
Ответ
БОРЩ → БОРТ → ПОРТ → ПОСТ;
ЛИПА → ЛАПА → ПАПА → ПАРА → ЖАРА;
КИНО → ВИНО → ВИНА → ВИЗА → ВАЗА → ВАТА;
ПАУК → ПАРК → ПАРА → КАРА → КОРА → КОЖА → ЛОЖА → ЛОЖЬ → ЛОСЬ;
из КЛЕН получить ЕЛКА нельзя.
Вы наверняка нашли четыре из пяти цепочек, а не смогли построить только одну. Но как доказать, что это действительно невозможно? Может быть, мы просто не придумали способ, а вообще-то он есть. Разобраться нам поможет теория графов.
Первым делом договоримся о том, что именно мы считаем словами, а то может получиться, что я дам вам задание МУХА → СЛОН и вы скажете: «4 хода! МУХА → МУХН → МУОН → МЛОН → СЛОН». Тогда мне придётся со словарями в руках доказывать, что это жульничество, потому что слов МУХН, МУОН и МЛОН не существует. Чтобы избежать этого, мы обратимся к словарю с самого начала и постановим, что будем пользоваться только теми 4-буквенными существительными, которые есть в заранее выбранном источнике. Для этой статьи я взял «Грамматический словарь русского языка» Андрея Зализняка — этот словарь чаще всего применяют в компьютерной лингвистике. Кстати, мысль о том, что очень важно заранее договориться о словаре, пришла в голову ещё Льюису Кэрроллу: 28 из 39 страниц его книги как раз и занимает перечень английских слов, которые можно использовать в игре. Кроме того, условимся, что мы не используем в игре букву Ё и заменяем её на Е.
Всего в «Грамматическом словаре» 1712 четырёхбуквенных существительных. Возьмём, к примеру, существительное ЛОЖЬ и изобразим его точкой. Найдём в словаре все слова, которые отличаются от него на одну букву; их ровно четыре: ЛОЖА, ЛОЖЕ, ЛОСЬ и РОЖЬ. Изобразим их точками, соединёнными со словом ЛОЖЬ; наличие связи означает, что между словами можно перейти за один ход. (Кстати, какую ещё пару слов надо не забыть соединить?) Затем добавим слова, которые за один ход получаются из этих четырёх слов: КОЖА, ЛОЗА, ЛУЖА, ЛЫЖА, РОЖА, РОЛЬ, ЛОСК, — и нарисуем нужные связи.
В итоге у нас получился граф, в котором некоторые из 12 точек (вершин) соединены отрезками (рёбрами). Если нам нужно превратить одно слово в другое, на математическом языке это формулируется так: найти путь между соответствующими вершинами, желательно кратчайший. Так, если нам надо пройти от ЛЫЖА до РОЛЬ, это займёт четыре шага, и пути могут быть разными: ЛЫЖА → ЛОЖА → РОЖА → РОЖЬ → РОЛЬ или ЛЫЖА → ЛОЖА → ЛОЖЬ → РОЖЬ → РОЛЬ. (Докажите, что более короткого пути между словами ЛЫЖА и РОЛЬ нет.)
А теперь изобразим так не 12 слов, а все 1712, и посмотрим, как устроен этот граф. Вручную это сделать едва ли возможно, так что понадобится компьютер. Видно, что на графе выделяется большой кусок, где от любого слова можно дойти до любого другого; в теории графов такой подграф называют компонентой связности. Есть ещё несколько таких кусков поменьше и много точек, которые не связаны вообще ни с чем (такие отдельно стоящие точки тоже можно считать компонентами связности). Ясно, что от одного слова можно дойти до другого тогда и только тогда, когда они входят в одну и ту же компоненту связности.
Самая большая компонента связности включает в себя 1361 слово (то есть 79,5% всех слов). Кроме неё есть компонента размером 11 слов, ещё одна — размером 6 слов, 3 — размером 5 слов, 4 — размером 4 слова, 14 — размером 3 слова, 25 — размером 2 слова и ещё 211 отдельно стоящих слов (АЛОЭ, ВДОХ, ДЖАЗ, НЕБО, ОПЫТ, СОЮЗ, ТАЙМ и другие). Слово КЛЕН входит в большую компоненту связности, а слово ЕЛКА — в маленькую, 5-словную; этим и объясняется тот факт, что из слова КЛЕН не получится ЕЛКА.
Всего в нашем графе 3172 ребра, а значит, у слова в среднем 3172 1712 · 2 = 3,7 соседей. Возвращаясь к самой большой компоненте связности, обратим внимание на то, что из неё торчат «хвосты». Дело в том, что даже в ней у некоторых слов совсем мало соседей. Скажем, от слова ТИГР можно перейти только к слову ТИТР, от него — только к слову ЛИТР, дальше — только к слову ЛИВР (это старинная французская монета, вспомните «Трёх мушкетёров»), дальше — только к слову ЛАВР, а уже от него — к словам МАВР и ЛАВА, после чего возможностей становится резко больше: от слова ЛАВА отходит ещё 5 слов, и мы попадаем в основую гущу вершин.
Таким образом, слово ТИГР — это конец хвоста, и если понадобится пройти из одного такого хвоста в другой, путь может получиться очень длинным, даже если это кратчайший путь между этими двумя вершинами. Самые длинные пути имеют длину 23 — например, от слова ДЖИП до слова ТУЕС (берестяная коробочка) всего 22 шага: ДЖИП → ДЖИН → УЖИН → УДИН → ОДИН → ОВИН → ОВЕН → ОВЕС → СВЕС → СВЕТ → СВАТ → СВАН → СТАН → СТЕН → СТЕК → САЕК → РАЕК → РОЕК → БОЕК → БУЕК → БУЕР → ТУЕР → ТУЕС. Глядя на эту цепочку, вам наверняка хочется пожаловаться: «Я же не знаю половины этих слов!» (признаюсь честно: я тоже не знаю). Но раз мы договорились использовать «Грамматический словарь», то и будем на него опираться, а к борьбе с незнакомыми словами вернёмся чуть позже.
Для 5-буквенных слов английского языка такой граф впервые построил знаменитый американский учёный и автор классических пособий по программированию Дональд Кнут. А почему, кстати, у него 5 букв, а у нас — 4? Есть ли какое-то объяснение тому, что в игру «Из мухи — слона» по-русски обычно играют 4-буквенными словами? Интуитивно кажется, что так интереснее всего. Но попробуем оценить этот интерес и количественно.
Представьте себе, что мы играем однобуквенными словами. В «Грамматическом словаре» ровно 9 однобуквенных существительных: А, Е, И, О, У, Ы, Э, Ю, Я — названия гласных букв (слово Ё мы объединили со словом Е). Из любого слова к любому можно перейти за один ход, и это неинтересно. Если, напротив, играть в 10-буквенные слова, то от большинства слов — как, скажем, от слова БЕЗДЕЛЬНИК, — вообще нельзя никуда перейти. Получается, что игра интересна, когда выполнены два требования: пути между словами длинные и между двумя произвольно взятыми словами путь обычно существует (но не всегда — если успех гарантирован, играть тоже скучно).
Чтобы оценить среднюю длину пути, надо найти самые короткие пути между всеми парами точек, для которых путь есть, и вычислить среднее. Это трудоёмкий процесс, но есть алгоритмы, которые производят такое вычисление достаточно быстро. А сделав его, узнать вероятность успеха совсем просто: у нас есть 1712 4-буквенных слов, а значит, 1712 · 1711 упорядоченных пар (от любого из 1712 слов мы пытаемся пройти к любому из 1711 оставшихся); посчитаем, сколько из них соединены путём, и разделим на 1712 · 1711. Таких пар 1 851 342, а значит, вероятность успеха равна 1 851 342 / (1712 · 1711) ≈ 0,632.
Можно сделать то же самое по-другому, опираясь на знания про размеры компонент связности. Возьмём произвольное начало цепочки; вероятность того, что оно попадёт в большую компоненту связности, составляет 1361/1712; возьмём теперь другое произвольное слово в качестве конца цепочки: в большой компоненте осталось 1360 слов, а всего в словаре — 1711, то есть вероятность того, что оно окажется связанным с началом, составляет 1360/1711. Тогда начало и конец цепочки попадут в большую компоненту с вероятностью 1361 · 1360 / (1712 · 1711). Во вторую по величине компоненту связности они попадут с вероятностью 11 · 10 / (1712 · 1711). Суммируя эти вероятности для всех компонент, получим то же число 0,632. Результаты подсчётов для слов от 1 до 12 букв — в таблице:
Видно, что 4-буквенные слова действительно обеспечивают хорошую, но всё же не стопроцентную вероятность успеха и при этом создают достаточно длинные цепочки. А с 10-буквенными словами всё скучно: даже в тех редких случаях, когда путь есть, он обычно состоит из одного шага (ВОЗМЕЩЕНИЕ → ВОЗМУЩЕНИЕ), редко — из двух или больше. Единственный путь из пяти шагов соединяет слова ПАССИРОВКА и ФАРШИРОВКА: ПАССИРОВКА → МАССИРОВКА → МАСКИРОВКА → МАРКИРОВКА → МАРШИРОВКА → ФАРШИРОВКА.
Эта цепочка напоминает ещё об одной проблеме, с которой надо разобраться: редкие слова. Попробуйте решить такую задачу: ДАЛЬ → ПАРИ. В этих словах совпадает буква А на втором месте, и есть надежда справиться за три шага. Действительно, такой путь есть: ДАЛЬ → ПАЛЬ → ПАЛИ → ПАРИ. Но едва ли он вас порадует: большинство людей не знают ни слова ПАЛЬ (‘выжженный участок в лесу или в степи’), ни слова ПАЛИ (один из древних индийских языков). Но существует и путь из более нормальных слов: ДАЛЬ → ДАНЬ → ДЕНЬ → ТЕНЬ → ТЕНТ →ТЕСТ → ТОСТ → ПОСТ → ПОРТ → ПОРА → ПАРА → ПАРИ. Он длиннее, но в каком-то смысле лучше пути из трёх шагов. Попробуем формализовать эту идею.
Для этого нам понадобится ещё один словарь — частотный (я пользуюсь «Новым частотным словарём русской лексики» О. Ляшевской и С. Шарова). В частотном словаре слова упорядочены по тому, насколько они употребительны в языке: 1-е место занимает союз И, на 2-м месте — предлог В, на 3-м — частица НЕ и т. д. А вот 10 самых частых 4-буквенных существительных с указанием их мест: 65) ДЕЛО, 71) ДЕНЬ, 74) РУКА, 104) ЛИЦО, 106) ДРУГ, 110) ГЛАЗ, 140) СИЛА, 191) ВОДА, 192) ОТЕЦ, 205) НОГА.
Слова типа ДЖИП и ТИТР стоят гораздо ниже: 6616) ДЖИП, 8086) ТИТР. Всего в этом словаре 52 138 слов, из них с «Грамматическим словарём» пересеклось 1140 4-буквенных существительных. А, например, слово ЛИВР (старая французская монета) даже не попало в частотный словарь. Условно присвоим ему и всем другим таким словам номер 100000.
А теперь сделаем наш граф ориентированным и взвешенным. Ориентированный — это значит, что из вершины в вершину будут вести не отрезки, а стрелки, точнее пары стрелок: одна в одну сторону, другая в другую. А взвешенный значит, что каждой стрелке будет приписан вес: по одним стрелкам ходить будет дороже, а по другим дешевле. Веса припишем так: если стрелка ведёт в слово, которое занимает k-е место в частотном словаре, припишем ей вес k (мы могли бы выбрать и какую-нибудь другую функцию, но квадратный корень даёт результаты, которые кажутся подходящими для наших нужд). Например, все стрелки, ведущие в ДЕЛО, получают вес 65 ≈ 8,1 , все стрелки, ведущие в ТИТР, — 8086 ≈ 89,9 , а все стрелки, ведущие в ЛИВР, — 100000 ≈ 316,2 . Длиной пути теперь будет не количество рёбер, а сумма чисел на стрелках, по которым мы двигались. Проходить редкие слова теперь невыгодно: ведущие в них стрелки весят слишком много.
Попробуем для примера найти оптимальный путь от слова ЛОЖЬ к слову РОЖА. Возьмём подграф, содержащий слова ЛОЖЬ, РОЖЬ, ЛОЖА и РОЖА, и разметим в нём веса.
Окажется, что путь ЛОЖЬ → РОЖЬ → РОЖА стоит 121,6 + 78,6 = 200,2, а путь ЛОЖЬ → ЛОЖА → РОЖА стоит 82,6 + 78,6 = 161,2. Иначе говоря, выгоднее идти через более частое слово ЛОЖА, чем через более редкое РОЖЬ.
Но вернёмся к путям от ДАЛЬ к ПАРИ. Оказывается, более длинный по числу шагов путь выгоднее с точки зрения весов: ДАЛЬ → 96,5 ДАНЬ → 8,4 ДЕНЬ → 36,4 ТЕНЬ → 140,9 ТЕНТ → 65,8 ТЕСТ → 81,6 ТОСТ → 38,8 ПОСТ → 58,4 ПОРТ → 16,6 ПОРА → 27,9 ПАРА → 126,2 ПАРИ (сумма 697,5); ДАЛЬ → 316,2 ПАЛЬ → 316,2 ПАЛИ → 126,2 ПАРИ (сумма 758,6).
Так мы формализовали ощущение, почему длинная цепочка с известными словами лучше, чем короткая с неизвестными. Кстати, для задачи МУХА → СЛОН цепочки без весов и с весами тоже разные. Без весов (10 шагов): МУХА → МУРА → МАРА → ПАРА → ПАРК → ПАЕК → САЕК → СТЕК → СТЕН → СТОН → СЛОН; с весами (13 шагов): МУХА → МУКА → ЛУКА → ЛУПА → ЛАПА → ПАПА → ПАРА → ПАРК → ПАЕК → САЕК → СТЕК → СТОК → СТОН → СЛОН.
Увы, и в цепочке с весами не удалось обойтись без малоизвестного слова САЕК (точнее, САЁК), которое значит ‘молодой олень’. Но другие решения этой задачи включают в себя ещё и не такое. Самую короткую из известных цепочек придумал Владимир Гончаров; в ней 7 шагов: МУХА → МУЛА → КУЛА → КИЛА →КИЛН → КИОН → СИОН → СЛОН. По нашим правилам она не подходит, потому что в «Грамматическом словаре» из 6 промежуточных слов есть только КИЛА (это разговорное название для грыжи), а если бы они и были, то с весами эта цепочка стоила бы очень дорого, ведь все промежуточные слова в ней редкие — да и разве интересна цепочка, в которой 6 из 6 промежуточных слов нам неизвестны?
Всё сказанное выше, с одной стороны, звучит неутешительно: игру «из мухи — слона» постигла судьба шахмат и шашек — компьютер играет в неё гораздо лучше человека. С другой стороны, не всё так плохо: компьютерный анализ позволил нам узнать много интересного и про саму игру, и про русский язык.
Художник Мария Усеинова
Многим известна игра со словами, сделать из мухи слона
Суть её в том, что нужно из начального слова сделать конечное, на каждом шаге меняя только одну букву, получая при этом на каждом шаге осмысленное существительное.
Классическое решение задачи как из мухи сделать слона
Как из мухи сделать слона из 16 ходов
муха — мура — тура — тара — кара — каре — кафе — кафр — каюр — каюк — крюк — урюк — урок — срок — сток — стон — слон.
Решение из 10 ходов (10 переходов):
муха — мура — фура — фора — кора — корн — коан — клан — клон — слон
Решение из 9 ходов (9 переходов):
муха — маха — мана — манн — ланн — линн — лион — сион — слон
Самый короткий вариант из 8 ходов:
муха — муна — луна — лина — линн — лион — сион — слон
муха — муна — мина — лина — линн — лион — сион — слон
Значение словосочетания «делать из мухи слона»
МУХА — СЛОН
Делать из мухи слона
— сильно преувеличивать что-либо, придавать чему-либо незначительному большое значение
— крайне преувеличивать, представлять мелочь и ничтожное имеющим крупное значение
Предложения со словосочетанием «делать из мухи слона»
Вполне вероятно, её мать преувеличила серьёзность проблемы с деньгами, она всегда делала из мухи слона… А что, если в этот раз всё действительно серьёзно?
Триш Мори, Все очень просто, 2013
Внешне он — само спокойствие, а потому и все вокруг недоумевают, отчего у него постоянно возникают стычки с трагиками, делающими из мухи слона.
Лууле Виилма, Лууле Виилма. Книга-надежда, книга-спасение! Исцеление от любой болезни силой Любви, 2015
— С работы я вернулся вовремя, — нахмурился отец, — Что ты, детуня, делаешь из мухи слона?
Анатолий Зарецкий, Мысли из палаты №6
Мне казалось, что перепуганные, затравленные «буржуи» боятся даже собственной тени и делают из мухи слона.
И. В. Одоевцева, На берегах Невы
— Ну вот, ты опять делаешь из мухи слона.
Меллори Кейн, Третье чудо, 2015
И вы совершенно напрасно делаете из мухи слона.
Элизабет Мид-Смит, Семь молоденьких девиц, или Дом вверх дном, 1904
Не делай из мухи слона. Вдруг полетит.
В. Н. Ковалев, Афоризмы-размышлизмы
Перестаньте же делать из мухи слона!
Е. А. Тарасов, Как преодолеть свои страхи и комплексы. 10 тестов + 14 правил, 2015
Это всё равно, что делать из мухи слона.
В. В. Козлов, Конфликт: участвовать или создавать…
Ошо, почему я делаю из мухи слона?
Б. Ш. Раджниш (Ошо), Древняя музыка в соснах: в дзен разум внезапно останавливается
Поэтому продолжает делать из мух слонов.
Б. Ш. Раджниш (Ошо), Древняя музыка в соснах: в дзен разум внезапно останавливается
— Может, это и в самом деле чей-то глупый розыгрыш, а я делаю из мухи слона.
Вера и Марина Воробей, В паутине страха
Она не делала из мухи слона, а просто писала.
Джулия Кэмерон, Право писать. Приглашение и приобщение к писательской жизни, 1998
— Всё-таки не понимаю, почему ты делаешь из мухи слона.
Стефани Лоуренс, Безупречная жена, 1997
Принимать малейшую критику, как величайшее оскорбление и делать из мухи слона.
Ирина Бйорно, Тридцать три несчастья, или Как стать ЭНЖеком
Может, я просто все преувеличиваю и делаю из мухи слона.
Алена Бородина, Всё в моих руках, 2013
Крапивница, как правило, имеет отношение к мелким, сокрытым в глубине души страхам, а также к склонности делать из мухи слона.
М. Л. Шульц, Всё будет хорошо!, 2013
Кто выискивает в слове недобрый скрытый смысл, тот его находит, даже если собеседник говорил без задней мысли. Уши слушающего делают из мухи слона.
Лууле Виилма, Тепло надежды, 2012
Если вы не будете делать из мухи слона, то вскоре всё вернётся на круги своя.
Анн Бакюс, Гид по воспитанию детей от 1 до 3 лет. Практическое руководство от французского психолога, 2012
Но дипломаты не были бы дипломатами, если бы не считали долгом своей чести усложнять простые вещи, делать из мухи слона и затягивать решение любого важного
вопроса всяческими искусными способами.
Стефан Цвейг, Мария Антуанетта, 1932
Неточные совпадения со словосочетанием «делать из мухи слона»
И вот по своему обыкновению из мухи делать слона, а потом спекулировать фальшивой слоновой костью, они и раздули один год до юбилея.
В. С. Бушин, Пятая колонна. Отпор клеветникам, 2014
Это значит из мухи делать слона, а из слона муху.
Валентин Мордасов, Святые отцы об исповеди. Духовник и отношение к нему, 1992
Повторяю, вы всё время из мухи делаете слона.
Элизабет Мид-Смит, Семь молоденьких девиц, или Дом вверх дном, 1904
— Это верный признак того, что кто-то склонен из мухи делать слона.
Эдуард Веркин, Большая книга летних приключений, 2009
До сих пор люди умели из мухи делать слона, а вы хотите из мухи сделать человека…
А. Р. Беляев, Ариэль, 2016
Наш смиренник распускает хвост, словно павлин, задирает хохол, а тем временем бесстыжий льстец приравнивает этого ничтожного человека к богам, выставляет его образцом всех доблестей, до которых тому, как до звезды небесной, далеко, наряжает ворону в павлиньи перья, старается выбелить эфиопа и из мухи делает слона.
Эразм (Дезидерий) Роттердамский, Похвала глупости, 1509
Наверняка она опять раздула из мухи слона!
Триш Мори, Все очень просто, 2013
Ещё он сказал, что все дети дерутся время от времени и нечего раздувать из мухи слона.
М. Е. Некрасова, Скелеты на пороге, 2008
Раздуть из мухи слона — и муха лопнет!
Н. Г. Еремич, Тайм-менеджмент для женщин. Как все успевать, 2008
Вдруг раздуваю из мухи слона?
Ю. М. Герт, Избранное, 2014
— Мне следовало бы пойти за женой и успокоить её, а то она способна сделать из мухи слона.
В. И. Крыжановская-Рочестер, Заколдованный замок, 1898
Тоже мне, сделал из мухи слона.
Александр Базель, Пепел страниц
Я подумал, что, может, телевидение, как всегда, раздуло из мухи слона и решило накормить своих почитателей вкусной побасёнкой?
Арчибальд Брукс, Когда зомби оживают… Призрачная магия Черного континента, 2008
Длинные языки раздуют из мухи слона, ведь всем известно, что обычно он не прилагает столько усилий.
Мэдлин Хантер, Опасность в бриллиантах, 2012
Не стоит раздувать из мухи слона.
Ольга Морозова, Ван Гог и Марго (сборник), 2013
Могло ли быть так, что она раздула из мухи слона?
Морган Райс, Обманутая, 2011
Действительно, что-то я раздуваю из мухи слона.
Светлана Головьева, Невеста поневоле
На то они и были специалисты, дабы добывать из обыденных мелочей зерна истины, а может, выращивать из мух слонов.
Ф. Д. Березин, Параллельный катаклизм, 2002
Нечего делать из мухи слона.
Кимберли Лэнг, Не по сценарию, 2012
Известно: мы, женщины, любим сделать из мухи слона, раздуть проблему.
Лидия Филановская, Сияние предметов и людей (сборник), 2007
— Перестань раздувать из мухи слона!
А. В. Устинова, Загадка черной вдовы, 2014
Они могут сделать из мухи слона, копить обиды и излишне остро реагировать в критические моменты.
Патрисия О’Коннелл, Как компании-лидеры избегают бестолковых решений. Преодоление 8 «подводных камней», которые способны разрушить даже непотопляемый бизнес Поддавшись таким мыслям, женщина сделала из мухи слона.
Шефали Тсабари, Дети – зеркало нашего тайного «Я». Как на самом деле сделать счастливыми себя и своих детей!, 2010
Мне хочется сказать: не раздувайте из мухи слона.
Лариса Суркова, Как здорово с ребенком от 1 до 3 лет: генератор полезных советов, 2015
Легко раздувала из мухи слона, чем постоянно его выводила из себя.
Елена Сподина, Дорога судьбы. Повесть
Если у вас есть какие-то очень важные проекты, суперсерьёзные задачи, проверьте, не раздутый ли это из мухи слон.
Алиса Курамшина, Достигатор на халяву, 2014
Вы думаете, невозможно сделать из мухи слона? Hепpавда! Можно, но тpудно:
МУХА — муpа — туpа — таpа — каpа — каpе — кафе — кафp — каюp — каюк — кpюк — уpюк — уpок — сpок — сток — стон — СЛОH.
Муха пpевpатилась в слона всего лишь за 16 ходов. Как видите, пpи одном ходе можно заменять лишь одну букву, поpядок следования букв пpи этом менять нельзя. Попpобуйте по этим пpавилам совеpшить «путешествие во вpемени» — пpевpатить сначала МИГ в ЧАС, затем ЧАС в ГОД, затем ГОД в ВЕК, и наконец ВЕК в слово «ЭРА». Всего эта цепочка занимает 17 ходов. Получилось? Да или нет — ничего стpашного, но это еще не все. Попpобуйте тепеpь сделать «скачок во вpемени» — пpевpатить слово МИГ сpазу в слово ЭРА за 6 ходов.
Ответ: 1) МИГ — маг — май — чай — ЧАС — чад — гад — ГОД — род — рок — бок — бек — ВЕК — бек — бок — боа — бра — ЭРА
Или:
… — ГОД — гид — вид — вис — вес — ВЕК — …
Если использовать отсутствующее в словаре, но всем нам известное слово БОД (единица скорости передачи информации), то получается чуть короче:
МИГ — маг — май — чай — ЧАС — чад — гад — ГОД — бод — бок — бек — ВЕК — бек — бок — боа — бра — ЭРА
(слово БОД можно считать пpочно вошедшим в нашу жизнь неологизмом, а следовательно и использовать).
2) МИГ — мир — мор — бор — боа — бра — ЭРА
Недавно ребенок принес из школы задачку. В пятом классе на уроках русской словесности детям задают такие задания: составить цепочку слов, каждое последующее из которых, отличается от предыдущего всего на одну букву. Изначально задано первое и последнее слово цепочки. Решив прекратить мучения любимой дочки, которая в течение нескольких часов тщетно пыталась сделать из мухи слона, я написал следующий калькулятор:
Преобразование 4-х буквенных слов при помощи генетического алгоритма
Начальное слово Слово из которого надо получить второе слово Конечное слово Слово в которое требуется преобразовать первое слово Максимальная длина цепочки Размер популяции Максимальное количество элементов в каждом поколении Рассчитать content_copy Ссылка save Сохранить extension Виджет
Описание решения
Поначалу я применил «грубую силу» и попробовал решить задачу в лоб. Суть моего наивного метода сводилась к построению дерева слов, полученных путем перебора всех букв русского алфавита и подстановке их вместо одной из букв предыдущего слова (см. рисунок).
Неконтролируемое увеличение популяции при использовании наивного алгоритма
Каждое новое слово проверялось на отсутствие среди предшествующих, а также на наличие в словаре, который я перенес с сайта любителей кроссвордов в наш справочник Слова из 4-х букв (надеюсь, авторы сайта меня простят за эту вольность).
Далее, успешно проверенное слово включалось в дерево и для него снова проводилась аналогичная процедура, до тех пор, пока не будет найдено искомое слово.
С первого раза, конечно же, ничего не заработало — мой рекурсивный алгоритм быстренько переполнил ограниченный стек джаваскрипта. Преобразование рекурсивного алгоритма в циклический дало более удачный результат — муха была трансформирована в слона минут этак за 10.
Полученный результат был пригоден для дочки, но не для меня. К тому же, пока работала программа, у меня было достаточно времени поразмыслить над улучшением алгоритма и гипотетической возможностью мухи эволюционировать в слона. Этот программно-биологический бред в конечном итоге привел меня к генетическому алгоритму, который как нельзя кстати подошел для решения этой задачи и переродил муху в слона в течение нескольких секунд.
Генетический алгоритм
Генетическим алгоритм был назван так из-за сходства процесса поиска решения с биологической эволюцией. Решением задачи является вектор слов, удовлетворяющих некоторому критерию (хромосома). На каждом шаге мы порождаем несколько таких векторов (популяцию), после чего осуществляем отбор наиболее пригодных вариантов (жизнеспособных особей), т. е. выполняем селекцию. На последующем шаге ранее полученные варианты снова видоизменяются, порождаются новые варианты (происходит мутация) и так до тех пор, пока не будет выполнен критерий останова алгоритма (в нашем случае муха преобразуется в слона).
По сути, мой начальный алгоритм тоже можно было отнести к генетическим (селекция осуществлялась путем проверки по словарю), но так как число порожденных вариантов увеличивалось на каждом шаге, то в конечном итоге всей популяции новых особей для дальнейшего существования не оставалось жизненного пространства (ресурсов процессора).
В модифицированном алгоритме была применена улучшенная функция селекции, которая отбирает только самые похожие на конечное слово варианты. Количество самых жизнеспособных вариантов задается параметром Размер популяции, чем меньше это число, тем быстрее работает алгоритм, чем больше — тем качественнее получается результат.
В качестве дополнительного критерия останова было введено ограничение на максимальный размер цепочки, для этого был введен еще один параметр. Алгоритм остановится, если после воспроизводства заданного числа поколений не будет получен искомый результат.
Функция приспособленности (похожести текущего слова на конечное) оценивала каждый вариант по 12 бальной шкале.
- за каждую букву, совпадающую по положению и значению с конечным результатом, начислялось 3 балла
- если гласная буква слова находилась на том же месте, что и другая гласная буква искомого слова — 2 балла
- и один балл начислялся просто за наличие гласной буквы.
Таким образом, конечное слово СЛОН оценивалось в 12 баллов, а начальная МУХА всего в 2.
Желающие более детально ознакомиться с алгоритмом, могут это сделать, путем исследования содержимого функции calculate из javascript’а этой страницы.
