Сложно ли сделать из мухи слона?

Недавно, перед тем как написать про свои соображения о путях развития ИИ ^[1], решил посмотреть, что уже писали об ИИ на Хабре. В числе прочих наткнулся на статью ^[2] с довольно сложным решением (через генетический алгоритм) широко известной задачи поиска метаграмм ^[3]: дано два слова (существительных) одинаковой длины, нужно получить из первого второе, меняя только одну букву и получая при этом имеющее смысл слово.

Сальвадор Дали. Искушение св. Антония. 1946. (Фрагмент).
Бельгийский Королевский музей изящных искусств (Брюссель).

Неужели эта задача требует столь сложного решения? Может, это задача ИИ? – Исхожу из определения ^[1]:

к ИИ относятся задачи, которые компьютер решает заметно хуже человека.

(О применении генетических алгоритмов в ИИ см. книгу: Д. Рутковская, М. Пилиньский, Л. Рутковский, Нейронные сети, генетические алгоритмы и нечеткие системы, М.: Горячая линия – Телеком, 2006).

Однако ларчик открывается довольно просто. Пусть длина каждого из заданных слов . Из словаря существительных выписываем все слова длиной . Число найденных слов обозначим . Эти слова будут метками вершин неориентированного графа. Каждую пару вершин, метки которых отличаются на одну букву, соединяем ребром. Для этого перебираем все пары вершин, сравнивая их метки – число пар , число побуквенных сравнений . Далее решаем типовую задачу поиска кратчайшего пути между указанными вершинами графа.

Словарь существительных взял с CD-ROM к книге Сергея Мельникова ^[4], Delphi и Turbo Pascal на занимательных примерах, СПб.: БХВ – Петербург, 2006 (к слову сказать, в этой книге можно найти много остроумных и простых решений подобных, казалось бы, сложных задач со словами):

В словаре перечислены все имена существительные «Орфографического словаря»
(106000 слов, 28-е издание, 1990 г.). [...] Набор текста осуществлён в 1996-98 годах игроками команды «Пузляры» (http://puzzle.ezakaz.ru) — Константином Кнопом, Яковом Зайдельманом, Валерием Тимониным, Виктором Кабановым, Дмитрием Филимоненковым.

Получил:

Число загруженных слов (число вершин графа): 1501
Число ребер: 2402
Решение: (8 слов) муха-мула-кула-кила-килт-киот-клот-клон-слон
Затрачено времени: 4.59 сек.


Вряд ли обычный человек сообразит быстрее. Более того, так как используются алгоритмы, корректность которых строго доказана, то очевидно, что программа гарантированно находит самое короткое решение, если оно существует в рамках данного словаря. А вот человек не сможет доказать, что его решение самое короткое, как и то, что решения не существует. Таким образом, тут компьютер вне конкуренции с человеком, и эта задача — не задача ИИ.

А вот некоторые другие метаграммы:

муха-мура-бура-бора-кора-корн-коан-клан-улан-улар-удар-удав
мышка-мошка-кошка-корка-горка
шило-кило-коло-соло-сало-рало-рыло-мыло
баран-барон-басон-басок-бачок-бочок-борок-порок-порог-ворог-ворот


Над последним решением программа думала уже 25.21сек. Интересно, что граф оказывается несвязным. Так, например, не удалось найти решения для пешка – ферзь.

Можно расширить задачу. Пусть программа находит самые длинные цепочки с заданным числом букв, то есть генерирует головоломки. Для решения этой задачи нужно принять длину ребра нашего графа равной единице и вычислить матрицу расстояний между вершинами. Это можно сделать, например, с помощью алгоритма Флойда-Уоршелла ^[5]. Так, для слов в 11 букв получим:

Число загруженных слов: 3391
Число ребер: 223
Максимальное расстояние: 9
Пары на максимальном расстоянии: закатывание-запихивание, запихивание-наматывание, обсаживание-отматывание, отматывание-отсиживание
Затрачено времени: 3821.45 сек.

Найдем решение для пары запихивание – наматывание:

Решение: (9 слов) запихивание-запахивание-запаривание-заваривание-заваливание-закаливание-накаливание-накалывание-накатывание-наматывание
Затрачено времени: 62.12 сек.


В заключение этой небольшой заметки стоит отметить, что совершенно справедливо программист, приступая к решению новой задачи, пытается использовать похожее известное решение. С ростом популярности методов ИИ они будут все чаще применяться к различным задачам. Но тут требуется особая осторожность – иначе из мелкой алгоритмической мухи может получиться громадный слон.

При этом все сказанное ни в коей мере не стоит воспринимать как критику указанной статьи с генетическим алгоритмом. Автор любой работы имеет безусловное право исследовать любой алгоритм на любой задаче. И такое исследование приносит свою пользу. В частности, благодаря ему стало возможным сравнение, приведенное в этой заметке.

Автор: third112

Источник ^[6]