- ベストアンサー
比較の回数を少なくする方法
- 比較の回数を少なくする方法について考えています。例えば、10個のリンゴの大きさに順位を付けたい場合、天秤にのせて重さを比較する方法を考えています。しかし、どのように比較すればよいかわかりません。また、リンゴの数が増えた場合の比較の回数の求め方も知りたいです。
- 現在、10個のリンゴの大きさの順位を求めるために天秤を用いて比較していますが、比較回数を少なくしたいです。リンゴの大きさにはユニークな値があり、絶対的な値を求めることはできません。そのため、天秤を使用してリンゴの重さを比較することで順位を求めたいです。どのような方法がありますか？また、リンゴの数が増えた場合の比較回数も知りたいです。
- リンゴの大きさに順位を付けるために、天秤を使用して比較していますが、比較回数を少なくしたいです。リンゴの大きさにはユニークな値があり、絶対的な値を取得する方法はありません。そのため、リンゴの重さを比較して順位を求める方法を考えています。どのような方法がありますか？また、リンゴの数が増えた場合の比較回数も知りたいです。
- 小林 K太郎（@kingfruits）
- お礼率66% (211/319)
- 数学・算数
- 回答数7
- ありがとう数7
- みんなの回答 （7）
- 専門家の回答
質問者が選んだベストアンサー
どうして「ソートについて調べても、あまり役に立たたないというのが実感なんです。」と思うのか不思議です。 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はどの程度の数なんでしょうか？
その他の回答 (6)
- kmee
- ベストアンサー率55% (1857/3366)
繰り返しになるところもありますが。 「順位」という相対的な値を求めるのが、ソートです。 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に依存します。 アルゴリズムの選択を間違えれば、 同じ組合せを何回も評価しなければならない上、比較の総回数も増えます。 アルゴリズムをよく調べてください。効率のいいソートでは、同じ組合せを比較しないように工夫されています。 挿入ソートでは、比較は常に「これまでに順位が決定した物」と「これから順位を決めようとしている物」の組合せです。 マージソートは、トーナメント戦を、負けたチームを吸収しながら勝ち進む感じになります。比較対象は常に「敵チーム」であり、一度対戦した相手は「自チーム」になるので、二度と対戦することはありません。 ソートのアルゴリズム自体は、コンピュータとは関係ありません。 比較回数、組み合わせ、順序等が関係する、数学の一分野です。
お礼
ご認識のあるとおり、繰り返しのご回答でしたね。 ですが、ごかいとうありがとうございました。
- ask-it-aurora
- ベストアンサー率66% (86/130)
御節介とは思いますが，やっぱりソートが何なのかわかっていないようなので老婆心ながらもう一度回答させてもらいます． たぶんあなたの頭のなかではソートアルゴリズムとは次のようになっているのではないかと想像します． [目的] リストの要素を一列になるように並び替えたい [束縛] コンピュータの計算時間を短くしたい [仮定] 計算時間は比較回数に比例する [結論] 比較回数がなるべく少なくなる方法を探そう この比較回数がなるべく少なくなる方法というのが先人たちが工夫してきたソートアルゴリズムたちです． さて以前の質問(参考URL) を見ると本当にしたいことはリンゴの例とは少し違うように思われます．が，もし一定の設定を満たすならば話は同じです： [目的] 大量にある画像を優劣をつけ，一列に並び替えたい [束縛] 比較をする人間への負担を少なくしたい [仮定] 負担は比較回数に比例する [結論] 比較回数がなるべく少なくなる方法を探そう なのでこれはソートの問題です． で，その一定の条件ですがそれは「順序」が全順序であることです．自然言語の「順序」と数学者の使う「順序」という言葉は同じですが，細部が異なります．実際に使うときには本当に全順序になっていると見做してよいのかを検討すべきです．自然言語の「順序」に対応する概念としては半順序（数学者の言う順序は普通コレ），全順序，擬順序などがあります．定義はご自分で調べてください．もし別の順序だったのならソレ用のアルゴリズムを考えるべきです（し，そもそもこれらのどれにもならないかもしれません．人間の負担は一旦，無視して小さな予備実験を行い，どんなデータと向き合っているのかをまずハッキリさせては？）
お礼
ask-it-auroraさん、ご回答ありがとうございます。 測定対象に、相対的な値をつける事が目的です。相対的な値がついてしまえば、ソートについて悩む事は全くないのです。 なので、ソートのロジックに何を採用するかなどは、どうでも好い問題と思えてしまうのですが、比較によって相対的な値を求めるという事の本質がソートであると言う事なのでしょうか。。。
補足
ん～ ＞御節介とは思いますが 本人がそういうだけの事はあるかな。 といった回答でした。 ですがご回答ありがとうございました。
- kmee
- ベストアンサー率55% (1857/3366)
「順位を付ける」ことと「順番に並べる」ことは等価です。 「1位を 求める」ことは「先頭にくるものを探す」ことです。 ソートのプログラムにも、実際に並び変えるのではなく、順位にあたる番号を付与する、というものもあります。 今回の問題は「ソート」について調べるのが正解です。
お礼
kmeeさん、ご回答ありがとうございます。 これはソートの問題であると、他の回答者様の多くもそうご回答頂いたのですが、実際のこれをパソコンを使ってシステム化しようと考えると、なにか違和感を感じるのです。ソートについて調べてみると、コンピューターでソートを行ううえでのアルゴリズムである前提が多く、比較は確かに処理時間を左右するコストであり、比較回数が少ないというのは一つの指標となっているのですが、私が求めているのは、仮に処理全体で所用する時間が遅くても、比較の回数そのものが少ない事が優先されるのです。絶対的な値の取得が、もし済んでいて、それがデータ化されてコンピュータに取り込まれている状態であれば、ソートのアルゴリズムが何であれ処理時間は非常に短い時間であり、それは二つのリンゴを天秤にかけて比較する時間とくらべたら、無に等しい時間です。 なので、ソートを行う過程で、出題に示したようなA：Bの比較を実施した後は、B：Aの比較はしたくないのは無論、A:B、B：Cの比較後、A：Cの比較が不用であれば、そのような比較を人間に求めないようなサポートをコンピュータにやらせたいというのが真の目的です。 と、いいますか、簡素に申し上げれば、ソートについて調べても、あまり役に立たたないというのが実感なんです。
- f272
- ベストアンサー率46% (8477/18147)
10個の並べ替えなら全部で22回の比較で十分です。 キーワードは「Ford-Johnson アルゴリズム」です。
お礼
f272さん、ご回答ありがとうございます。 「Ford-Johnson アルゴリズム」で調べてみます。
- ask-it-aurora
- ベストアンサー率66% (86/130)
> これはソートの問題だとお考えですか？ はい．ソートというとGIFアニメでよくあるピョコピョコ並び替えるのをイメージしがちですが，並び替えというイメージに引きずられないようにもっと抽象的に考えればいいと思います．つまりソートとは「有限集合上に与えられている未知の全順序を決定するアルゴリズム」なので，リンゴ10個の重さの順位づけもソートの問題です． 現実の試合などはするたびに結果が変わり得ますし，相性があって全順序にならなかったりするのでその限りではありませんが．
お礼
ask-it-auroraさん、度々、ご回答ありがとうございました。
- ask-it-aurora
- ベストアンサー率66% (86/130)
検索すべきキーワードは「比較ソート」です．たとえば「マージソート」なんかがお手軽だと思います（僕は手でテストの解答用紙を番号順に並べるときにこんな感じでやりました．）比較回数は大体N*ln(N)くらいです．これについても「計算時間 アルゴリズム」などと検索すればいろいろでるでしょう．
補足
ask-it-auroraさん、ご回答ありがとうございます。 私も当初はソートの問題かと思ってたのですが、これはソートの問題ではないような気がしてきまして、このような質問を数学のカテゴリでしてみました。 まったくもって入れ替えの事を考える必要はなく、比較することにより、最終的な相対的な値を求める事が目的なのです。同じ値どうしによる比較を重複して行いたくないのが目的です。他の例で例えるならば、計りによるリンゴの計測でなく、計測は「試合」のような物と考えてほしいのです。同じ相手との試合をする事無く、一位からビリまで順位をつけるにはどうしたらよいかという問題です。 こう補足してもこれはソートの問題だとお考えですか？
補足
＞あなたが対象としているnはどの程度の数なんでしょうか？ ん～ 実は言いたくないのですが、（言うと何が目的がばれそうで。。ｗ）かなり大きな値です。 比較に所用する時間は一ヶ月以上とかですねｗ