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

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

Японский кроссворд - это популярная головоломка, которую можно найти в большинстве современных газет и журналов. Японские кроссворды были изобретены в Японии где-то всего 20 лет назад. Иногда их называют иначе: нонограммы, гриддлеры или «рисуй по числам». В этой статье мы посмотрим, что такое японские кроссворды, посмотрим, как их решают люди, и разберём алгоритм автоматического решения кроссвордов, основанный па конечных автоматах. Для демонстрации алгоритма мы будем пользоваться демонстрационной программой из системы DADemo. Задание головоломки состоит в том, чтобы восстановить зашифрованный рисунок. На рис. 1с/ приведён пример японского кроссворда, на рис. 16 приведено его решение.





Нам осталось найти алгоритм, который будет брать некоторую частично заполненную строку и искать в ней новые клетки, которые можно закрасить. Ниже мы разберём такой алгоритм, который будет работать достаточно эффективно. Значит ли это, что и решение для всего кроссворда можно найти эффективно? В статье [1], которую цитируют практически все авторы текстов о японских кроссвордах, показано, что задача «Проверить, имеет ли данный кроссворд решение», является NP-полной. Если не вдаваться в обсуждение понятия NP-полноты, то можно просто сказать, что, вероятно, не существует эффективного (полиномиального по времени) алгоритма для решения японских кроссвордов. Если такой алгоритм найдется, то можно будет эффективно (полиномиального по времени) решать любую NP-полную задачу. Среди этих задач есть задачи намного более полезные для практики, чем японские кроссворды, но найти для них полиномиальный алгоритм пока никому не удалось.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Решение японских кроссвордов с использованием конечных автоматов, Посов И.А. - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Теги: Посов :: кроссворд :: решение :: Япония