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}

这个数组被分成三个排序的子序列。我的算法将它评为只有 40% 的排序，但直观地说，它应该得到比这更高的分数。这种事情有标准算法吗？

4

11 回答 11

5

这似乎是Levenshtein Damerau–Levenshtein距离的一个很好的候选 - 对数组进行排序所需的交换次数。这应该与每个项目离它应该在排序数组中的位置的距离成正比。

这是一个简单的红宝石算法，它对距离的平方求和。这似乎是衡量排序的一个好方法——每次交换两个无序元素时，结果都会变小。

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

这是我刚编的一个。

对于每对相邻值，计算它们之间的数值差。如果第二个大于或等于第一个，则将其添加到sorted总数中，否则添加到unsorted总数中。完成后，取两者的比值。

于 2010-01-20T20:08:22.503 回答
2

计算所有排序子序列的长度，然后将它们平方并相加。如果要校准最大的强调程度，请使用不同于 2 的功率。

我不确定将其按长度标准化的最佳方法是什么，也许将其除以长度的平方？

于 2010-01-20T20:10:04.190 回答
2

您可能正在寻找的是Kendall Tau。这是两个数组之间冒泡排序距离的一对一函数。要测试一个数组是否“几乎已排序”，请根据已排序的数组计算其 Kendall Tau。

于 2010-01-20T20:16:04.000 回答
1

我建议看一下煎饼问题和排列的反转距离。这些算法通常用于查找两个排列（标识和排列的字符串）之间的距离。这个距离度量应该考虑更多的顺序值簇，以及反转（单调递减而不是递增的子序列）。还有多项式时间的近似值[PDF]。

这实际上完全取决于数字的含义以及此距离函数在您的上下文中是否有意义。

于 2010-01-20T19:38:59.467 回答
1

我有同样的问题（单调性评分），我建议你尝试Longest increasing Subsequence。运行效率最高的算法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

这在很大程度上取决于您打算使用该度量的目的，但一种简单的方法是将数组输入标准排序算法并测量需要执行多少操作（交换和/或比较）才能进行排序数组。

于 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 回答