Алгоритм оценки монотонности массива (т. е. оценки "сортированности" массива)

EDIT : Вау, много отличных ответов. Да, я использую это как функцию пригодности для оценки качества сорта, выполняемого генетическим алгоритмом. Таким образом, оценка стоимости важна (т. е. она должна быть быстрой, предпочтительно O(n).)

Как часть приложения ИИ, с которым я играю, я хотел бы иметь возможность оценить потенциальный массив целых чисел на основе его монотонности, или "сортированности". На данный момент я использую эвристику, которая вычисляет самую длинную сортировку выполнить, а затем разделить его на длину массива: 

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}

Этот массив разбит на три отсортированных под-последовательности. Мой алгоритм оценит его как сортированный только на 40%, но интуитивно он должен получить более высокий балл. Существует ли стандартный алгоритм для такого рода вещей?

11 9
artificial-intelligence information-theory genetic-algorithm

11 ответов:

Я ожидаю, что выбор функции для использования очень сильно зависит от того, для чего вы собираетесь ее использовать. Исходя из вашего вопроса, я бы предположил, что вы используете генетическую систему для создания программы сортировки, и это должно быть функцией ранжирования. Если это так, то скорость выполнения имеет решающее значение. Исходя из этого, я уверен, что ваш алгоритм с самой длинной сортировкой подпоследовательностей будет работать довольно хорошо. Это звучит так, как будто это должно определять фитнес довольно хорошо.

3

Это кажется хорошим кандидатом для Левенштейн Damerau-Levenstein distance-количество свопов, необходимых для сортировки массива. Это должно быть пропорционально тому, как далеко каждый элемент находится от того места, где он должен быть в отсортированном массиве.

Вот простой алгоритм ruby, который суммирует квадраты расстояний. Это кажется хорошей мерой сортированности-результат становится меньше каждый раз, когда два элемента из порядка меняются местами. 
ap = a.sort
sum = 0
a.each_index{|i| j = ap.index(a[i])-i 
  sum += (j*j)
}
dist = sum/(a.size*a.size)
5

Что-то вроде этого? http://en.wikipedia.org/wiki/Rank_correlation

2

Вот один, который я только что придумал.

Для каждой пары соседних значений вычислите числовую разницу между ними. Если второе больше или равно первому, добавьте его к сумме sorted, в противном случае добавьте к сумме unsorted. Когда закончите, возьмите соотношение двух.

2

Вычислите длину всех отсортированных под-последовательностей, затем возведите их в квадрат и добавьте. Если вы хотите откалибровать, сколько enphasis вы ставите на наибольший, используйте мощность, отличную от 2.

Я не уверен, что лучший способ нормализовать это по длине, может быть, разделить его на длину в квадрате?

2

То, что вы, вероятно, ищете, - это Кендалл Тау. Это взаимно однозначная функция расстояния сортировки пузырьков между двумя массивами. Чтобы проверить, является ли массив "почти отсортированным", вычислите его Kendall Tau против отсортированного массива.

2

Я бы предложил посмотреть на Блиновую Задачу и расстояние обращения перестановок. Эти алгоритмы часто используются для определения расстояния между двумя перестановками (тождеством и перестановочной строкой). Эта мера расстояния должна учитывать больше сгустков значений порядка, а также развороты (монотонно убывающие вместо возрастающих подпоследовательностей). Существуют также приближения , которые являются полиномиальными по времени[PDF].

На самом деле все зависит от что означает число и имеет ли эта функция расстояния смысл в вашем контексте.

1

У меня та же проблема (оценка монотонности), и я предлагаю вам попробовать самую длинную возрастающую подпоследовательность. Самый эффективный алгоритм, запущенный в O(n log n), не так уж плох.

Беря пример из вопроса, самая длинная возрастающая последовательность {4, 5, 6, 0, 1, 2, 3, 7, 8, 9} равна {0, 1, 2, 3, 7, 8, 9} (Длина 7). Может быть, это лучше (70%), чем ваш алгоритм с самой длинной сортировкой.

1

Это сильно зависит от того, для чего вы собираетесь использовать меру, но один простой способ сделать это-ввести массив в стандартный алгоритм сортировки и измерить, сколько операций (свопов и/или сравнений) необходимо выполнить для сортировки массива.

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

Таким образом, он делает то, что ему нужно. Хотя не очень уверен, как это доказать.

0

Как насчет подсчета количества шагов с возрастающим значением по сравнению с общим числом шагов? Это O(n).

0