选择覆盖最多单词的字母？ [英] Choosing an alphabet that covers the most words?

问题描述

给出一个单词列表和一个最多包含P个字母的字母表，我们如何选择覆盖最多单词的最佳字母表？

Given a list of words and an alphabet that has at most P letters, how can we choose the optimal alphabet that covers the most words?

例如： P = 1的单词 aaaaaa， bb和 bb，由于 b包含两个单词，因此最佳字母为 b。

For example: Given words "aaaaaa" "bb" "bb" with P=1, the optimal alphabet is "b" since "b" covers two words.

另一个示例：给定单词P = 4的 abmm abaa mnab bbcc mnnn，最佳字母是 abmn，因为它覆盖了5个单词中的4个。

Another example: Given words "abmm" "abaa" "mnab" "bbcc" "mnnn" with P=4, the optimal alphabet is "abmn", since that covers 4 of the 5 words.

有没有已知的算法，或者有人可以提出解决该问题的算法？

Are there any known algorithms, or can someone suggest an algorithm that solves this problem?

推荐答案

此问题是NP难题通过减少CLIQUE（这是最密集的k-sub（超图）问题）。给定一个图，请使用不同的字母标记其顶点，并为每个边缘创建一个两个字母的单词。当且仅当我们可以覆盖k个选择2个带有k个字母的单词时，存在一个k-clique。

This problem is NP-hard by reduction from CLIQUE (it's sort of a densest k-sub(hyper)graph problem). Given a graph, label its vertices with distinct letters and, for each edge, make a two-letter word. There exists a k-clique if and only if we can cover k choose 2 words with k letters.

即使对于CLIQUE，算法情况也是grim （在合理的假设下，运行时间必须为n ^ Theta（k）），所以除了确定以外，我不确定该建议什么具有原始位阵列的暴力破解。

The algorithm situation even for CLIQUE is grim (running times must be n^Theta(k) under a plausible hypothesis), so I'm not sure what to recommend other than brute force with primitive bit arrays.

这篇关于选择覆盖最多单词的字母？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！