比較の回数を少なくする方法

例えば、１０個のリンゴがあるとします。リンゴの大きさに同じ物は無いと仮定します。（大きさはユニーク）

その１０個のリンゴの大きさに順位を付けたいのですが、絶対的な値を取得する「計り」の様な装置は無く、天秤にのせて重さの比較をする事により、順位を求めたいです。（天秤にはリンゴをひとつずつしか乗せられないとします。）

比較の作業をなるべく少なくしたいです。どのように比較したらよいでしょうか？
また、示した例ではリンゴは１０個でしたが、リンゴの数がｎ個になった時の比較の回数の求め方も知りたいです。

以下、完結できてませんが自分のこれまでの考えです。
　ＡＢＣＤＥＦＧＨＩＪ
Ａ□■■■■■■■■■
Ｂ□□■■■■■■■■
Ｃ□□□■■■■■■■
Ｄ□□□□■■■■■■
Ｅ□□□□□■■■■■
Ｆ□□□□□□■■■■
Ｇ□□□□□□□■■■
Ｈ□□□□□□□□■■
Ｉ□□□□□□□□□■
リンゴをA～Jとした場合、■の部分の比較をすれば良いかと考え、
比較回数は、N＊N/2 - Nかなと思ったのですのですが、もっと少ない比較で答えを求める事が可能かと思いました。
なぜかと言うと、例えば、A：B比較後にB：C比較の結果がA＜B、B＜CならA-C比較は不用になると考えたからです。
A：B、B：C比較の結果がA＞B、B＜Cになれば、A：Cの比較は必要になるので確立的要素も必要になるのかとも思います。

どのようなご指導でもかまいません、○○について調べろなどのキーワードをくださるだけでもありがたいです。

以上、よろしくご指導の程、お願い申し上げます。

No.5 ベストアンサー 回答者： f272 回答日時： 2013/12/21 18:46

どうして「ソートについて調べても、あまり役に立たたないというのが実感なんです。

」と思うのか不思議です。
n個のものがあれば，その並び方の数はn!個あります。m回比較して順位が確定するとすれば2^m>=n!です。つまりm>=ceiling(log(n!))ですね。(対数の底は2だとしています。ceilingはそれ以上の整数で最も小さい数です。)
n=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16に対して
ceiling(log(n!))=0,1,3,5,7,10,13,,16,19,22,26,29,33,37,41,45
ですからceiling(log(n!))回で順位が確定する方法があれば，それが最低の回数だと分かるのです。
Ford-Johnson アルゴリズムを使えば比較の回数は
F(n)=0,1,3,5,7,10,13,16,19,22,26,30,34,38,42,46
F(n)=Σ[k=1からnまで](ceiling(log(k*3/4)))
ですからnが11までなら最低回数であることが保証されます。（実はn=12,13,14,15でも最低回数ということが証明されているらしい。）

「実際のこれをパソコンを使ってシステム化」しようとすると，あまりネット上に情報がないので難しいかもしれない。
でも，例えばマージソートを使えば
M(n)=0,1,3,5,8,11,14,17,21,25,29,33,37,41,45,49
で順位付けが完了します。そんなに悪くないでしょ。

一般的なnに対して最も比較回数が少ない方法はわかっていません。したがってプログラム化するにはある程度妥協する必要があります。あなたが対象としているnはどの程度の数なんでしょうか？

この回答への補足

＞あなたが対象としているnはどの程度の数なんでしょうか？
ん～　実は言いたくないのですが、（言うと何が目的がばれそうで。。ｗ）かなり大きな値です。

比較に所用する時間は一ヶ月以上とかですねｗ

補足日時：2013/12/22 22:20

No.7 回答者： kmee 回答日時： 2013/12/22 12:08

繰り返しになるところもありますが。

「順位」という相対的な値を求めるのが、ソートです。
300gのリンゴが「何番目」になるかは、他のリンゴ次第です。

比較ソートで比較するのは、2値の「相対的な関係」です。
ソートのプログラムによくでてくるコードに、次のようなものがあります。

if A[ j ] < A[ i ] then

コンピュータでやっているので、内部では数値計算しているかもしれません。
しかし、やっているのは、 A[j]とA[i]のどちらが大きいか、天秤で調べるようなものです。
「<」という演算子に惑わされているのなら、こういうことです。

if 「A[ j ] と A[ i ] を天秤に乗せて、A[j]が上になった」 then

画像の比較なら、こういうことです

if 「A[ j ] と A[ i ] を表示したら、A[j]が『良い』と判断された」 then

ifの中にこれだけの処理を書ける言語はあまりありませんが、
「Aj と Ai を表示して、Ajが『良い』と判断されたらTrue」という関数 ImageCompareを定義すれば

if ImageCompare(A[ j ], A[ i ] ) then

という、ごくありふれたコードになります。


ソートのアルゴリズムは、一般化すれば次の通りです

1. 目的の合致した Ai, Aj を選ぶ
2. Ai, Aj の大小関係を比較する
3. 2.の結果によって(入れ替え等の)処理を行う。あるいは、何もしない
4. 1～3を必要な回数繰り返す

アルゴリズムの違いは、1,3,4の違いです。
1の違いは、 どんな組み合わせで調べるのか、同じ Ai,Aj の組合せを何回評価する可能性があるのか、に関係します。
4の「必要な回数」は、1に依存します。
アルゴリズムの選択を間違えれば、 同じ組合せを何回も評価しなければならない上、比較の総回数も増えます。

アルゴリズムをよく調べてください。効率のいいソートでは、同じ組合せを比較しないように工夫されています。
挿入ソートでは、比較は常に「これまでに順位が決定した物」と「これから順位を決めようとしている物」の組合せです。
マージソートは、トーナメント戦を、負けたチームを吸収しながら勝ち進む感じになります。比較対象は常に「敵チーム」であり、一度対戦した相手は「自チーム」になるので、二度と対戦することはありません。


ソートのアルゴリズム自体は、コンピュータとは関係ありません。
比較回数、組み合わせ、順序等が関係する、数学の一分野です。

この回答へのお礼

ご認識のあるとおり、繰り返しのご回答でしたね。

ですが、ごかいとうありがとうございました。

お礼日時：2013/12/22 22:18

No.6 回答者： ask-it-aurora 回答日時： 2013/12/21 20:14

御節介とは思いますが，やっぱりソートが何なのかわかっていないようなので老婆心ながらもう一度回答させてもらいます．

たぶんあなたの頭のなかではソートアルゴリズムとは次のようになっているのではないかと想像します．
[目的] リストの要素を一列になるように並び替えたい
[束縛] コンピュータの計算時間を短くしたい
[仮定] 計算時間は比較回数に比例する
[結論] 比較回数がなるべく少なくなる方法を探そう
この比較回数がなるべく少なくなる方法というのが先人たちが工夫してきたソートアルゴリズムたちです．

さて以前の質問(参考URL) を見ると本当にしたいことはリンゴの例とは少し違うように思われます．が，もし一定の設定を満たすならば話は同じです：
[目的] 大量にある画像を優劣をつけ，一列に並び替えたい
[束縛] 比較をする人間への負担を少なくしたい
[仮定] 負担は比較回数に比例する
[結論] 比較回数がなるべく少なくなる方法を探そう
なのでこれはソートの問題です．

で，その一定の条件ですがそれは「順序」が全順序であることです．自然言語の「順序」と数学者の使う「順序」という言葉は同じですが，細部が異なります．実際に使うときには本当に全順序になっていると見做してよいのかを検討すべきです．自然言語の「順序」に対応する概念としては半順序（数学者の言う順序は普通コレ），全順序，擬順序などがあります．定義はご自分で調べてください．もし別の順序だったのならソレ用のアルゴリズムを考えるべきです（し，そもそもこれらのどれにもならないかもしれません．人間の負担は一旦，無視して小さな予備実験を行い，どんなデータと向き合っているのかをまずハッキリさせては？）

参考URL：http://oshiete.goo.ne.jp/qa/8391364.html

この回答への補足

ん～
＞御節介とは思いますが
本人がそういうだけの事はあるかな。　といった回答でした。

ですがご回答ありがとうございました。

補足日時：2013/12/22 22:17

この回答へのお礼

ask-it-auroraさん、ご回答ありがとうございます。

測定対象に、相対的な値をつける事が目的です。相対的な値がついてしまえば、ソートについて悩む事は全くないのです。
なので、ソートのロジックに何を採用するかなどは、どうでも好い問題と思えてしまうのですが、比較によって相対的な値を求めるという事の本質がソートであると言う事なのでしょうか。。。

お礼日時：2013/12/21 20:28

No.4 回答者： kmee 回答日時： 2013/12/20 23:35

「順位を付ける」ことと「順番に並べる」ことは等価です。

「1位を 求める」ことは「先頭にくるものを探す」ことです。

ソートのプログラムにも、実際に並び変えるのではなく、順位にあたる番号を付与する、というものもあります。

今回の問題は「ソート」について調べるのが正解です。

この回答へのお礼

kmeeさん、ご回答ありがとうございます。

これはソートの問題であると、他の回答者様の多くもそうご回答頂いたのですが、実際のこれをパソコンを使ってシステム化しようと考えると、なにか違和感を感じるのです。ソートについて調べてみると、コンピューターでソートを行ううえでのアルゴリズムである前提が多く、比較は確かに処理時間を左右するコストであり、比較回数が少ないというのは一つの指標となっているのですが、私が求めているのは、仮に処理全体で所用する時間が遅くても、比較の回数そのものが少ない事が優先されるのです。絶対的な値の取得が、もし済んでいて、それがデータ化されてコンピュータに取り込まれている状態であれば、ソートのアルゴリズムが何であれ処理時間は非常に短い時間であり、それは二つのリンゴを天秤にかけて比較する時間とくらべたら、無に等しい時間です。

なので、ソートを行う過程で、出題に示したようなA：Bの比較を実施した後は、B：Aの比較はしたくないのは無論、A:B、B：Cの比較後、A：Cの比較が不用であれば、そのような比較を人間に求めないようなサポートをコンピュータにやらせたいというのが真の目的です。

と、いいますか、簡素に申し上げれば、ソートについて調べても、あまり役に立たたないというのが実感なんです。

お礼日時：2013/12/21 00:56

No.3 回答者： f272 回答日時： 2013/12/20 23:18

10個の並べ替えなら全部で22回の比較で十分です。

キーワードは「Ford-Johnson アルゴリズム」です。

この回答へのお礼

f272さん、ご回答ありがとうございます。

「Ford-Johnson アルゴリズム」で調べてみます。

お礼日時：2013/12/21 00:18

No.2 回答者： ask-it-aurora 回答日時： 2013/12/20 23:02

> これはソートの問題だとお考えですか？

はい．ソートというとGIFアニメでよくあるピョコピョコ並び替えるのをイメージしがちですが，並び替えというイメージに引きずられないようにもっと抽象的に考えればいいと思います．つまりソートとは「有限集合上に与えられている未知の全順序を決定するアルゴリズム」なので，リンゴ10個の重さの順位づけもソートの問題です．

現実の試合などはするたびに結果が変わり得ますし，相性があって全順序にならなかったりするのでその限りではありませんが．

この回答へのお礼

ask-it-auroraさん、度々、ご回答ありがとうございました。

お礼日時：2013/12/21 00:19

No.1 回答者： ask-it-aurora 回答日時： 2013/12/20 21:36

検索すべきキーワードは「比較ソート」です．たとえば「マージソート」なんかがお手軽だと思います（僕は手でテストの解答用紙を番号順に並

べるときにこんな感じでやりました．）比較回数は大体N*ln(N)くらいです．これについても「計算時間 アルゴリズム」などと検索すればいろいろでるでしょう．

この回答への補足

ask-it-auroraさん、ご回答ありがとうございます。

私も当初はソートの問題かと思ってたのですが、これはソートの問題ではないような気がしてきまして、このような質問を数学のカテゴリでしてみました。　まったくもって入れ替えの事を考える必要はなく、比較することにより、最終的な相対的な値を求める事が目的なのです。同じ値どうしによる比較を重複して行いたくないのが目的です。他の例で例えるならば、計りによるリンゴの計測でなく、計測は「試合」のような物と考えてほしいのです。同じ相手との試合をする事無く、一位からビリまで順位をつけるにはどうしたらよいかという問題です。　こう補足してもこれはソートの問題だとお考えですか？

補足日時：2013/12/20 21:51