Техника - молодёжи 2005-07, страница 58

эхо ■ т м > ДОЛГОЖДАННЫЙ И НЕОЖИДАННЫЙ СЮРПРИЗ

В прошлом номере «ТМ» мы подвели первые итоги конкурса среди приславших ответы на ТМ-ворд в № 1 -4. Очень рады, что игра, которую журнал начал публиковать, вызвала такой интерес у читателей. Но мы были просто ошеломлены, когда в наш адрес пришло это письмо. Наверное, трудно представить, что составленная вручную игра из вопросов, записанных в буквальном смысле огрызком карандаша в блокноте на коленке при перелистывании атласов, энциклопедий и старых номеров «ТМ», даст пищу для ума ученым мужам из Российской Академии наук.

Уважаемый Клуб «ТМ»! Недавно мне совершенно случайно попал в руки номер Вашего журнала за март 2005 г. Я давно уже не видел этого журнала и был приятно удивлен, что он существует и даже неплохо выглядит. Многие статьи этого номера я прочитал с большим интересом. Однако наибольшее мое внимание привлек ТМ-ворд. Я уже довольно давно балуюсь на досуге решением всяческих кроссвордов, и достиг в этом неплохих результатов. Однако в силу своих профессиональных склонностей (работаю уже более 20 лет программистом) меня всегда больше интересовало не само решение кроссворда как таковое, а возможность автоматизации данного процесса, чтобы кроссворды вместо человека могла решать программа.

Еще в 1993 г. я предпринял попытку и в результате написал программу (тогда еще в операционной системе DOS), которая хоть и не решала кроссворд целиком, зато резко упрощала поиск нужных слов, поскольку работала с автоматизированным словарем существительных русского языка, фамилий и географических названий. С тех пор я постоянно слежу за появлением в различных журналах и газетах каких-нибудь новых типов аналогичных головоломок, чтобы исследовать возможность их автоматического решения.

ТМ-ворд явился для меня долгожданным и неожиданным сюрпризом. Прочитав условия, как нужно решать его и что должно получиться в результате, и взглянув внимательно на картинку, изображающую данный ТМ-ворд, я сразу понял: это то, что нужно в смысле возможности автоматического решения. Если в обычном кроссворде с пересекающимися словами вариантов подбора любого слова на любое место существует множество, даже несмотря на семантическое отсечение вариантов с помощью ключевых слов описания данного слова, то в ТМ-вор-де все варианты сильно взаимосвязаны, в результате чего их количество резко ограничивается.

С математической точки зрения, ТМ-ворд представляет собой плоский многосвязный ориентированный граф с заданными начальным и конечным узлами, а задача его решения фактически сводится к нахождению всевозможных путей по

заданному графу от начального до конечного узла. С первого взгляда на ТМ-ворд ясно, что в этом графе существует множество циклов, которые, очевидно, не приводят к решению. Это позволяет довольно быстро сократить число вариантов, отсекая от графа заведомо неподходящие узлы. Кроме того, в результате каждого прохода по графу образуется набор букв определенной длины, который в качестве анаграммы должен представлять собой некоторое слово русского языка той же самой длины. Имея автоматизированный словарь русского языка, это довольно легко проверить.

В результате все свои идеи по поводу автоматизации решения вашего ТМ-вор-да я оформил в виде весьма небольшой программы на стандартном языке ANSI С и сразу же получил единственное решение. Отмечу специально, что речь идет не о создании программы, которая обладает пресловутым «искусственным интеллектом», т.е. анализирует смысл вопросов ТМ-ворда и подбирает правильные решения. Программы, слава богу, не умеют этого делать, и, наверное, не скоро еще научатся. Данная программа просто анализирует связи между узлами в графе и пытается построить путь от одного узла до другого, независимо оттого, по правильным ответам идет путь или нет. Решение данного ТМ-ворда, согласно выходному файлу программы, выглядит следующим образом. Программа обнаружила в заданном графе 29 узлов (включая узел под названием «финиш») и 63 ребра, связывающие эти узлы.

При полном поиске путей по графу программа выявила всего 2405 вариантов различных проходов по графу от начального до конечного узла. В качестве дополнительной информации программа сообщила, что четвертый узел в верхнем ряду ТМ-ворда, содержащий вопрос «Какой продукт получают путем взрыва?», вообще не участвует ни в одном из вариантов и может быть смело исключен из данного ТМ-ворда вместе с входящими и выходящими из него ребрами. Для каждого из полученных 2405 вариантов набора букв программа проверила по словарю возможность составления анаграммы той же длины.

В качестве словаря использовался spelling-словарь от русифицированной версии хорошо известной программы MS Word, содержащий 78434 слова. В результате программа выдала всего лишь два варианта: анаграмма от последовательности букв «рекеилйичкэтс» дает слово «электрический», а анаграмма от последовательности «тиул-десес» дает слово «исследует». Поскольку последний вариант не подходит по смыслу сформулированного описания ключевого слова, как одного из способов общения и ухаживания в рыбьем царстве, остается лишь один вариант, и этот вариант ключевого слова «электрический».

Полное время работы программы на процессоре AMD Athlon 2200+ состави

ло всего лишь 7 с. Теперь, после получения ключевой последовательности и ключевого слова, мгновенно можно сформулировать ответы на 13 вопросов ТМ-ворда. Записывая их в принятом у вас виде, решение ТМ-ворда выглядит для начала следующим образом:

1) 449 м-?-?-? - железные пластинки

2) банановое соцветие -?-?-?- переохлажденная жидкость - ?

3) ? - Мейсенский фарфор - выкройка готического платья - пары ртути -кратер - ?

4) ? - Титания - ? - Ада - 1965 г. -сбрил бороду

5) ? - ? - ? - ? - обе

Ключевое слово: электрический

Здесь знаком вопроса обозначены

ответы, которые не участвуют в формировании ключевого слова. В принципе, можно было бы уже считать решение ТМ-ворда на этом законченным, поскольку, хотя 15 ответов из 28 не получены, тем не менее, ключевое слово уже известно. В дополнение к ответам, полученным с помощью программы, я попытался дать ответы еще на какие-ни-будь вопросы, воспользовавшись доступом в Интернет или энциклопедией «Britannica», последняя версия которой вышла совсем недавно.

В результате этого я смог дать однозначные ответы еще на семь вопросов, так что окончательно решение ТМ-вор-да выглядит так:

1) 449 м - ? - Муха це-це - ? - железные пластинки

2) банановое соцветие - ? - Берта Бенц -? - переохлажденная жидкость - 71 %

3) в аптеке - Мейсенский фарфор -выкройка готического платья - пары ртути - ? - кратер - Александрия

4) 1823 г. - Титания - ? - Ада - 1965 г. -сбрил бороду

5) ? - ? - ? - Ад - обе

Ответы на некоторые из оставшихся вопросов мне просто не очень хотелось искать (выяснять, кто автор телефона с лобстером, или что за стиль, в котором сделаны часы на картинке), поскольку они все равно не участвуют в формировании ключевого слова, а ответы на другие выглядят, как мне кажется, неоднозначными.

Я вовсе не ожидаю от вас получения какого-нибудь приза за написание программы для решения ТМ-ворда. Во-первых, я уже просто вышел из того возраста, когда человеку интересен результат, а не сам процесс. А во-вторых, я уже получил от вас награду в виде самой идеи ТМ-ворда и благодарен вам за возможность проявить свои профессиональные навыки даже в таком несерьезном деле. Желаю вам и дальше радовать своих читателей какими-ни-будь интересными идеями.

С уважением, Андрей ГРОМОВ, главный специалист по программированию Лаборатории спутникового мониторинга Института Автоматики

и Процессов Управления (ИАПУ ДВО РАН), г. Владивосток

m

ТЕХНИКА- МОЛОДЕЖИ 7' 2 0 0 5

56