Решение японских кроссвордов с использованием конечных автоматов, Посов И.А.
Японский кроссворд - это популярная головоломка, которую можно найти в большинстве современных газет и журналов. Японские кроссворды были изобретены в Японии где-то всего 20 лет назад. Иногда их называют иначе: нонограммы, гриддлеры или «рисуй по числам». В этой статье мы посмотрим, что такое японские кроссворды, посмотрим, как их решают люди, и разберём алгоритм автоматического решения кроссвордов, основанный па конечных автоматах. Для демонстрации алгоритма мы будем пользоваться демонстрационной программой из системы DADemo. Задание головоломки состоит в том, чтобы восстановить зашифрованный рисунок. На рис. 1с/ приведён пример японского кроссворда, на рис. 16 приведено его решение.
Нам осталось найти алгоритм, который будет брать некоторую частично заполненную строку и искать в ней новые клетки, которые можно закрасить. Ниже мы разберём такой алгоритм, который будет работать достаточно эффективно. Значит ли это, что и решение для всего кроссворда можно найти эффективно? В статье [1], которую цитируют практически все авторы текстов о японских кроссвордах, показано, что задача «Проверить, имеет ли данный кроссворд решение», является NP-полной. Если не вдаваться в обсуждение понятия NP-полноты, то можно просто сказать, что, вероятно, не существует эффективного (полиномиального по времени) алгоритма для решения японских кроссвордов. Если такой алгоритм найдется, то можно будет эффективно (полиномиального по времени) решать любую NP-полную задачу. Среди этих задач есть задачи намного более полезные для практики, чем японские кроссворды, но найти для них полиномиальный алгоритм пока никому не удалось.
Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Решение японских кроссвордов с использованием конечных автоматов, Посов И.А. - fileskachat.com, быстрое и бесплатное скачивание.
Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу
Скачать - pdf - Яндекс.Диск.
Дата публикации:
Теги: Посов :: кроссворд :: решение :: Япония
Смотрите также учебники, книги и учебные материалы:
Следующие учебники и книги:
- Системные риски здоровью, Прокопенко Ю.И., 2015
- Основы проектирования управляемых оснований с инерциальными чувствительными элементами для контроля гироскопических приборов, Калихман Д.М., 2001
- Теория и практика создания тестов для системы образования, Майоров А.Н., 2001
- Эволюционные методы моделирования и оптимизации сложных систем, Семенкин Е.С., Жукова М.Н., Жуков В.Г., Панфилов И.А., Тынченко В.В., 2007
Предыдущие статьи:
- О поиске гамильтонова цикла методом перебора гамильтоновых подграфов, Гавриков А.В.
- Современные аппараты управления и защиты, Богатырев Н.И., 2016
- Управление жизненными циклами организационно-технических систем, Белов M.B., Новиков Д.А., 2020
- Системы автоматического управления, часть 1, Бархоткин В.А., Кочетков М.П., 2004