4

長さの異なるムービー クリップ ( a1,...,an )の (再生) リスト(A)があります。(A)のクリップからクリップ ( b1,...,bm ) を連結した新しいリスト(B)を作成したいと思います。

(B)のbxが超えてはならないMAX_LENという制限もあります。a 内の隣接するクリップのみを連結できます ( a1+a2+a3は正当な連結ですが、a1+a3はそうではありません)。(A) のすべてのクリップは、 (B)に 1 回表示され、 (A)に表示された順序で表示される必要があります。

最適解プライマリ:

1) (B)のクリップの数を最小限に抑えます。

そして二次：

2) (B)の最短クリップの継続時間を最大化します。

主な制約1)は2)よりも重要であるため、NumOfClips( S1 ) < NumOfClips( S1 )である2 つの異なるソリューションS1およびS2の場合、durationOfShortestClip( S1 ) < durationOfShortestClip( S2 ) であっても、 S1はS2よりも「最適」です。

以下は、入力リスト(A)の 3 つの可能な出力(B1)と(B2)と(B3)を示す例です。( B1 )または(B2)のいずれも1 )を満たさない (ただし、25>23 であるため、 (B2)は(B1)よりも優れたソリューションです) 最適なソリューションは(B3)です。 入力リストと出力リストの例

効率的な方法で最適なソリューションを見つける方法を知りたいですか? 最適なサブ問題の存在または非存在など、その他のヘルプ完全な情報/手がかりも高く評価されます。

4

2 に答える 2

0

欲張りアルゴリズムを使用できる主な制約。（A）の最初の要素クリップを（B）の最初の要素に設定する必要があるため、最初の要素（B）に空きスペースがあり、（A）の2番目の要素クリップがある場合）最初の要素に設定できるのは（B）なので、これを行うか、Bの2番目の要素に設定します。このソリューションを繰り返して、（A）のすべてのクリップを（B）に1回表示します。この結果では、（B）のクリップの数をo（n）で最小化しています。最適なソリューションを得るには、最短の期間を最大化する必要がある2次制約を実現しました。欲張りアルゴリズムがBを提供し、B（i）がリストの最初の要素アイテムであると仮定します。B（i）のクリップがB（i-1）に表示されないことは明らかです。したがって、b（i）の最後のメンバーだけです。 ）はb（i + 1）に表示されます。したがって、移動が（B）の最短クリップの持続時間を最大化するかどうかを確認します。

于 2013-01-08T15:43:31.677 に答える
0

非常に漠然としたアイデアですが、少なくとも問題が多項式であることを証明しています。私の解決策は種類のものO(N^3 * log N * log L)で、L はすべてのクリップの長さの合計です。

まず、適切な最小数のクリップ グループを見つけますG。これは非常に簡単です。最初のグループにできるだけ多くのクリップを配置し、次のグループに進みます。Gこれにより、 (基準 1)の最小値が確実に生成されます。ただし、基準 2) による最適性はまだ見つかっていません。

方法は次のとおりです。

  • と の間のインデックスを持つクリップの iffmat[i][j]を持つ行列を作成し、合計が 未満になります。のその他の値はすべて0 です。mat[i][j] = 1ijMAX_LENmat
  • すべてのグループのクリップ合計の最小値を二分探索します。このステップにより、log L私のアルゴリズムの係数が得られます。特定のステップで選択された値がM
  • matasのコピーを作成しcopy_matます。copy_mat[i][j] = 1 <=> mat[i][j] = 1 and SUM(clips i..j) >= M
  • この行列を、見つかったクリップ グループの数で累乗しますG。行列の乗算はN^3、最も簡単な方法で実装されている場合の係数を与えます。パワーを上げると、追加のlog N要素が追加されます。
  • copy_mat[1][N] = 1で解決策がある場合は、Mそれを増やしてみてください。そうでなければ - 減少します。
  • 二分探索ステップを減らします。

二分探索が終了すると、 の最適値が見つかりますM。正確なグループ化を見つける必要がある場合は、行列の乗算中に 1 つの補助行列を使用する必要がありますが、この最後のビットは自分で把握できるはずです。

私はより速い解決策を考え続けますが、少なくとも私の問題は複雑さが指数関数的ではなく、約1000個のクリップの数で比較的高速に機能することを証明しています.

于 2013-01-08T15:45:31.940 に答える