2

特定の文の最大の重みを見つける必要があるゲームに取り組んでいます。

「the quick brown fox」という文があり、定義された重みを持つ単一単語と二重単語の両方を想定するとします。「the」-> 10、「quick」-> 5、「brown」-> 3、「fox」-> 8 、「ザ・クイック」 -> 5、「クイック・ブラウン」 -> 10、「ブラウン・フォックス」 -> 1

単一語と二重語のどの組み合わせが最大の重みを提供するかを知りたいです。この場合、「the」、「quick brown」、「fox」になります (重み = 28)

この問題は線形計画法で解決できると言われましたが、そのような方法を実装する方法がわかりません。具体的には、問題の制約を表現する方法がわかりません。この場合、一部のダブルワードは、含む単一の単語と組み合わせることができないという事実です（つまり、「クイック」はどちらとも組み合わせることができません「ザ」または「クイック」）

この問題にどのようにアプローチするかについて、誰かがガイダンスを提供できますか? 私はこの分野の専門家ではなく、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

positionから までBiggestWeight(i)の単語で副問題を呼び出します。ここで、 は単語の数です。in-1n

  • あなたの問題は見つけることBiggestWeight(0)です。

  • 基本ケースはBiggestWeight(n)、0単語のリストが空であるため、 とBiggestWeight(n-1)等しく、単語がweight(n-1)1 つのリストの選択肢は 1 つしかないため、 と等しくなります。

  • サブ問題間の関係は : 番目の単語が 1 つの単語か、2 つの単語の最初の単語のいずれかであるBiggestWeight(i) = max(weight(i)+BiggestWeight(i+1), pairWeight(i,i+1)+BiggestWeight(i+2) ) ためです。i

したがって、値が size のテーブルに格納されている場合n+1、結果は で見つかりO(n)ます。

于 2012-04-11T18:57:55.503 に答える
0

サンプルの問題に対する力ずくのアプローチには、2^7可能な組み合わせが含まれます。それを減らすことができるかどうか見てみましょう。便宜上、変数をマッピングしましょう。

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

は、「茶色a3=True」を使用していることを示します。これから、一連のルールを構築できます。たとえば、またはb3と組み合わせて使用​​することはできません。a3a4

(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]変数の組み合わせを再帰的にステップ実行し、ルールの 1 つに違反する場合はブランチを早期に刈り込みます。葉ノードに到達したら、変数に対応する重みを出力し、これまでで最大の場合はそれを保持します。これは最も効率的な答えではないかもしれませんが、確実に組み合わせを減らすことができます。

于 2012-04-11T17:43:23.793 に答える