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

質問

次のような問題を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.92

amanojaku1

>変数がレジスターに割り当てられてないと、パイプライン・ハザード(パイプラインの停止状態)が発生するので、その場合は最大値最小値を条件付分岐で記述した方がパフォーマンスが良くなります。

これは最大値最小値の場合であって、他の処理でも同様ではありません。

回答No.91

amanojaku1

>変数がレジスターに割り当てられてないと、パイプライン・ハザード(パイプラインの停止状態)が発生するので、その場合は最大値最小値を条件付分岐で記述した方がパフォーマンスが良くなります。

CPUのレジスターの数に依存し、コンパイラーのレジスターの割り当てに依存し、パフォーマンスの良し悪しが変わります。

回答No.90

amanojaku1

条件付分岐で分岐予測が外れた場合、パイプラインのStall(ストール：停止状態)が発生します、これは製造ラインの製品の製造が失敗し、それを破棄すると言うことになります。
それなら条件付分岐自体を使わないで記述すれば製品の破棄はなくなります。
その どちらかが筋立てとしてスマートか と言うだけの話です。
ただし、実際は それほど単純ではなく、変数がレジスターに割り当てられてないと、パイプライン・ハザード(パイプラインの停止状態)が発生するので、その場合は最大値最小値を条件付分岐で記述した方がパフォーマンスが良くなります。
これらはパフォーマンスの良し悪しが変わるだけで、ハードに依存して実行結果が変わる訳ではありません。
そもそも条件付分岐で分岐予測が外れた場合、製品の製造が失敗して(そして その製品を破棄して)いますが、それでもハードに依存して実行結果が変わる訳ではありません。

回答No.89

amanojaku1

>gmmin = (gmt[m] & (-(long long)(gmt[m]<gmmin))) | (gmmin & ~(-(long long)(gmt[m]<gmmin)));
>gmmax = (gmt[m] & (-(long long)(gmmax<gmt[m]))) | (gmmax & ~(-(long long)(gmmax<gmt[m])));

「<」：係演算子、「&、|、~」：ビット演算子、「-」：四則演算子と、どれも非常に単純な演算子だけです、これでハードに依存したりしません。
もちろんBasic系のように「(long long)(gmt[m]<gmmin))」が真の時に「-1」になる場合はマイナスしてはダメですが。

回答No.88

amanojaku1

>変数がレジスターに割り当てられてないと、パイプライン・ハザード(パイプラインの停止状態)が発生する

これは、変数がレジスターに割り当てられてないと、(コードを条件付分岐自体を使って記述しようが、コードを条件付分岐自体を使わないで記述しようが)パイプライン・ハザード(パイプラインの停止状態)が発生する、と言う意味です。

回答No.87

amanojaku1

>それなら条件付分岐自体を使わないで記述すれば製品の破棄はなくなると言うだけの事です。

つまり、条件付分岐自体を使わないで記述した方が、コードとしては筋立てが良いと言うことです。
ただし、実際は それほど単純ではなく、変数がレジスターに割り当てられてないと、パイプライン・ハザード(パイプラインの停止状態)が発生するので、その場合は最大値最小値を条件付分岐で記述した方がパフォーマンスが良くなります。

回答No.86

amanojaku1

>それってかなり環境依存ではないでしょうか？CPUの構造やバスの通信規格など複合的なハード条件に左右されると思います。

もしかして、Stall(ストール：停止状態)云々のことを言ってますか？
あれはパイプラインの問題です。
条件付分岐で分岐予測が外れた場合、パイプラインのStall(ストール：停止状態)が発生します、これは聖像ラインの製品の製造が失敗し、それを破棄すると言うことになります。
それなら条件付分岐自体を使わないで記述すれば製品の破棄はなくなると言うだけの事です。
ただし、実際は それほど単純ではなく、変数がレジスターに割り当てられてないと、パイプライン・ハザード(パイプラインの停止状態)が発生するので、その場合は最大値最小値を条件付分岐で記述した方がパフォーマンスが良くなります。
これらはハードの話に聞こえるかも知れませんが(まあ実際ハードの話ですが)、ハードに依存して実行結果が変わる訳ではありません(パフォーマンスが良くなるか悪くなるかと言うだけの話です)。
そもそも条件付分岐で分岐予測が外れた場合、製品の製造が失敗していると言うことに注意して下さい、それでもハードに依存して実行結果が変わる訳ではありません。

回答No.85

amanojaku1

>「(long long)(gmt[m]<gmmin))」が真の時に「1」なら(signedなら)マイナスにすれば「-1」と言うだけのことです((signedなら)「-1」と言うのは全ビット「1」と言う事)。

CPUは整数の加算・減算を「2の補数」で計算します(これはCPUの普遍的な仕様と言って良いほどの決まりごと)。
「2の補数」で「-1」と言うのは全ビット「1」と言う事です。

回答No.84

amanojaku1

>CPUのレジスターの数に依存し、コンパイラーのレジスターの割り当てに依存します(自分でregister指定子を指定することでパフォーマンスが改善する可能性があるかもしれないと言う視点を持っていて損はないでしょう)。

パフォーマンスの良し悪しが、CPUのレジスターの数に依存し、コンパイラーのレジスターの割り当てに依存すると言う意味で、コード自体はハードに依存してません。

回答No.83

amanojaku1

>>それってかなり環境依存ではないでしょうか？CPUの構造やバスの通信規格など複合的なハード条件に左右されると思います。

>CPUのレジスターの数に依存し、コンパイラーのレジスターの割り当てに依存します(自分でregister指定子を指定することでパフォーマンスが改善する可能性があるかもしれないと言う視点を持っていて損はないでしょう)。

コード自体はハードに依存してません。
「(long long)(gmt[m]<gmmin))」が真の時に「1」なら(signedなら)マイナスにすれば「-1」と言うだけのことです((signedなら)「-1」と言うのは全ビット「1」と言う事)。
よってコード自体は全くハードに依存してません。
もちろんBasic系のように「(long long)(gmt[m]<gmmin))」が真の時に「-1」になる場合はマイナスしてはダメですが。