4

環境

ユーザーに画像のペアを提示し、どちらを好むかを示す心理テストを実装しています。A キーまたは L キーのいずれかを使用して、好みに応じて応答します。画像の数が非常に多い場合、考えられるすべてのペアを比較することは、個人 (O(n^2)) にとってかなり要求が厳しいものです。

質問

ここではマージソートアルゴリズムをハックして、比較の数を劇的に減らしました。結果は次のとおりです。

function mergeSort(arr)
{
    if (arr.length < 2)
        return arr;

    var middle = parseInt(arr.length / 2);
    var left   = arr.slice(0, middle);
    var right  = arr.slice(middle, arr.length);

    return merge(mergeSort(left), mergeSort(right));
}


function merge(left, right)
{
    var result = [];

    while (left.length && right.length) {
        if (getUserPreference(left[0],right[0])) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

関数getUserPreferenceがユーザーに委任する場所。私は複数のシミュレーションを実行しました（応答が偶然に「間違った」〜1/3の時間になる可能性があり、「間違った」とは、間違ったキーを押して真の好みを入力しないことを意味します）、ソートは次のようにうまく機能するようです次の基準:

  • 出力結果は、ユーザーの好みに十分近い (シミュレートされた)。
  • アルゴリズムは適切なタイミングで停止します。10項目のリストの場合、最大20ステップ。

私が知りたいのは、このアルゴリズムが入力ソリューションを停止または近似することに完全に失敗する可能性があるかどうか、そこにいるアルゴリズムの専門家が教えてくれるかどうかです。

4

1 に答える 1

3

このアルゴリズムが完全に停止しない可能性はありますか?

いいえ。比較がどれほど悪い/間違っている/不幸であっても、アルゴリズムは常に停止します。

アルゴリズムは適切なタイミングで停止します。10 項目のリストの場合、最大 20 ステップ。

10 項目の場合、最良のケースは 15 回の比較、最悪のケースは 25 回の比較です。一般に、マージ ソートは平均的なO(n log n)手順で実行されます。

このアルゴリズムが入力解の近似に完全に失敗する可能性はありますか?

それは、「ユーザーの好みに十分近い」という定義に大きく依存します。そしておそらく重要な間違いは、ユーザーの好みが推移的な関係であると仮定することです。

于 2016-10-25T16:00:54.740 に答える