数値を複数の群に分ける最適な組み合わせを求める方法

質問

次のような問題をCで記述するにはどのようにすればいいでしょうか？

要素数が不定の整数値配列がある。
この配列の各要素を、与えられた個数の群に分ける。
条件として、与えられた数値列で隣り合う数値しか同じ群に含めることは出来ない。

例：
数値列は{5,2,7,12,6,15,4}
群の個数を3とする。

(1) {5,2},{7,12,6},{15,4}
(2) {5},{2,7},{12,6,15,4}
(3) {5,2,7},{12},{6,15,4}
・・・

と複数の組み合わせがある。
これらの組み合わせのうち、各群の合計値が最も均等になるような組み合わせを求める。最大値と最小値の差が最小となる組み合わせを最も均等と考える。

上の例であれば、各群の合計値と、合計値の最大値と最小値の差は、

(1) {5,2},{7,12,6},{15,4} ==> 7,25,19 (25-7=18)
(2) {5},{2,7},{12,6,15,4} ==> 5,9,37 (37-5=32)
(3) {5,2,7},{12},{6,15,4} ==> 14,12,25 (25-12=13) ☆

のようになり、この３つの中で最も均等なのは

(3) {5,2,7}{12}{6,15,4}

となる。
実際は、これ以外の組み合わせでより均等となるものがあるかと思います。

この問題そのものが必要なわけではなく、この結果を利用して別のある問題を解決しようとしています。

数値の数が増えると組み合わせの数も大幅に増えて計算時間に影響すると思います。
全ての組み合わせを試すことなく答えにたどり着く方法があれば、考え方だけでも提示頂ければと思います。

回答No.27

amanojaku1 · ベストアンサー

>回答No.23　amanojaku1

「2018/06/15 03:48:47」の時点で修正しました。
それ以前にコピーしている場合は注意して下さい。

数値を複数の群に分ける最適な組み合わせを求める方法
http://ashtarte.pa.land.to/utf8/smt.cgi?r+sara/&bid+000000DC&tsn+000000DC&bts+2018/06/15%2002%3A04%3A46&

お礼

コメント追加して頂きありがとうございます。今頑張って理解しているところですが、何となく分かってきました。

それにしても２進数の数学的特徴をうまくこの問題に当てはめるという発想が凄いですね。問題の本質は順列のパターンを網羅することですが、私は再帰を使うイメージしかなかったです。

回答No.42

amanojaku1

>C++で書き直したコードを載せます。行数の関係上、デバッグ出力部は省略しています。C++11な環境でしかビルド出来ないかも知れません。
>このコードで私の環境では2000万パターンを超えても５秒程度で結果が出ました。

>行数の関係上、デバッグ出力部は省略しています。

と言う事はデバッグ出力が残ってますか？、デバッグ出力で時間が掛かっている可能性があります、(ループ内にある)デバッグ出力は下記のように「#if～#endif」で囲ってみて下さい(ちなみに最適化は有効になってますか？)。

define hoge 0　←デバッグ時は1以上に設定
#if (0<hoge)
デバッグ出力
#endif

詳細は下記参照。

ロベールのC＋＋教室 - 第18章 if...2 - - Biglobe
http://www7b.biglobe.ne.jp/~robe/cpphtml/html03/cpp03018.html

お礼

説明不足でした。計測時はデバッグ出力は全て無効化しています。最適化は最大の/O2としています。この状態で2000万パターンが５～６秒程度でした。コードもかなり最適化したつもりですが、まだ計算量を減らせる部分があるでしょうか。

回答No.41

amanojaku1

>肝は どのパラメータを使うか、と言うか この手法が使えるパラメータを選択できるか(イメージできるか)です。
>
>例えばgmqとgmpは別の表現方法で本質は同じモノですが、gmpでは この手法は使えません。

gpaのパターンの2回目の桁の繰り上がりを する前までをイメージするとgmpでは この手法は使えない事がわかります、そこで このパターンに対応できるgmqが必要だろうと考えられます。
つまり何も無い所から このパターンをイメージできるかが肝になります。

5, | 2, | 7, | 12,6,15,4,
5,2, | 7, | 12, | 6,15,4,
5,2,7, | 12, | 6, | 15,4,
5,2,7,12, | 6, | 15, | 4,
5, | 2,7, | 12, | 6,15,4,
5,2, | 7,12, | 6, | 15,4,
5,2,7, | 12,6, | 15, | 4,

回答No.40

amanojaku1

>この手の応用力は訓練で磨くというより直観なんでしょうか。アルゴリズムに慣れた人なら何てことはないのでしょうが、普通に情報数学を勉強した程度の頭では現実の問題に応用するのは難しいです。

そこよりも、下記の方が重要です(もし、gmqを思いつかなければ この手法は使えないので)。

>肝は どのパラメータを使うか、と言うか この手法が使えるパラメータを選択できるか(イメージできるか)です。
>
>例えばgmqとgmpは別の表現方法で本質は同じモノですが、gmpでは この手法は使えません。

回答No.39

amanojaku1

>4桁が難しいなら、3桁の一部のパターンをイメージすれば良いでしょう。

桁数が多くて難しい場合は、桁数を減らして一部のパターンをイメージすれば良いでしょう。

回答No.38

amanojaku1

>この手の応用力は訓練で磨くというより直観なんでしょうか。アルゴリズムに慣れた人なら何てことはないのでしょうが、普通に情報数学を勉強した程度の頭では現実の問題に応用するのは難しいです。

人には得意・不得意と言うのがあるようで、Ｎ進数の応用は割りとできる方です。

>1,1,1,3
>2,1,1,2
>3,1,1,1
>4,1,1,0

↑この部分のパターンを見れば、最上位桁がゼロの場合に桁の繰り上がりが必要と言うのが分かります。
(全てのパターンを考える必要はありません)4桁が難しいなら、3桁の一部のパターンをイメージすれば良いでしょう。

回答No.37

amanojaku1

>ちなみにgmqの最上位桁がゼロの場合が桁の繰り上がり条件と言うのは非常に稀です。
>恐らく今後 一生 なかなか お目にかかれないアルゴリズムと言って良いでしょう。

つまり、gmqの最上位桁がゼロの場合が桁の繰り上がり条件と言うアルゴリズムは、今後 役に立つ機会は殆ど無いだろうと思われます。

回答No.36

amanojaku1

ちなみにgmqの最上位桁がゼロの場合が桁の繰り上がり条件と言うのは非常に稀です。
恐らく今後 一生 なかなか お目にかかれないアルゴリズムと言って良いでしょう。

回答No.35

amanojaku1

肝は どのパラメータを使うか、と言うか この手法が使えるパラメータを選択できるか(イメージできるか)です。

例えばgmqとgmpは別の表現方法で本質は同じモノですが、gmpでは この手法は使えません。

>自分なら最上位桁のさらに上に計算用の桁を追加してしまいそうですが

この場合は たまたまgmqの最上位桁がゼロが有り得ない値なので、そのまま使えましたが、場合によってはオバーフロー用の桁を追加したり、オバーフロー用のフラグ変数を別途用意する必要があります。

回答No.34

amanojaku1

>ざっくりとしたアルゴリズムは
>kの初期値は「0」
>kが示す「gmqの桁」(gmq[k])に1を加算
>下位の桁は1クリア
>gmqの最上位の桁(gmq[gp-1])の値を算出
>ついでにgmq要素の値を算出
>gmqの最上位の桁(gmq[gp-1])の値を算出、ゼロならループする(その場合kは加算(k++)される)

ざっくりとしたアルゴリズムは
kの初期値は「0」
kが示す「gmqの桁」(gmq[k])に1を加算
下位の桁は1クリア
gmqの最上位の桁(gmq[gp-1])の値を算出
ついでにgmq要素の値を算出
gmqの最上位の桁(gmq[gp-1])の値を算出、ゼロなら「k<(gmq.length-1)」までループする(その場合kは加算(k++)される)
ループ条件が「k<gmq.length」ではなく「k<(gmq.length-1)」になっている事に注意して下さい。
breakせずにループが完了した場合は、gmq要素の最上位の桁(gmq[gp-1])がゼロ(gmqがオバーフロー)となります

お礼

N=6, GC=4で全パターンを並べてみました。
この場合は３桁の３進数ですね。

1,1,1,3
2,1,1,2
3,1,1,1
4,1,1,0
1,2,1,2 <=２桁目に繰り上がり
2,2,1,1
3,2,1,0
1,3,1,1
2,3,1,0
1,1,2,2 <=３桁目に繰り上がり
2,1,2,1
3,1,2,0
1,2,2,1
2,2,2,0
1,3,2,0
1,1,3,1
2,1,3,0
1,2,3,0
1,1,4,0 <=繰り上がり完了

実際に全パターンを並べてみれば、これがＮ進数を加算した時の各桁の並びに等しいことが分かりますね。
ただこの問題の場合は普通のＮ進数と異なり、無の桁が０ではなく１となるのでイメージしにくいのでした。全体的に１を引けば普通のＮ進数ですね。
最上位桁が０になることをもって桁上がりを判定するなど、面白いテクニックが詰まっていると思います。
この手の応用力は訓練で磨くというより直観なんでしょうか。アルゴリズムに慣れた人なら何てことはないのでしょうが、普通に情報数学を勉強した程度の頭では現実の問題に応用するのは難しいです。

ともあれ大変勉強になりました。他の方の解法もあるかも知れませんので、もうしばらくオープンにしておきます。

回答No.33

amanojaku1

>k=2; gmq[k]=2;　←「k=2」なので「gmq[2]++」で「gmq[1]=1」、下位の桁は1クリア

k=2; gmq[k]=2;　←「k=2」なので「gmq[2]++」で「gmq[2]=2」、下位の桁は1クリア