大量にある画像に人間が優劣を判定し、その結果をソートしたいです。(順位を付けたい)
画像はすでにデジタルデータ化されてパソコンの中にあります。
二つの画像を人間に見せて判断を求める事を繰り返すプログラムを作成しようと思うのですが、人間が行う操作(比較の判断)をなるべく少なくする為には、どのようなソートのアルゴリズムを選択したら良いでしょうか?
ソートのアルゴリズムの説明などを読むと、例えば、「バブルソート」及び「選択ソート」では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で質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
System.IO.Directory.GetFiles...
-
DataGridViewの複数列を連動し...
-
VB.NETでファイル名順にファイ...
-
n番目に大きい数を求めるアル...
-
C言語でファイルの中身をソー...
-
数字文字列のソート方法
-
C# DataGridView のヘッダーセ...
-
DataGridViewのソートを止めたい
-
C# DataTableの行をソートしてD...
-
ファイル名「1.jpg ~10.jpg~...
-
用意されたファイルを読み込む...
-
C++ 入力した3つのint型の整数...
-
Excel VBAで並べ替えをしたい
-
VBScriptで重複レコードを削除...
-
配列の中身を入れ替える方法を...
-
VBA基本構文の作り方 2列の...
-
文字列をソートする方法
-
EXCEL VBAのソートについて
-
n個の要素で出来る順列組み合...
-
ポインタと構造体の利用について
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
System.IO.Directory.GetFiles...
-
C# DataGridView のヘッダーセ...
-
VB.NETでファイル名順にファイ...
-
あるディレクトリ内のファイル...
-
VBA基本構文の作り方 2列の...
-
ファイル名「1.jpg ~10.jpg~...
-
Excelですべての組合せ(重複組...
-
vbでDataTableの抽出コピー
-
C# DataTableの行をソートしてD...
-
listboxの並び替え
-
(VBA) Dir 関数で取得するファ...
-
コレクションの数値をSortで並...
-
C言語・要素除去
-
Fortran77で多次元配列を並び替...
-
C# DataTable ソートについて
-
excel VBA の条件をつけての列...
-
VBScriptで重複レコードを削除...
-
文字列をソートする方法
-
n番目に大きい数を求めるアル...
-
C言語でアナグラムを求めるプロ...
おすすめ情報