Algorithmus zur Bewertung der Monotonie eines Arrays (d Beurteilen des „sortedness“ eines Arrays)

StackOverflow https://stackoverflow.com/questions/2104166

Frage

Bearbeiten : Wow, viele große Antworten. Ja, ich bin mit diesem als Fitness-Funktion, um die Qualität einer Art durch einen genetischen Algorithmus durchgeführt um zu beurteilen. So Kosten-Auswertung wichtig ist (das heißt, es muss schnell sein, vorzugsweise O(n).)

Im Rahmen einer AI-Anwendung ich mit liebäugelt bin, würde Ich mag Lage sein, einen Kandidaten Array von ganzen Zahlen auf der Grundlage seiner Monotonie, um zu bewerten, auch bekannt als seine „sortedness“. Im Moment benutze ich eine Heuristik, die den längsten sortierten Lauf berechnet, und dann teilt, dass durch die Länge des Arrays: 

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;
}

Dies ist ein guter Anfang, aber es funktioniert nicht, die Möglichkeit zu berücksichtigen, dass es möglicherweise „Klumpen“ von sortierten Teilfolgen sein. Z. 

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

Dieses Array in drei sortierten Untersequenzen aufgeteilt. Mein Algorithmus wird es bewerten, da nur 40% sortiert, sondern intuitiv, sollte es eine höhere Punktzahl als die. Gibt es einen Standard-Algorithmus für diese Art der Sache?

War es hilfreich?

Lösung

Ich gehe davon aus, dass die Wahl der Funktion zu verwenden, hängt sehr stark ab, was Sie beabsichtigen, es zu verwenden. Auf der Grundlage Ihrer Frage, ich würde vermuten, dass Sie eine genetische System werden mit einem Sortierprogramm zu erstellen, und dies ist die Ranking-Funktion sein. Wenn das der Fall ist, ist dann eine hohe Ausführungsgeschwindigkeit entscheidend. Auf dieser Grundlage, ich wette, Ihre längste sortierte-Teilfolge Algorithmus wäre ziemlich gut funktionieren. Das klingt wie es Fitness definieren sollte ziemlich gut.

Andere Tipps

Dies scheint ein guter Kandidat für die Levenshtein Damerau-Levenshtein Entfernung - die Anzahl von Swaps erforderlich, um das Array zu sortieren. Dies sollte proportional sein, wie weit jedes Element ist, von wo es in einem sortierten Array sein sollte.

Hier ist ein einfaches Ruby-Algorithmus, der die Quadrate der Abstände summiert. Es scheint ein gutes Maß für sortedness -. Das Ergebnis kleiner sind jedes Mal zwei Out-of-Order erhält Elemente vertauscht 

ap = a.sort
sum = 0
a.each_index{|i| j = ap.index(a[i])-i 
  sum += (j*j)
}
dist = sum/(a.size*a.size)

Hier ist ein ich bildete gerade.

Für jedes Paar von benachbarten Werten, die Berechnung der numerischen Unterschied zwischen ihnen. Wenn die zweiten größer oder gleich die ersten, Hinzufügen, dass der Gesamt sorted, ansonsten den unsorted Gesamt hinzuzufügen. Wenn Sie fertig sind, nehmen Sie das Verhältnis der beiden.

Berechnen Sie die Längen aller sortierten Teilsequenzen, quadratisch sie dann und sie hinzufügen. Wenn Sie kalibrieren möchten, wie viel enphasis Sie auf dem größten setzen, verwenden Sie eine Leistung anders als 2.

Ich bin nicht sicher, was ist der beste Weg, dies durch Länge zu normalisieren, vielleicht teilen sie pro Länge im Quadrat?

Was sind Sie wahrscheinlich suchen, ist Kendall Tau . Es ist eine Eins-zu-Eins-Funktion der Blasensortierung Abstand zwischen zwei Arrays. Zur Prüfung, ob ein Array „fast sortiert“, berechnen ihre Kendall Tau gegen einen sortierten Feld.

Ich würde vorschlagen, Blick auf dem Pancake Problem und die Umkehrabstand der Permutationen. Diese Algorithmen werden oft verwendet, um den Abstand zwischen zwei Permutationen zu finden (die Identität und die permutierte string). Dieses Abstandsmaß ist unter Berücksichtigung der mehr Klumpen, um Werte sowie Umkehrungen (monoton abnehm statt Subsequenzen der Erhöhung). Darüber hinaus gibt es Annäherungen, die sind Polynomzeit [PDF] .

Es ist wirklich alles hängt davon ab, was die Zahl bedeutet, und wenn dieser Abstand Funktion macht Sinn in Ihrem Kontext though.

Ich habe das gleiche Problem (Monotonie Scoring), und ich schlage vor, Sie Longest Erhöhung Subsequence . Der effizienteste Algorithmus läuft in O(n log n), nicht so schlecht.

Unter Beispiel von der Frage, die längsten Sequenz von zunehmenden {4, 5, 6, 0, 1, 2, 3, 7, 8, 9} ist {0, 1, 2, 3, 7, 8, 9} (Länge von 7). Vielleicht besser bewerten (70%) als die am längsten sortiert-run-Algorithmus.

Es hängt stark ab, was Sie beabsichtigen, die Maßnahme zu verwenden, aber eine einfache Möglichkeit, dies zu tun, ist das Array in einem Standard-Sortieralgorithmus zu füttern und messen, wie viele Operationen (Swaps und / oder Vergleiche) notwendig sein getan, um das Array zu sortieren.

Einige Experimente mit einem Modifikator Ratcliff und 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

So Art tut, was es braucht, um. Nicht ganz sicher, wie es zu beweisen, though.

Wie wäre es, die Anzahl der Schritte mit zunehmendem Wert gegenüber der Gesamtzahl der Schritte zu zählen. Das ist O(n).

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top