9

編集：うわー、多くの素晴らしい応答。はい、私はこれを遺伝的アルゴリズムによって実行される種類の品質を判断するための適応度関数として使用しています。したがって、評価のコストは重要です（つまり、高速である必要があります。できればO(n)）。

私がいじっているAIアプリケーションの一部として、整数の候補配列をその単調性、別名「ソート性」に基づいて評価できるようにしたいと思います。現在、ソートされた最長の実行を計算し、それを配列の長さで割るヒューリスティックを使用しています。

public double monotonicity(int[] array) {
    if (array.length == 0) return 1d;

    int longestRun = longestSortedRun(array);
    return (double) longestRun / (double) array.length;
}

public int longestSortedRun(int[] array) {

    if (array.length == 0) return 0;

    int longestRun = 1;
    int currentRun = 1;

    for (int i = 1; i < array.length; i++) {
        if (array[i] >= array[i - 1]) {
            currentRun++;
        } else {
            currentRun = 1;
        }

        if (currentRun > longestRun) longestRun = currentRun;
    }

    return longestRun;
}

これは良いスタートですが、ソートされたサブシーケンスの「塊」が存在する可能性を考慮に入れていません。例えば：

{ 4, 5, 6, 0, 1, 2, 3, 7, 8, 9}

この配列は、3つのソートされたサブシーケンスに分割されます。私のアルゴリズムでは、40％しかソートされていないと評価されますが、直感的には、それよりも高いスコアが得られるはずです。この種のもののための標準的なアルゴリズムはありますか？

4

11 に答える 11

5

これは、レーベンシュタイン ダメラウ-レーベンシュタイン距離（配列を並べ替えるのに必要なスワップの数）の良い候補のようです。これは、各アイテムがソートされた配列内のどこからどれだけ離れているかに比例する必要があります。

これは、距離の2乗を合計する単純なルビーアルゴリズムです。これは、ソートの適切な尺度のようです。2つの順序が正しくない要素が交換されるたびに、結果は小さくなります。

ap = a.sort
sum = 0
a.each_index{|i| j = ap.index(a[i])-i 
  sum += (j*j)
}
dist = sum/(a.size*a.size)
于 2010-01-20T19:14:57.370 に答える
3

使用する関数の選択は、使用目的に大きく依存すると思います。あなたの質問に基づいて、遺伝子システムを使用して並べ替えプログラムを作成していると思います。これがランキング関数になります。その場合、実行速度が重要です。それに基づいて、あなたの最長ソートサブシーケンスアルゴリズムはかなりうまくいくと思います. それは、フィットネスをかなりうまく定義する必要があるように思えます.

于 2010-01-20T19:27:51.270 に答える
2

このようなもの？http://en.wikipedia.org/wiki/Rank_correlation

于 2010-01-20T19:16:40.487 に答える
2

ここに私が作ったものがあります。

隣接する値の各ペアについて、それらの間の数値差を計算します。2 番目が 1 番目よりも大きいか等しい場合はsorted合計に追加し、それ以外の場合は合計に追加しunsortedます。完了したら、2 つの比率を取ります。

于 2010-01-20T20:08:22.503 に答える
2

ソートされたすべてのサブシーケンスの長さを計算し、それらを 2 乗して加算します。最大にどの程度強調するかを調整したい場合は、2 以外の累乗を使用してください。

これを長さで正規化する最良の方法がわかりません。長さの 2 乗で割るのがよいでしょうか。

于 2010-01-20T20:10:04.190 に答える
2

おそらく探しているのはKendall Tauです。これは、2 つの配列間のバブル ソート距離の 1 対 1 の関数です。配列が「ほぼソートされている」かどうかをテストするには、ソートされた配列に対してそのケンドール タウを計算します。

于 2010-01-20T20:16:04.000 に答える
1

パンケーキ問題と順列の反転距離を調​​べることをお勧めします。これらのアルゴリズムは、2つの順列（IDと順列文字列）間の距離を見つけるためによく使用されます。この距離測度では、順序値のより多くの塊と、反転（サブシーケンスを増やす代わりに単調に減少する）を考慮に入れる必要があります。多項式時間である近似もあります[PDF] 。

それは本当にすべて、数が何を意味するか、そしてこの距離関数があなたの文脈で意味があるかどうかに依存します。

于 2010-01-20T19:38:59.467 に答える
1

私は同じ問題 (単調性スコアリング) を抱えています。最も効率的なアルゴリズムは で実行されますがO(n log n)、それほど悪くはありません。

質問から例を挙げると、最長の増加シーケンス{4, 5, 6, 0, 1, 2, 3, 7, 8, 9}は{0, 1, 2, 3, 7, 8, 9}(長さ 7) です。おそらく、最長のソート実行アルゴリズムよりも評価が高い (70%) でしょう。

于 2012-02-09T02:04:55.993 に答える
0

メジャーを何に使用するかによって大きく異なりますが、これを行う簡単な方法の 1 つは、配列を標準の並べ替えアルゴリズムにフィードし、並べ替えるために実行する必要がある操作 (スワップおよび/または比較) の数を測定することです。配列。

于 2010-01-20T20:00:40.513 に答える
0

修飾子 Ratcliff & Obershelp を使用したいくつかの実験

>>> from difflib import SequenceMatcher as sm
>>> a = [ 4, 5, 6, 0, 1, 2, 3, 7, 8, 9 ]
>>> c = [ 0, 1, 9, 2, 8, 3, 6, 4, 7, 5 ]
>>> b = [ 4, 5, 6, 0, 1, 2, 3, 7, 8, 9 ]
>>> b.sort()
>>> s = sm(None, a, b)
>>> s.ratio()
0.69999999999999996
>>> s2 = sm(None, c, b)
>>> s2.ratio()
0.29999999999999999

そのため、必要なことを行います。ただし、それを証明する方法がよくわかりません。

于 2010-01-20T20:12:27.610 に答える
0

総ステップ数に対して値を増やしてステップ数をカウントするのはどうですか。それはO(n)。

于 2013-04-12T18:54:21.690 に答える