Поиск самого длинного слова по словарю и буквам

Для игры по построению слов, над которой я работаю, у меня есть тройка, в которой хранятся все возможные слова из словаря. На данный момент это около 179 000 человек.

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

Вопрос в следующем: учитывая сетку букв 5x5 и этот словарь, как я могу эффективно определить либо самое длинное слово, которое можно составить, либо список всех возможных слов? Обратите внимание, что буквы не обязательно должны соприкасаться друг с другом, чтобы их можно было использовать; любая из букв сетки в порядке.

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


c++ dictionary search trie
person Daniel Burnett    schedule 26.03.2014    source источник
comment
Вы пробовали метод грубой силы, и производительность была неприемлемой?   -  person Pete    schedule 26.03.2014
comment
Учитывая операции, которые вы хотите выполнить, уверены ли вы, что trie является подходящей структурой данных для использования?   -  person ct_    schedule 26.03.2014
comment
@Pete: я не пробовал, но это было бы факториальное время. Начальная полная сетка 5x5 имеет порядок 25! возможности проверить - слишком неэффективно.   -  person Daniel Burnett    schedule 26.03.2014
comment
@ct_: Я не уверен на 100%, но это лучшее, что я мог придумать... есть другие предложения?   -  person Daniel Burnett    schedule 26.03.2014
comment
@DanielBurnett Я не думаю, что на самом деле метод грубой силы будет где-то рядом с 25! - вы не ожидаете, что будет очень много слов из 25 букв. Конечно, алгоритм не сложно написать для его проверки - по крайней мере, он дает наихудший эталон для проверки других схем, а также предлагает ссылку для проверки их правильности.   -  person Pete    schedule 27.03.2014

Ответы (2)


arrow_upward
0
arrow_downward

Поиск «лучшего» слова всегда потребует некоторого поиска в дереве. Но trie не является ужасной структурой для этого.

Однако вам придется сделать что-то вроде:

  1. Выберите букву с доски.
  2. Найдите узел в дереве для текущего «слова».
  3. Выберите другую букву на доске.
  4. Повторяйте с шага 2 до тех пор, пока: на доске не будет найдено ни одного слова или букв.
  5. Запомните «счет» за слово, которое вы нашли.
  6. Повторите этот процесс для всех (уникальных?) начальных букв на доске.

Возможно, вы захотите проверить, «пробовали ли вы эту последовательность раньше», но я не уверен, что это принесет большую пользу.

Чтобы сделать его достаточно справедливым для конкурента, конкурирующего с компьютером, вы можете ограничить количество попыток, которые делает компьютер, просто потому, что человек, вероятно, никогда не выиграет у компьютера в этом случае.

person Mats Petersson    schedule 26.03.2014

arrow_upward
0
arrow_downward

Я придумал алгоритм, который выполняет O(n) операций на протяжении всей игры, где n — размер словаря. Однако он использует дополнительные структуры данных, и, по всей видимости, простого перебора будет достаточно. Если производительность окажется проблемой, читайте дальше.

Рассмотрим набор слов, которые можно составить из букв на доске. Слова будут удаляться из этого набора на протяжении всей игры по мере удаления букв с доски.

Начальный набор слов можно определить, просмотрев словарь. Слова, буквы которых образуют подмножество букв на доске, действительны. Есть много способов проверить это, например, сравнить отсортированные буквы слова с отсортированными буквами на доске или создать таблицы частоты букв и сравнить их.

Когда буква удаляется, слова, в которых эта буква встречается столько же раз, сколько и на доске до удаления буквы, должны быть удалены из набора. Например, если на доске было два слова e и одно из них было удалено, из набора нужно удалить только слова, содержащие ровно два слова e.

Набор слов можно эффективно поддерживать с помощью связанного списка. Для постоянного доступа к слову с наивысшим баллом список может быть отсортирован в начале с использованием алгоритма сортировки O(n), такого как классическая сортировка. Удаление узлов из списка не нарушит порядок.

Для эффективного удаления всех слов с определенной частотностью обращения к узлам связанного списка хранятся в двумерном массиве. Запись (x, n) массива содержит ссылки на все узлы, слова которых имеют ровно n вхождений буквы x.

Например, ссылки на узел, содержащий слово "глаз", будут храниться в записях ('e', 2) и ('y', 1) массива. Когда на доске есть два элемента e и один из них удаляется, все узлы в записи ('e', 2) удаляются из связанного списка. Если слово уже удалено, оно игнорируется.

Удаление узла из связанного списка выполняется за постоянное время, и каждое слово может быть удалено не более одного раза за всю игру (и может иметь не более 25 дополнительных попыток удаления), что делает весь процесс O(n)< /эм>.

person tom    schedule 26.03.2014
comment
Я никогда не думал сделать это таким образом! Я проверю это, когда у меня будет шанс, но, похоже, это должно работать. Спасибо! - person Daniel Burnett; 26.03.2014