大量にある画像に人間が優劣を判定し、その結果をソートしたいです。(順位を付けたい)
画像はすでにデジタルデータ化されてパソコンの中にあります。
二つの画像を人間に見せて判断を求める事を繰り返すプログラムを作成しようと思うのですが、人間が行う操作(比較の判断)をなるべく少なくする為には、どのようなソートのアルゴリズムを選択したら良いでしょうか?
ソートのアルゴリズムの説明などを読むと、例えば、「バブルソート」及び「選択ソート」ではn(n-1)/2の比較が必要になるそうですが、この比較の回数が最も少ない方法を探しています。
また、例えばA,B,Cの比較に置いて、
A>B、B>Cの比較後にはAとCは比較せずともA>Cの関係が成り立つのですが、こういった事も考慮した上での比較回数の最も少ないソートの方法が知りたいです。
以上、ご指導のほど、よろしくお願い申し上げます。
No.2ベストアンサー
- 回答日時:
比較回数を最小にするという意味なので、
ソーティング・ネットワーク問題に類しています。
この問題は、任意に数については結論が出ていないと思うので、
質問への直接の答えは「ない」ということになるかと思います。
マージソートやクイックソートの比較部を外部化して、
人間へのインターフィスを作るのが現実的かと思います。
MillenniuMさん、ご回答ありがとうございました。
結論として、ソートの比較演算の部分だけ人間にインターフェィスするようにし、ソートのアルゴリズム自体は言語にお任せという方針にしようと思いました。とても参考になるご意見で、そのように考えるキッカケとなりました。ありがとうございました。
No.4
- 回答日時:
人間が優劣を判断すると言うのなら挿入ソートが
有効かもしれません。
#画像に点数を付けて、点数順に並べた画像データ
#に追加・挿入していく
挿入ソート
#二分挿入ソート
http://ja.wikipedia.org/wiki/%E6%8C%BF%E5%85%A5% …
No.3
- 回答日時:
この場合、質問の最後にあるような、
> A>B、B>Cの比較後にはAとCは比較せずともA>Cの関係が成り立つ
という関係が、本当に成り立つかというのが、ひとつのキーになります。
クイックソートというのは、おおざっぱに言えば、
1) ある値をひとつ決める。
2) その値より、「大きいグループ」と「小さいグループ」にグループ分けする
3) それぞれのグループで、同じようにソートをする
という仕掛けです。
たとえば、
1 2 8 4 3 2 だと、適当に4を基準に取ると、
大きいグループ 8
小さいグループ 1 2 3 2
で、小さいグループで、2 を基準に同じことをすると
小さいグループの中の大きいグループ 3
小さいグループの中の小さいグループ 1
で、
1 2 2 3 4 8
とソートができます。
この場合、最初に別れてしまった 1 と 8 は、その後比較されることはありません。
ですから、「大きいグループ」に分類されたデータと、「小さいグループ」に分類されたデータは、このあと、比較されることがありません。
比較回数の少ないソートというのは、こういう風に、「A>B、B>C ならば、A>C」ということが成り立つという前提で、自明な比較を避けるようにしているのです。
AsanoNagiさん、ごかいとうありがとうございました。
>自明な比較を避けるようにしているのです。
知りたかった回答です。
とても参考になりました。ありがとうございました。
No.1
- 回答日時:
比較回数が少ないのはクイックソートやマージソートです。
ランダム性が高ければクイックソートですが、クイックソートの最悪の場合を考慮するとマージソートの方が優秀です(ただしメモリ使用量が大きい)。 どちらも実装はそれほど難しくありません。
ただ、画像の優劣そのものを人間が判断するとなると少々面倒かもしれません。
同じデータ同士の比較をすることもありますので、ある時はA>Bとなったのが次の比較でA<Bとなってはソートすることができません。人間が判断することのブレが無いことが前提です。
http://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC% …
この回答への補足
ok-kanetoさん、ご回答ありがとうございます。
>比較回数が少ないのはクイックソートやマージソートです。
比較回数はn*log2nなのでn(n-1)/2のものより小さいって事ですよね。
人間の判断のゆらぎについては考慮しなくてOKです。そういう前提です。
質問の最後にふれた「A>B、B>Cの比較後にはAとCは比較せずともA>Cの関係が成り立つのですが、」
についてですが、クイックソートおよびマージソートでは、A>B、B>Cの比較後に比較せずとも結論のでているAとCの比較するような局面はあるのでしょうか? あるとした場合、比較処理は人間に要求するのではなく、プログラムにやらせたいので、その部分の実装を考慮したいのです。プログラム的な実装が難しいかどうかは問題ではなく、判断する人間の労力を最小限にしたいのが目的です。
もしかするとソートという考えよりも総当たりトーナメントで最下位まで順位を付ける為に最も効率の良い試合の組み合わせは? という質問の方が良いのかもしれません。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(パソコン・スマホ・電化製品) 挿入ソートとマージソートを比較すると,挿入ソートのほうが計算量は少なく,効率的なアルゴリズムである。 1 2022/11/30 17:31
- 統計学 お世話になっています. x軸は時間(期間)y軸はある値に対する2つのグラフ比較をしますが、私個人の考 2 2023/03/30 11:42
- Excel(エクセル) 結合セルのソートについて 5 2022/04/22 11:57
- BTOパソコン PCの選び方 6 2022/09/11 00:16
- 日用品・生活雑貨 用紙や画用紙のサイズ(A4.四つ切りetc) A4.B4.B5.四つ切り.八つ切り…のサイズを把握し 2 2022/12/29 23:05
- 高校 方程式の証明 5 2022/05/12 09:29
- 日本語 「名詞+的」で「形容動詞」? 9 2023/01/26 18:30
- Visual Basic(VBA) ExcelVBAでDo Until loopのネスト、IF文を使って一致する物と一致しない物としたい 11 2022/12/24 17:46
- 洋画 『GLOCK 19 Gen5 MOS』は、普通の『GLOCK 19 Gen5 』と比較して、画像上、 2 2023/03/06 17:31
- Excel(エクセル) Excelで、ゴルフ場、ボウリング場、フィットネスクラブの利用者数比較をしたいです。 しかしフィット 4 2022/11/20 22:17
関連するカテゴリからQ&Aを探す
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
高速検索アルゴリズムとデータ...
-
VBA基本構文の作り方 2列の...
-
C++ 入力した3つのint型の整数...
-
配列の問題
-
VB.NETでファイル名順にファイ...
-
昇順と降順
-
excel VBA リストビューの行...
-
C# ArrayList内の要素の並べ替え。
-
数字文字列のソート方法
-
10個の整数を入力して小さい順...
-
自己参照型構造体とソート
-
文字列をソートする方法
-
VBScriptで配列のソートをする...
-
C# DataGridView のヘッダーセ...
-
プログラミングについて 配列を...
-
C言語・要素除去
-
あるディレクトリ内のファイル...
-
2次元配列を複数項目でソートし...
-
クイックソートしながら重複要...
-
該当のセルのみを2次元配列に入...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
System.IO.Directory.GetFiles...
-
VB.NETでファイル名順にファイ...
-
C# DataGridView のヘッダーセ...
-
なぜ?counterintuitive
-
ファイル名「1.jpg ~10.jpg~...
-
Excelですべての組合せ(重複組...
-
C# DataTableの行をソートしてD...
-
n番目に大きい数を求めるアル...
-
リスト構造のソートで悩んでま...
-
C言語・要素除去
-
10個の整数を入力して小さい順...
-
VBA基本構文の作り方 2列の...
-
あるディレクトリ内のファイル...
-
excel VBA の条件をつけての列...
-
excel VBA リストビューの行...
-
数字文字列のソート方法
-
Excel VBAで並べ替えをしたい
-
VBScriptで重複レコードを削除...
-
vbでDataTableの抽出コピー
-
構造体配列のソート
おすすめ情報