Algoritmo per la valutazione del monotonia di una matrice (cioè giudicare la “sortedness” di un array)

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

Domanda

Modifica : Wow, molti grandi risposte. Sì, sto usando questo come una funzione di fitness per giudicare la qualità di una specie effettuata da un algoritmo genetico. Così costo della valutazione è importante (cioè, deve essere veloce, preferibilmente O(n).)

Come parte di un programma AI sto accarezzando, mi piacerebbe essere in grado di valutare una serie di interi candidato in base alla sua monotonia, alias la sua "sortedness". Al momento, sto usando un euristica che calcola la più lunga ordinato, e poi divide che entro la lunghezza dell'array: 

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

Questo è un buon inizio, ma non riesce a prendere in considerazione la possibilità che ci possa essere "ciuffi" di ordinati sub-sequenze. Per esempio:. 

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

Questa matrice è suddivisa in tre filtrate sottosequenze. Il mio algoritmo tariffa come solo il 40% ordinato, ma intuitivamente, dovrebbe ottenere un punteggio più alto di quello. Esiste un algoritmo standard per questo genere di cose?

È stato utile?

Soluzione

Mi aspetto che la scelta della funzione da usare dipende fortemente da ciò che si intende utilizzare per. Sulla base della sua domanda, direi che si sta utilizzando un sistema genetico per creare un programma di ordinamento, e questo è quello di essere la funzione graduatoria. Se questo è il caso, allora la velocità di esecuzione è importante. Sulla base di questo, scommetto che il vostro algoritmo più lungo-ordinato-sottosequenza avrebbe funzionato abbastanza bene. Che suona come dovrebbe definire il fitness abbastanza bene.

Altri suggerimenti

Questo mi sembra un buon candidato per Levenshtein Damerau-Levenshtein distanza - il numero di swap necessari per ordinare l'array. Questo dovrebbe essere proporzionale alla parte di ciascuno articolo è da dove dovrebbe essere in un array ordinato.

Ecco un algoritmo di rubino semplice che somma i quadrati delle distanze. Sembra una buona misura di sortedness -. Il risultato diventa più piccolo ogni volta due out-of-order elementi sono scambiati 

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

Ecco quello che ho appena inventato.

Per ogni coppia di valori adiacenti, calcolare la differenza numerica tra loro. Se il secondo è maggiore o uguale alla prima, che aggiungere al totale sorted, altrimenti aggiungere al totale unsorted. Una volta fatto, prendere il rapporto tra i due.

Calcolare le lunghezze di tutte le sotto-sequenze ordinate, poi piazza li e aggiungerli. Se si desidera calibrare la quantità di enfasi che si mette sulla più grande, utilizzare una diversa potenza di 2.

Non sono sicuro di quello che è il modo migliore per normalizzare questo per lunghezza, forse dividerla per lunghezza al quadrato?

Quello che probabilmente stai cercando è Kendall Tau . E 'una funzione uno a uno della distanza bubble sort tra due array. Per verificare se un array è "quasi allineati", calcolare la sua Kendall Tau contro un array ordinato.

vorrei suggerire guardando il Pancake problema e la distanza inversione dei permutazioni. Questi algoritmi sono spesso utilizzati per trovare la distanza tra due permutazioni (l'identità e la stringa permutato). Questa misura distanza deve tener conto più ciuffi di valori in ordine, e anche inversioni (monotonicamente decrescente invece di aumentare sottosequenze). Ci sono anche approssimazioni che sono polinomiale tempo [PDF] .

E 'davvero tutto dipende da ciò che si intende il numero e se questa funzione distanza ha un senso nel vostro contesto però.

Ho lo stesso problema (monotonia di punteggio), e vi consiglio di provare Longest Aumentare Subsequence . La corsa più efficiente algoritmo in O(n log n), non è così male.

Prendendo esempio dalla domanda crescente sequenza più lunga di {4, 5, 6, 0, 1, 2, 3, 7, 8, 9} è {0, 1, 2, 3, 7, 8, 9} (lunghezza di 7). Forse tasso migliore (70%) di quanto il tuo periodo più lungo-ordinato algoritmo.

E 'altamente dipende da quello che avete intenzione di utilizzare la misura per, ma un modo semplice per farlo è quello di alimentare l'array in un algoritmo di ordinamento di serie e misurare il numero di operazioni (swap e / o confronti) devono essere fatto per ordinare l'array.

Alcuni esperimenti con un modificatore Ratcliff e 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

Quindi tipo di fa quello che deve. Non troppo sicuro come provarlo però.

Come di contare il numero di passi con l'aumentare del valore rispetto al numero di passi totali. Ecco O(n).

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top