2

区画の内容 (および区画自体) の並べ替え順序を維持しながら、特定の数のほぼ同じサイズの区画に分割したい「ゴツゴツした」一連のアイテムがあります。太陽の下で新しいものは何もないので、問題の適切な名前が欠けているだけだと思います。私の最終目標は、アルゴリズムの Python 実装ですが、少なくとも正しい方向へのプッシュが必要です。

問題は、さまざまな長さのセクションに分割されたテキストがあり、それを一連の公平な読み方に分割したいということです。もちろん、読み取りの順序は同じままでなければなりません。

いくつかの詳細については、2,519 のセクションがあります。最長は 1,876 語、最短は 7 語です。平均の長さは 305 語で、長さの中央値は 242 です。

4

3 に答える 3

5

それがあなたのプログラムを正確に解決するかどうかはわかりませんが、MIT OCW コースのIntroduction to Algorithmsでは、動的プログラミングを使用して行の最適な分割を解決し、テキストがページに沿って適切に埋められるようにします (' word-wrapping ') 、ラテックスと同様です。このビデオの17 分をご覧ください。

このアルゴリズムは、行分割の醜さに基づいてペナルティを定義する関数が与えられた場合に、保証された最適な分割を提供します。講義では、この醜さ関数を と定義し(pagewidth - actual_linewidth)^3ていますが、独自の関数を定義することもできます。アルゴリズムは多かれ少なかれすべての異なる分割の可能性を (スマートな方法で) 試し、最適なものを選択します。DP の主な要件は、問題をサブプログラムに分割できることです。たとえば、n以前の単語の解法に基づいて単語の解法を記述することができn-1, n-2, ...ます。これらのタイプの DP アルゴリズムは通常、O(n^2)またはO(n^3)であるため、NP ハードではありません。

基本的なアルゴリズムに興味がある場合は、講義シリーズ全体を視聴することを強くお勧めします。教師は素晴らしいです。

于 2013-10-11T18:25:51.807 に答える
1

わかりました、これは私の好奇心を刺激したので、単純な悪さヒューリスティックを使用して動的計画法アルゴリズムを作成しましたabs(num_words - avg_words)**3。どんなヒューリスティックでも動作するはずです。出力例は次のとおりです。

>>> section_words = [100, 100, 100, 100, 100, 100, 40000, 100, 100, 100, 100]
>>> def heuristic(num_words, avg):
...     return abs(num_words - avg)**3
... 
>>> print_solution(solve(section_words, heuristic, 3))
Total=41000, 3 readings, avg=13666.67
Reading #1 (  600 words): [100, 100, 100, 100, 100, 100]
Reading #2 (40000 words): [40000]
Reading #3 (  400 words): [100, 100, 100, 100]
>>> print_solution(solve(section_words, heuristic, 5))
Total=41000, 5 readings, avg=8200.00
Reading #1 (  300 words): [100, 100, 100]
Reading #2 (  300 words): [100, 100, 100]
Reading #3 (40000 words): [40000]
Reading #4 (  200 words): [100, 100]
Reading #5 (  200 words): [100, 100]

>>> section_words = [7, 300, 242, 100, 115, 49, 563, 
                     1000, 400, 9, 14, 300, 200, 400, 
                     500, 200, 10, 19, 1876, 100, 200, 
                     15, 59, 299, 144, 85, 400, 600, 534, 200, 143, 15]
>>> print_solution(solve(section_words, heuristic, 10))
Total=9098, 10 readings, avg=909.80
Reading #1 (  649 words): [7, 300, 242, 100]
Reading #2 (  727 words): [115, 49, 563]
Reading #3 ( 1000 words): [1000]
Reading #4 (  723 words): [400, 9, 14, 300]
Reading #5 (  600 words): [200, 400]
Reading #6 (  729 words): [500, 200, 10, 19]
Reading #7 ( 1876 words): [1876]
Reading #8 (  902 words): [100, 200, 15, 59, 299, 144, 85]
Reading #9 ( 1000 words): [400, 600]
Reading #10 (  892 words): [534, 200, 143, 15]

>>> print_solution(solve(section_words, heuristic, 5))
Total=9098, 5 readings, avg=1819.60
Reading #1 ( 2376 words): [7, 300, 242, 100, 115, 49, 563, 1000]
Reading #2 ( 2023 words): [400, 9, 14, 300, 200, 400, 500, 200]
Reading #3 ( 1905 words): [10, 19, 1876]
Reading #4 ( 1302 words): [100, 200, 15, 59, 299, 144, 85, 400]
Reading #5 ( 1492 words): [600, 534, 200, 143, 15]

>>> print_solution(solve(section_words, heuristic, 3))
Total=9098, 3 readings, avg=3032.67
Reading #1 ( 3099 words): [7, 300, 242, 100, 115, 49, 563, 1000, 400, 9, 14, 300]
Reading #2 ( 3205 words): [200, 400, 500, 200, 10, 19, 1876]
Reading #3 ( 2794 words): [100, 200, 15, 59, 299, 144, 85, 400, 600, 534, 200, 143, 15]

これがコードです。ただし、良い練習のために自分で実装することをお勧めします!

サブ問題は次のとおりです。セクションを読み値でR(n, i, j)分割することの最も悪い点は何ですか?ijn

基本ケースは単純です:

R(1, i, j) = heuristic(num words in sections i thru j, total words / total sections)

次に、再帰のために、残したセクションの数を左右に分割するすべての可能な方法から最適なソリューションを見つけ、そのパーティションを配置するのに最適な場所を見つけます。

R(n, i, j) = the lowest badness out of
    R(1, i, i+1) + R(n-1, i+1, j)
    R(1, i, i+2) + R(n-1, i+2, j)
    ...
    R(1, i, j-1) + R(n-1, j-1, j)

    R(2, i, i+1) + R(n-2, i+1, j)
    R(2, i, i+2) + R(n-2, i+2, j)
    ...
    R(2, i, j-1) + R(n-2, j-1, j)

    ...
    ...

    R(n-1, i, i+1) + R(1, i+1, j)
    R(n-1, i, i+2) + R(1, i+2, j)
    ...
    R(n-1, i, j-1) + R(1, j-1, j)

病的なケースは、セクションよりも多くの読み取り値がある場合です。

R(n, i, j) = infinity if n > j-i

ソリューションを構築してn=1いきj-i = 1ますi=0。

最終的に 5 つの入れ子になった for ループを持つことになるので、可能な限り効率的かどうかはわかりませんが、うまくいくようです。

于 2013-10-11T20:05:28.753 に答える
1

これにより、「貪欲な」戦略である「OK」の結果が得られるはずです。

  • あなたが目指している平均値を計算してくださいavg = total_words / num_readings。
  • セクションの反復を開始し、これまでの単語数を累積します。
  • 完全に一致した場合は、そのセクションをマークして次に進みます。
  • それ以外の場合は、単語数を超えようとしている場合は、平均に近いものに基づいて、次のセクションを含めるかどうかを選択します。する場合は、そのままにしておきます。

それよりもうまくやるには、ヒューリスティックが必要です。1 つの巨大なセクションと多数の小さなセクションなど、入力を台無しにした場合は、次のように言います。

100 100 100 100 100 100 40000 100 100 100 100

そして、それを 5 つのセクションに分割したいのですが、出力をどのように見せたいですか? 私のアルゴリズムはあなたにこれを与えるでしょう：

100 100 100 100 100 100
40000
100 100 100 100
0
0

セクションごとに少なくとも 1 つの単語を強制するように簡単に適応させることができます。

100 100 100 100 100 100
40000
100 100
100
100

しかし、それはこのオプションほど「良い」ものではないかもしれません:

100 100 100
100 100 100
40000
100 100
100 100

はい、バスが提案した講義をチェックすることをお勧めします。ヒューリスティックを少し調整する必要があります。たとえば、1 つのセクションに複数の単語を含めることは問題ありませんが、ライン パッキングの場合は、それを超えると限りなく悪いことになります。

于 2013-10-11T18:25:53.813 に答える