Как разгадывать кроссворд (NP-Hard)?

В настоящее время я выполняю задание и придерживаюсь определенного подхода.

У меня есть кроссворд, состоящий из пустой сетки (без сплошного квадрата, как в обычном кроссворде) с разной шириной и высотой от 4 до 400 (включительно).

Правила:

  1. Слова являются частью ввода - списка из 10–1000 (включительно) английских слов разной длины.
  2. Горизонтальное слово может пересекать только вертикальное слово.
  3. Вертикальное слово может пересекать только горизонтальное слово.
  4. Слово может пересекать только 1 или 2 других слова.
  5. Каждая буква приносит одно очко.
  6. Слова должны иметь пробел в 1 ячейку сетки, если они не являются частью пересекающегося слова.

Пример:

X X X X X X  
X B O S S X  
X X X X X X

Цель:
набрать максимально возможное количество очков в течение 5 минут.

Пока:
После некоторого исследования я понял, что это проблема NP-Hard. Таким образом, невозможно рассчитать наиболее оптимальное решение, поскольку невозможно изучить каждую комбинацию.

Казалось бы, самым простым решением было бы отсортировать слова по длине и вставить слова с наивысшей оценкой для максимальной оценки (жадный алгоритм).

Мне также рассказали о рекурсивном дереве с узлами, состоящими из альтернативных вставок слов с одинаковой оценкой, и алгоритм ранца, применимый к этой проблеме (не уверен, как будет выглядеть реализация).

Вопросы:

  1. Что позволяет мне проверить максимальное количество комбинаций в течение 5 минут, которое масштабируется в соответствии с максимально возможным списком слов и размером сетки?
  2. Какие эвристики я могу применить при вставке слов?

Между прочим, цель здесь - получить наилучшее возможное решение за 5 минут. За пояснение каждая буква допустимого слова дает 1 балл, таким образом, слово из 5 букв дает 5 баллов.

Заранее спасибо. Я читал много математических обозначений в кроссвордах в течение всего дня, что, кажется, завело меня по кругу.


algorithm knapsack-problem np-hard greedy crossword
person Edmond Dantès    schedule 10.09.2015    source источник
comment
Таким образом, невозможно рассчитать наиболее оптимальное решение, потому что невозможно исследовать каждую комбинацию - вы наверняка используете список слов, чтобы накормить ее? Тогда количество возможных решений конечно. (Это может включать не найденное решение.) Хотя в зависимости от длины вашего списка слов это может занять больше 5 минут.   -  person Jongware    schedule 10.09.2015
comment
Список слов действительно есть.   -  person Edmond Dantès    schedule 10.09.2015
comment
Оценка слов равна количеству букв в слове, поэтому слово из 5 букв приносит 5 баллов. Я действительно сказал, что каждая буква стоит 1 балл.   -  person Edmond Dantès    schedule 10.09.2015
comment
@Sienks: Ах, ты тоже - извини, я плохо понимаю прочитанное. Не стесняйтесь откатывать свое редактирование.   -  person j_random_hacker    schedule 10.09.2015
comment
Я не уверен, что sort the words according to length and inserting the highest scoring words for maximum score - хорошая идея. На самом деле я бы начал с самых коротких (больше вариантов размещения большего количества слов). Помните, максимум 2 перекрестка. А как насчет поиска самой распространенной буквы?   -  person shapiro yaacov    schedule 10.09.2015
comment
Ваша цель - найти то, что дает максимальное количество очков, или просто набрать как можно больше очков за пять минут?   -  person ST3    schedule 10.09.2015
comment
Наилучшее решение (с наивысшей оценкой) за 5 минут.   -  person Edmond Dantès    schedule 10.09.2015
comment
Это действительно кажется интересной проблемой. Вы видели это на каком-нибудь онлайн-форуме или где-то в этом роде?   -  person vish4071    schedule 10.09.2015
comment
Это 1 часть задания, которое я сейчас выполняю. Я пытаюсь использовать это как возможность подтолкнуть себя к тому, чтобы придумать хорошее решение (а не просто какой-то простой жадный алгоритм, придуманный мной).   -  person Edmond Dantès    schedule 10.09.2015
comment
На самом деле, чтобы найти решения таких проблем, вам нужно просто придумать базовую стратегию, применить ее, а затем посмотреть, как она работает. Затем вы продолжаете улучшать его или, если он действительно плох, вы думаете о новом.   -  person vish4071    schedule 10.09.2015
comment
Я работал над множеством таких проблем (которые похожи на кодирование бота для игры), и самое сложное - это разработать эвристику, измеряющую производительность. Это требует некоторого обсуждения и времени. Я бы написал в ответ очень простую стратегию, но всякая импровизация - это то, что вам нужно будет сделать.   -  person vish4071    schedule 10.09.2015
comment
Считается ли буква на перекрестке 1 или 2 очками?   -  person cybersam    schedule 10.09.2015
comment
Каждый персонаж стоит 1 очко.   -  person Edmond Dantès    schedule 11.09.2015

Ответы (2)


arrow_upward
0
arrow_downward

Я бы начал со слова со следующими характеристиками:

  • Он должен иметь максимально возможное количество пересечений.
  • Его длина должна быть такой, чтобы количество слов такой длины было минимальным в списке.

т.е. длина слова должна быть наименее частой и наибольшим количеством пересечений.
Причина такого выбора в том, что он минимизирует дальнейшую возможность выбора слов. например. Выбирается слово размером 9 с двумя дополнительными пересечениями. Эти пересекающиеся слова имеют длину 6 и 5 (скажем). Теперь вы удалили возможность всех тех слов длины 6 и 5, у которых 3-й символ - это 'a', а 2-й символ - 's' (скажем, 'a' и 's' - пересекающиеся буквы).

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

Теперь попробуйте заполнить все слова в этой 1-й выбранной позиции (так как у нее минимальная частота, это должно быть удобно), а затем углубитесь в кроссворд, чтобы заполнить его. Какое бы слово ни принесло больше очков, пока не будет достигнута тупиковая ситуация, должно быть вашим решением. Когда вы зайдете в тупик, вы можете начать с нового слова.

person vish4071    schedule 10.09.2015

arrow_upward
0
arrow_downward

Это кажется действительно интересной проблемой дискретной оптимизации. Вы, конечно, правы; с количеством слов и количеством возможных мест размещения вы не сможете когда-либо исследовать часть пространства.

Кроме того, учитывая 5-минутный лимит времени (довольно короткий), я думаю, вам будет очень сложно использовать любую надежную эвристику. Я думаю, что лучшим вариантом может быть какой-то алгоритм случайной перестановки / имитации отжига.

Если бы я делал это, я бы сначала вычислял кластеры слов, полностью игнорируя саму структуру кроссворда. Возьмите одно слово, найдите второе слово, которое пересекает его. Затем найдите другое слово, которое может вписаться в эту структуру (соблюдая максимум 2 пересечения на слово), и так далее. У вас должно получиться множество из этих кластеров, которые вы можете ранжировать по плотности (количество точек / использованная площадь). Я думаю, вы сможете сделать это относительно быстро.

Затем для части случайной перестановки / имитации отжига для своих ходов я помещал либо кластер, либо неиспользуемое слово в сам кроссворд, либо перемещал существующий кластер / слово. Просто сохраните текущую конфигурацию с наибольшим количеством баллов и верните ее через 5 минут.

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

person DaveTheScientist    schedule 10.09.2015
comment
Если вы просто проигнорируете структуру кроссворда и начнете создавать кластеры как таковые, будет очень много кластеров, которые будет действительно трудно сохранить в первую очередь, и вы скажете, что их можно быстро вычислить. Как вы предлагаете рассчитывать такие кластеры? Я думаю, что создание таких кластеров займет действительно очень много времени. - person vish4071; 11.09.2015
comment
Потому что, скажем, слово длиной 7 имеет 2 e's в позициях 2 и 7. Поскольку e является наиболее часто встречающимся символом, было бы около 300 слов (по крайней мере, в наборе из 1000 слов), имеющих e в некоторой позиции. Какие слова вы предлагаете вставить сейчас? Кроме того, с этими 2 e's, пусть это первое слово будет иметь a и s, тогда как вы предлагаете ему выбрать 2 точки пересечения? - person vish4071; 11.09.2015
comment
Моим инстинктом было бы использовать рекурсивный алгоритм для построения этих кластеров. Выберите одно слово (возможно, самое длинное). Выберите второе слово (возможно, второе по длине). Для каждой возможной точки вставки начните новую рекурсию, добавив третье слово и так далее. Идите, пока не попадете в тупик; теперь у вас есть кластер. Я вполне могу ошибаться, считая, что это займет слишком много времени и потребует слишком много памяти. Но быстрая эвристика могла бы стоить времени, поскольку я думаю, что эти кластеры были бы полезны для решения проблемы. - person DaveTheScientist; 14.09.2015