1

编辑：为什么我认为这不是重复的：正如biziclop(a>b & b>c => a>c)所写，这里的问题不像这里提到的其他问题那样不及物，而是a>b => -(b>a)违反了该条款，所以这是一个不同的问题。

我收到以下错误消息：

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.TimSort.mergeHi(Unknown Source)
at java.util.TimSort.mergeAt(Unknown Source)
at java.util.TimSort.mergeForceCollapse(Unknown Source)
at java.util.TimSort.sort(Unknown Source)
at java.util.Arrays.sort(Unknown Source)
at construct.Repair.regretRepair(Repair.java:101)
at lns.One.repaired(One.java:122)
at lns.One.segment(One.java:68)
at lns.One.lnsSolution(One.java:35)
at lns.All.lnsSolutions(All.java:22)
at barter.Genetic.initialPopulation(Genetic.java:36)
at barter.Genetic.run(Genetic.java:26)
at program.Main.main(Main.java:22)

这就是它发生的地方：

Arrays.sort(regretProfits, new Comparator<RegretProfit>(){
            @Override
            public int compare(RegretProfit first, RegretProfit second){
                if (first.possibleRoutes <= 0){
                    if (second.possibleRoutes > 0){
                        return 1;
                    }
                    return 0;
                }                   
                if (first.possibleRoutes < solution.schedule.size() - kay + 1){
                    if (first.possibleRoutes < second.possibleRoutes){
                        return -1;
                    }
                    if (first.possibleRoutes > second.possibleRoutes){
                        return 1;
                    }
                    if (first.profit > second.profit){
                        return -1;
                    }
                    if (first.profit < second.profit){
                        return 1;
                    }
                }
                if (first.regret > second.regret){
                    return -1;
                }
                if (first.regret < second.regret){
                    return 1;
                }
                return 0;
            }
        ;});

这是定义对象 RegretProfit 的类：

public class RegretProfit {
    public int[] order;
    public double regret;
    public double profit;
    public int possibleRoutes;
}

该错误仅每几千次迭代发生一次。如果有人知道问题可能是什么，我将非常感激。我已经读过不传递性会导致此异常，但我真的无法弄清楚我可能出错的地方。

解决了，感谢biziclop！

Arrays.sort(regretProfits, new Comparator<RegretProfit>(){
            @Override
            public int compare(RegretProfit first, RegretProfit second){
                if (first.possibleRoutes <= 0 && second.possibleRoutes > 0){
                    return 1;
                }
                if (first.possibleRoutes <= 0 && second.possibleRoutes <= 0){
                    return 0;
                }
                if (first.possibleRoutes > 0 && second.possibleRoutes <= 0){
                    return -1;
                }
                if (first.possibleRoutes < solution.schedule.size() - kay + 1 || second.possibleRoutes < solution.schedule.size() - kay + 1){
                    if (first.possibleRoutes < second.possibleRoutes){
                        return -1;
                    }
                    if (first.possibleRoutes > second.possibleRoutes){
                        return 1;
                    }
                    if (first.profit > second.profit){
                        return -1;
                    }
                    if (first.profit < second.profit){
                        return 1;
                    }
                }
                if (first.regret > second.regret){
                    return -1;
                }
                if (first.regret < second.regret){
                    return 1;
                }
                return 0;
            }
        ;});
4

1 回答 1

4

这里的关键问题不是传递性，违反合同的部分是sgn(compare(x, y)) == -sgn(compare(y, x))

例如，如果您有这些记录：

 first.possibleRoutes = -1; first.regret = 1
 second.possibleRoutes = 1; second.regret = -1

您的比较器返回 1。但是如果您交换它们：

 first.possibleRoutes = 1; first.regret = -1
 second.possibleRoutes = -1; second.regret = 1

您的比较器仍然可能返回 1。

查看代码有两个可疑的非对称结构：

            if (first.possibleRoutes <= 0){
                if (second.possibleRoutes > 0){
                    return 1;
                }
                return 0;
            }

first如果和second被反转，这里没有匹配的 -1 返回。您还将每个项目possibleRoutes <= 0视为平等，这可能不是您想要的。

            if (first.possibleRoutes < solution.schedule.size() - kay + 1){

在这里，您完全根据 的值输入一个分支first，这意味着该分支也可能导致sgn(compare(x, y)) != -sgn(compare(y, x)).

当然，在整个系统的额外约束下，这两个问题可能会相互抵消（显然在这种情况下不会），但这是设计比较器的一种非常脆弱的方式，我建议你确保所有分支都是对称的。它使推理代码的正确性变得容易得多。

于 2015-06-19T15:48:41.377 回答