1

与えられた数値のリスト L = { a1, a2, a3, a4, ... , aN}

問題は、このLを一度だけではなく、アトミックになるまで再帰的に 2 つの部分に分割することです。主なアイデアはこの投稿のようなものですが、再帰的なものを追加しています。

(追加: 6 月 9 日) たとえば、 L = {10, 20, 1, 2} (編集: 6 月 10 日)の場合、解はまず {10, 1, 2} と {20} に分割します。 、次に前者を {1, 2} と {10} に分割し、{1, 2} を {1}, {2} に続けます。これで、L のすべてのメンバーがアトミックになり、分割できなくなりました。

分割後は、ある種の二分木のように見えるはずです。

このように見えるとしましょう..

  (a1 a2 a3 a4)
       /\
      /  \
     /    \
    /      \
 (a1 a2) (a3 a4)
   /\      /\
  /  \    /  \
(a1)(a2)(a3)(a4)

各ノードでの類似度関数は 

abs( sum(left_child) - sum(right_child) ) / sum(itself)

この関数の「合計」に従って、リストを分割する（ツリーを作成する）「最適化された」方法を見つけたいと思います。最上位では、この値は下位の値よりも影響が大きくなる可能性があるため、重みを指定する必要があることに注意してください。

weight(level) * abs( sum(left_child) - sum(right_child) ) / sum(itself)

let levelは、二分木におけるこのノードのレベルです。

時間計算量が O(2^N) の動的計画法を使用して、これを解決できると思います。ただし、このソリューションは私には遅すぎるようです。誰もがより良い解決策を持っていますか?

最適化と近似の両方も大歓迎です。

前もって感謝します。

4

1 に答える 1