Сложно ли сделать из мухи слона?
Недавно, перед тем как написать про свои соображения о путях развития ИИ, решил посмотреть, что уже писали об ИИ на Хабре. В числе прочих наткнулся на статью с довольно сложным решением (через генетический алгоритм) широко известной задачи поиска метаграмм: дано два слова (существительных) одинаковой длины, нужно получить из первого второе, меняя только одну букву и получая при этом имеющее смысл слово.
Сальвадор Дали. Искушение св. Антония. 1946. (Фрагмент).
Бельгийский Королевский музей изящных искусств (Брюссель).
Неужели эта задача требует столь сложного решения? Может, это задача ИИ? — Исхожу из определения:
к ИИ относятся задачи, которые компьютер решает заметно хуже человека.
(О применении генетических алгоритмов в ИИ см. книгу: Д. Рутковская, М. Пилиньский, Л. Рутковский, Нейронные сети, генетические алгоритмы и нечеткие системы, М.: Горячая линия — Телеком, 2006).
Однако ларчик открывается довольно просто. Пусть длина каждого из заданных слов 
. Из словаря существительных выписываем все слова длиной . Число найденных слов обозначим 
. Эти слова будут метками вершин неориентированного графа. Каждую пару вершин, метки которых отличаются на одну букву, соединяем ребром. Для этого перебираем все пары вершин, сравнивая их метки — число пар 
, число побуквенных сравнений 
. Далее решаем типовую задачу поиска кратчайшего пути между указанными вершинами графа.
Словарь существительных взял с CD-ROM к книге Сергея Мельникова, Delphi и Turbo Pascal на занимательных примерах, СПб.: БХВ — Петербург, 2006 (к слову сказать, в этой книге можно найти много остроумных и простых решений подобных, казалось бы, сложных задач со словами):
В словаре перечислены все имена существительные «Орфографического словаря»
(106000 слов, 28-е издание, 1990 г.). […] Набор текста осуществлён в 1996–98 годах игроками команды «Пузляры» (http://puzzle.ezakaz.ru) — Константином Кнопом, Яковом Зайдельманом, Валерием Тимониным, Виктором Кабановым, Дмитрием Филимоненковым.
Получил:
Число загруженных слов (число вершин графа): 1501
Число ребер: 2402
Решение: (8 слов) муха-мула-кула-кила-килт-киот-клот-клон-слон
Затрачено времени: 4.59 сек.
Вряд ли обычный человек сообразит быстрее. Более того, так как используются алгоритмы, корректность которых строго доказана, то очевидно, что программа гарантированно находит самое короткое решение, если оно существует в рамках данного словаря. А вот человек не сможет доказать, что его решение самое короткое, как и то, что решения не существует. Таким образом, тут компьютер вне конкуренции с человеком, и эта задача — не задача ИИ.
А вот некоторые другие метаграммы:
муха-мура-бура-бора-кора-корн-коан-клан-улан-улар-удар-удав
мышка-мошка-кошка-корка-горка
шило-кило-коло-соло-сало-рало-рыло-мыло
баран-барон-басон-басок-бачок-бочок-борок-порок-порог-ворог-ворот
Над последним решением программа думала уже 25.21сек. Интересно, что граф оказывается несвязным. Так, например, не удалось найти решения для пешка — ферзь.
Можно расширить задачу. Пусть программа находит самые длинные цепочки с заданным числом букв, то есть генерирует головоломки. Для решения этой задачи нужно принять длину ребра нашего графа равной единице и вычислить матрицу расстояний между вершинами. Это можно сделать, например, с помощью алгоритма Флойда-Уоршелла. Так, для слов в 11 букв получим:
Число загруженных слов: 3391
Число ребер: 223
Максимальное расстояние: 9
Пары на максимальном расстоянии: закатывание-запихивание, запихивание-наматывание, обсаживание-отматывание, отматывание-отсиживание
Затрачено времени: 3821.45 сек.
Найдем решение для пары запихивание — наматывание:
Решение: (9 слов) запихивание-запахивание-запаривание-заваривание-заваливание-закаливание-накаливание-накалывание-накатывание-наматывание
Затрачено времени: 62.12 сек.
В заключение этой небольшой заметки стоит отметить, что совершенно справедливо программист, приступая к решению новой задачи, пытается использовать похожее известное решение. С ростом популярности методов ИИ они будут все чаще применяться к различным задачам. Но тут требуется особая осторожность — иначе из мелкой алгоритмической мухи может получиться громадный слон.
При этом все сказанное ни в коей мере не стоит воспринимать как критику указанной статьи с генетическим алгоритмом. Автор любой работы имеет безусловное право исследовать любой алгоритм на любой задаче. И такое исследование приносит свою пользу. В частности, благодаря ему стало возможным сравнение, приведенное в этой заметке.
