用于对数组的单调性进行评级的算法(即判断数组的“排序") [英] Algorithm for rating the monotonicity of an array (i.e. judging the "sortedness" of an array)

问题描述

编辑:哇，很多好评.是的，我将其用作适应性函数来判断遗传算法执行的排序质量.因此，评估成本很重要(即必须快速，最好是O(n).)

EDIT: Wow, many great responses. Yes, I am using this as a fitness function for judging the quality of a sort performed by a genetic algorithm. So cost-of-evaluation is important (i.e., it has to be fast, preferably O(n).)

作为我正在玩弄的AI应用程序的一部分，我希望能够基于其单调性(也称为排序")对整数候选数组进行评分.此刻，我正在使用一种启发式算法来计算最长的排序运行，然后将其除以数组的长度:

As part of an AI application I am toying with, I'd like to be able to rate a candidate array of integers based on its monotonicity, aka its "sortedness". At the moment, I'm using a heuristic that calculates the longest sorted run, and then divides that by the length of the 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;
}

这是一个好的开始，但是它没有考虑排序子序列可能会成簇"的可能性.例如:

This is a good start, but it fails to take into account the possibility that there may be "clumps" of sorted sub-sequences. E.g.:

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

此数组分为三个排序的子序列.我的算法将其评为仅40％排序，但是从直观上讲，它应该获得更高的分数.这类事情有标准的算法吗?

This array is partitioned into three sorted sub-sequences. My algorithm will rate it as only 40% sorted, but intuitively, it should get a higher score than that. Is there a standard algorithm for this sort of thing?

推荐答案

我希望选择使用的功能在很大程度上取决于您打算使用的功能.根据您的问题，我想您正在使用遗传系统创建分类程序，这将成为排名功能.如果真是这样，那么执行速度至关重要.基于此，我敢打赌，您最长排序的子序列算法可以很好地工作.听起来应该很适合定义健身.

I expect that the choice of function to use depends very strongly on what you intend to use it for. Based on your question, I would guess that you are using a genetic system to create a sorting program, and this is to be the ranking function. If that is the case, then speed of execution is crucial. Based on that, I bet your longest-sorted-subsequence algorithm would work pretty well. That sounds like it should define fitness pretty well.

这篇关于用于对数组的单调性进行评级的算法(即判断数组的“排序")的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！