2

我正在开发一款游戏，我需要找到特定句子的最大权重。

假设我有句子“the quick brown fox”，并假设单个词和双词都具有定义的权重：“the”-> 10、“quick”-> 5、“brown”-> 3、“fox”-> 8 , “快速” -> 5, “快速棕色” -> 10, “棕色狐狸” -> 1

我想知道单字和双字的哪个组合提供了最大的权重，在这种情况下，它将是“the”、“quick brown”、“fox”（权重 = 28）

有人告诉我这个问题可以通过线性规划来解决，但我看不到如何实现这种方法。具体来说，我不知道如何表达问题的约束，在这种情况下，一些双词不能与包含的单个词组合（即“快速”不能与任何一个组合） "the" 或 "quick")

有人可以就如何解决这个问题提供一些指导吗？我不是该领域的专家，并且对 Simplex 的工作原理有一些基本的了解（从学校回来），但我缺乏关于如何为此类问题建模的知识。

此外，任何其他方法（不涉及线性编程或蛮力）也将受到欢迎。

谢谢。

4

4 回答 4

0

您可以在这里非常有效地使用 DP。

令 F 为最大权重函数，令句子为 w1 w2 w3 .. wk

让 G( [w1 w2 ..]) 返回组合的字典权重。

F([w1 w2 w3...wk]) = Max( G([w1])+ F([w2 w3...wk]), G([w1, w2])+ F([w3 w4.. .wk]) ... )

于 2012-04-11T19:07:46.270 回答
0

您的示例问题的蛮力方法涉及2^7可能的组合 - 让我们看看我们是否可以减少它。为方便起见，让我们映射变量：

the quick brown fox -> (a1, a2, a3, a4)
the quick   -> b1
quick brown -> b2
brown fox   -> b3

其中a3=True表示我们使用的是“棕色”。由此，我们可以构造出一套规则。例如，b3不能与a3or一起使用a4：

(a1:b1)     (b1:a1,a2)
(a2:b1,b2)  (b2:a2,a3)
(a3:b2,b3)  (b3:a3,a4)
(a4:b3)

现在从数组开始S=[a1=0,a2=0,...,b3=0]递归地遍历变量组合，如果分支违反了我们的规则之一，则尽早修剪它。如果我们到达一个叶子节点，则输出与变量对应的权重，如果是迄今为止最大的，则保留它。这可能不是最有效的答案，但它肯定可以减少组合。

于 2012-04-11T17:43:23.793 回答
0

用 from position to的单词调用BiggestWeight(i)子问题，其中是单词的数量。in-1n

  • 你的问题是找到BiggestWeight(0).

  • 基本情况是BiggestWeight(n)，等于0，因为单词列表是空的，并且BiggestWeight(n-1)，等于weight(n-1)，因为对于一个单词的列表只有一个选择。

  • 子问题之间的关系是： BiggestWeight(i) = max(weight(i)+BiggestWeight(i+1), pairWeight(i,i+1)+BiggestWeight(i+2) ) 因为第i-个字要么是单字，要么是双字的第一个。

因此，如果将值存储在大小为的表中n+1，则可以在 中找到结果O(n)。

于 2012-04-11T18:57:55.503 回答
0

假设组合仅由单字和双字组成：

int single[n];//if we choose i-th word : single[i]
int doubles[n];//if we choose the i-th and i+1-th word as a combination : doubles[i], the last word has the same value for it's single and doubles

int dp[n+2];//dynamic programming
dp[n] = dp[n+1] = 0;//bottom up

for(int i=n-1;i>=0;i--)
{
    dp[i]=max(dp[i+1]+single[i],dp[i+2],double[i];
}
//the maximum value is dp[0]
于 2012-04-11T17:30:00.027 回答