Как найти наилучший ответ на действительно большую кажущуюся проблему?

Question

Во-первых, это НЕ домашняя проблема. Мне не приходилось делать домашнее задание с 1988 года!

1. У меня есть список слов длиной N
2. У меня есть максимум 13 символов на выбор.
3. Там может быть кратно одной и той же букве

Приведен список слов, из которых 13 символов написали бы наиболее возможные слова. Я могу выбросить слова, которые затрудняют решение проблемы, например:

speedometer has 4 e's in it, something MOST words don't have, 
so I could toss that word due to a poor fit characteristic, or it might just 
go away based on the algorithm

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

Генетические алгоритмы приходят на ум, но я никогда не пробовал их раньше ...

Похоже, мне нужен способ оценить каждую букву, основываясь на ее связи с другими буквами в словах, в которых она находится ...

Answer 1

Звучит как сложная комбинаторная проблема.Вам дан словарь D слов, и вы можете выбрать N букв (возможно с повторениями), чтобы охватить / сгенерировать как можно больше слов в D.Я на 99,9% уверен, что в целом можно показать, что это проблема полной оптимизации NP (при условии, что возможно алфавит, т. Е. Набор букв, содержащий более 26 элементов), путем уменьшения значения SETCOVER, но я оставляю фактическое сокращениев качестве упражнения для читателя:)

Если предположить, что это сложно, у вас есть обычные маршруты:

• ветвь и граница
• стохастический поиск
• алгоритмы аппроксимации

Answer 2

Лучшее, что я могу придумать - это ветвь и связка. Создайте структуру данных «промежуточное состояние», которая состоит из

• Буквы, которые вы уже использовали (с кратностью)
• Количество символов, которые вы все еще можете использовать
• Письма еще доступны
• Слова все еще в вашем списке
• Количество слов в вашем списке (количество в предыдущем наборе)
• Количество слов, которые невозможно в этом состоянии
• Количество слов, которые уже включены в выбранные вами буквы

Вы бы начали с

• Пустой набор
• 13
• {A, B, ..., Z}
• Весь ваш список
• N
• 0
• 0

Поместить эту структуру данных в очередь.

На каждом шаге

Pop an item from the queue
Split into possible next states (branch)
Bound & delete extraneous possibilities

Из состояния я бы сгенерировал возможные следующие состояния следующим образом:

For each letter L in the set of letters left
    Generate a new state where:
        you've added L to the list of chosen letters
        the least letter is L
        so you remove anything less than L from the allowed letters

Так, например, если ваш оставшийся набор равен {W, X, Y, Z}, я бы сгенерировал одно состояние с W, добавленным к моему выбору, {W, X, Y, Z} все еще возможно, один с X в качестве моего выбора, {X, Y, Z} все еще возможен (но не W), один с Y в качестве моего выбора и {Y, Z} все еще возможен, и один с Z в качестве моего выбора и {Z} все еще возможен .

Делайте все различные расчеты, чтобы выяснить новые состояния.

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

Не требуется специального обращения со спидометром.

Не могу представить, что это будет быстро, но это сработает.

Возможно, существует некоторая оптимизация (например, сохраняйте каждое слово в вашем списке как массив AZ числа вхождений и объединяйте слова с одинаковой структурой: 2 вхождения AB ..... T => BAT и TAB ). То, как вы сортируете и отслеживаете минимальное и максимальное значения, также, вероятно, может помочь. Вероятно, этого недостаточно для асимптотической разницы, но, возможно, для проблемы, достаточно большой, чтобы запустить ее в разумное время, а не в экстремальное время.

Answer 3

Должно работать полное перебор, хотя реализация может привести к путанице.

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

Комментарии приветствуются. :)

Answer 4

Я не совсем понял это " У меня есть максимум 13 символов на выбор. ".Если у вас есть список из 1000 слов, значит, вы хотели уменьшить его до 13 символов?!

Некоторые мысли основаны на моем (неправильном) понимании:

Если вы толькообрабатывая английские слова lang, вы можете пропустить гласные, потому что согласные не менее описательны.Наш мозг может как бы заполнять гласные - так называемый язык SMS / Twitter:)

Возможно, для 1-3 буквенных букв, удаление гласных слов приведет к потере слишком большого количества информации.Но все же:

spdmtr hs 4 'snt, smthng MST wdds not hv, sld tss tht wrd dt pr ft chrctrstc, rt mght jst g wy bsd nth lgrthm

Стемминг сократит слова еще короче.Сначала стемминг, затем раздели гласные.Затем сделайте гистограмму ....

Answer 5

Снятие границ для каждого параметра, включая размер алфавита, позволяет легко уменьшить объективную задачу из задачи максимального охвата, которая является NP-трудной и трудной для аппроксимации с отношением лучше, чем (e - 1) / e ≈ 0,632. Его можно фиксировать в алфавитном размере с помощью грубой силы.

Я согласен с предложением Ника Джонсона о грубой силе; в худшем случае, есть только (13 + 26 - 1) выбор (26 - 1) мультимножеств, что составляет всего около 5 миллиардов. Если вы ограничите кратность каждой буквы тем, что может оказаться полезным, это число станет намного меньше. Даже если это слишком медленно, вы сможете перерабатывать структуры данных.