Составление кроссворда на заданной сетке это NP-Complete?

[novako]

Дана переборная задача:
Сетка квадрат 10 на 10, список слов из разного кол-ва букв, пусть в нем 100000 слов, предположим что в списке есть слова из которых можно составить такой кроссворд, их и надо найти. Сетка при это не имеет черных клеток, т.е. к каждую клетку надо вписать букву. И получится в результате 10 слов по вертикали и 10 слов по горизонтали. Длина каждого слова будет равна 10.

IMHO и не только моё! Что данная зада относится к самому сложному классу задач NPC (NP-Complete). Считается что сегодня решений нет и навряд ли будет найдено в ближайшем будущем. Некоторые ученые передерживаются точки зрения что не будет найдено никогда в силу физических ограничений вселенной.

Вопрос: Может быть я ошибаюсь? Эта конкретная проблема с кроссвордом решена?

[age]

novako
Боюсь разочаровать, но 10-буквенных сочетаний (слов) в русском языке не более 1000. Таким образом, задача сводится к нахождению всех таких перестановок $C_{1000}^{10}= 263 409 560 461 970 000 000 000$ возможных комбинаций. Вводя всевозможные эвристики по лишним сочетаниям (4 гласных подряд или 5 согласных, несочетающиеся комбинации "ы-э" и так далее) число комбинаций можно существенно сократить.
Таким образом, при грамотном подходе задача может быть решена.

[novako]

Во-первых полученная вами оценка это примерно 10^24. Давай те прикинем сколько это секунд на супер компьютере выполняющем 10^15 операций, на сегодня это самый быстрый супер компьютер. и так 24-15=9 т.е. примерно миллиард секунд, это примерно 30 лет. Да может быть решена, но с таким же успехом можно решить и другие NPC задачи, вот только результаты вряд ли будут актуальными.

Да понятно что в русском языке нет такого кол-ва слов из 10 букв. Но даже при том количестве что вы привели. Задача фактически не решаемая.

[venco]

novako в сообщении #227840 писал(а):

Задача фактически не решаемая.

Ну да, при неграмотном подходе - не решаемая. age же имел в виду грамотный подход.

[novako]

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

http://209.85.129.132/search?q=cache:FR_vkbdodyMJ:thue.stanford.edu/puzzle.html+crossword+puzzle+NP-Complete&cd=10&hl=ru&ct=clnk&gl=ua

[K-3]

Эта задача не является массовой, поэтому она не может быть NP-полной.

[novako]

K-3 в сообщении #229302 писал(а):

Эта задача не является массовой, поэтому она не может быть NP-полной.

Да задача частная, но ведь частная задача получается из массовой(общей) путем параметризации параметров. Таким образом следуя вашей логике получается что любую NP задачу можно свести к частной и найти ее решение, что собственно и требуется. Если бы это было так сейчас бы не было не разрешимых задач вообще.

[Yuri Gendelman]

novako в сообщении #229991 писал(а):

K-3 в сообщении #229302 писал(а):

Эта задача не является массовой, поэтому она не может быть NP-полной.

Да задача частная, но ведь частная задача получается из массовой(общей) путем параметризации параметров. Таким образом следуя вашей логике получается что любую NP задачу можно свести к частной и найти ее решение, что собственно и требуется. Если бы это было так сейчас бы не было не разрешимых задач вообще.

Не получается. Вы путаете NP-полноту и NP-трудность.

[novako]

Yuri Gendelman в сообщении #230068 писал(а):

[quote="novako в [url=http://dxdy.ru/post229991.html#p229991]
Не получается. Вы путаете NP-полноту и NP-трудность.

Объясните я не совсем понимаю теперь эту логику. Предположим что задача не массовая. Но из того что Вы написали следует что она тем не менее NP-полная. Как все же есть на самом деле. Для меня важно понять: является ли задача составления кроссворда NP-полной?

[Yuri Gendelman]

novako в сообщении #230070 писал(а):

Предположим что задача не массовая. Но из того что Вы написали следует что она тем не менее NP-полная. Как все же есть на самом деле. Для меня важно понять: является ли задача составления кроссворда NP-полной?

Не следует.
NP-полная задача - из Википедии:

Цитата:

NP-полная задача — это такая задача из класса NP, к которой можно свести любую другую задачу из класса NP. Таким образом, NP-полные задачи образуют в некотором смысле подмножество «самых сложных» задач в классе NP; и если для какой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена также «быстро».

То есть:
- Всякая NP-полная задача является NP-трудной (принадлежит классу NP).
- Не-NP-полная задача может быть NP-трудной, но может и не быть NP-трудной задачей.
Еще раз: задача может не быть NP-полной, но сам этот факт ничего не говорит о ее NP-трудности.

[novako]

Yuri Gendelman в сообщении #230082 писал(а):

novako в сообщении #230070 писал(а):

Предположим что задача не массовая. Но из того что Вы написали следует что она тем не менее NP-полная. Как все же есть на самом деле. Для меня важно понять: является ли задача составления кроссворда NP-полной?

Не следует.
NP-полная задача - из Википедии:

Цитата:

NP-полная задача — это такая задача из класса NP, к которой можно свести любую другую задачу из класса NP. Таким образом, NP-полные задачи образуют в некотором смысле подмножество «самых сложных» задач в классе NP; и если для какой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена также «быстро».

То есть:
- Всякая NP-полная задача является NP-трудной (принадлежит классу NP).
- Не-NP-полная задача может быть NP-трудной, но может и не быть NP-трудной задачей.
Еще раз: задача может не быть NP-полной, но сам этот факт ничего не говорит о ее NP-трудности.

Не совсем согласен! Во-первых Википедия не есть истина в последней инстанции, вот тому пример http://podrobnosti.ua/internet/2009/05/07/600825.html. Во-вторых класс задач P включает в себя NP, который включают в себя классы NP-hard и NP-Complete - ведутся споры, а пересекаются ли классы NP-hard и NP-Complete. Но не смотря на это NP-Complete - это самый сложный класс задач, в него входят переборные задачи, которые аналитическими методами не решить. Так что вопрос открыт.

[Yuri Gendelman]

novako в сообщении #230153 писал(а):

Во-вторых класс задач P включает в себя NP, ...

НЕ включает.
Наоборот, класс P - это подмножество класса NP.

IMHO эта тема - хороший пример для тех, кто считает, что программисту достаточно знать школьную математику.

[novako]

Yuri Gendelman в сообщении #230244 писал(а):

novako в сообщении #230153 писал(а):

Во-вторых класс задач P включает в себя NP, ...

НЕ включает.
Наоборот, класс P - это подмножество класса NP.

Да это так полностью согласен! Однако я не правильно выразился, имелось ввиду что NP входит в PSPACE.

[novako]

Поставлю вопрос таким образом:
Экспоненциальная ли по постановке эта задача? (см. сабж).

[K-3]

Цитата:

Экспоненциальная ли по постановке эта задача?

Экспонента --- эта функция. В вашей задаче нет никакого входного параметра (это и означает, что задача не массовая): размер кроссворда зафиксирован (по крайней мере, ограничен сверху константой), словарь зафиксирован. Поэтому ваша задача решается за константу (может быть, большую).

Как "погрузить" эту задачу в массовую? Да можно разными способами. Причем можно погрузить ее в полиномиальную, а можно - в NP-трудную. Надо только позабоится о том, чтобы такое погружение было естественным.

Например, дано $n$, дан словарь (произвольные "слова" составленные из букв русского алфавита).
Требуется составить кроссворд $n\times n$, заполненный какими-то словами из словаря, или установить, что сделать это невозможно. Это уже массовая задача: входом в ней является n и словарь. Скорее всего, она --- NP-трудная (кажется, что к ней можно свести задачу о покрытии).