特定の文の最大の重みを見つける必要があるゲームに取り組んでいます。
「the quick brown fox」という文があり、定義された重みを持つ単一の単語のみを想定するとします。「the」-> 10、「quick」-> 5、「brown」-> 3、「fox」-> 8
この場合、解決策は各単語の重みを追加することにあるため、問題は簡単です。
ここで、ダブル ワードも追加すると仮定すると、上記の単語の他に、"the quick" -> 5、"quick brown" -> 10、"brown fox" -> 1 もあるとします。
単一語と二重語のどの組み合わせが最大の重みを提供するかを知りたいです。この場合、「the」、「quick brown」、「fox」になります。
私の質問は、明らかな力ずくのアプローチ以外に、解決策を得る他の方法はありますか? 言うまでもなく、私はより大きな文でこれを達成するための最適な方法を探しています.
ありがとうございました。
lp_solveのような整数線形計画法ライブラリを見ることができます。この場合、スコアを最大化する必要があり、目的関数には重みが含まれます。次に、「クイックブラウン」と「ブラウン」を同時に持つことはできないなど、制約を受けることができます。
単語の配置については、これがこの論文で使用されましたが、問題はそれよりもはるかに単純ですが、この論文を参照して、ILP がどのように使用されたかを理解することができます。これを最適に解決するために使用できる ILP 以外のアルゴリズムはおそらくありますが、ILP は小さな問題に対して最適かつ効率的に解決できます。
これは動的プログラミングの質問のように感じます。
文章の k 個の単語が、各単語の間に電球を挟んで隣り合わせに配置されていることを想像できます (つまり、合計で k-1 個の電球)。電球が点灯している場合は、それに隣接する単語が単一のフレーズの一部であることを意味し、消灯している場合はそうではありません。したがって、これらの電球の任意の構成は、重みの可能な組み合わせを示しています。もちろん、必要なフレーズのスコアがないため、多くの構成は不可能です。したがって、k-1 個の電球は、最大 2^(k-1) 個の可能な答えがあることを意味します。
総当たりではなく、他の計算に再利用できる各計算の部分があることを認識することができます。 .. 怠惰な犬)、(茶色のキツネ ... 怠惰な犬) の最大スコアを一度だけ計算し、それをメモして、次にそれを見たときに余分な作業をせずに再利用できます。
始める前に、まず、可能な値が 1 つしかない電球を取り除く必要があります (「brown fox」というフレーズや、そのフレーズを含むより大きなフレーズがないと仮定すると、「brown fox」の間の電球が削除されます)。 ' および 'fox' は常にオフにする必要があります)..削除された各電球は、ソリューション スペースを半分にします。
w1、w2、w3 が単語の場合、電球は w1w2、w2w3、w3w4 などになります。
Optimal(w1w2 w2w3 w3w4 ...) = max(Optimal(w2w3 w3w4 ...) given w1w2 is on, Optimal(w2w3 w3w4 ...) given w1w2 is off)
(可能な解決策がない場合は注意してください。MIN_INT を返すだけで、うまくいくはずです)
このように問題を解決することもできますが、電球に近づく順序を賢く使えば、おそらくさらに時間を節約できます。最初に中央の球根を攻撃すると役立つかもしれません.. この部分についてはよくわかりません。