c# - 如何优化这种船员调度组合方法？

Question

我有这个方法，工作得很好，但它很慢，有时我必须等待 15 分钟才能得到一个好的结果，这没关系，但我想知道我是否可以让它更快。

基本上我运行的是最佳船队模拟，我预先计算了特定航程的可能船舶组合，但随后我必须为多个航程获得最佳船队组合。

显然我不能在不同的船上使用同一个船长或船员，因为航行是同时进行的，这就是为什么每个内循环中都有更多的条件。

如有任何帮助或指示，我们将不胜感激。

private static Ship[] GetBestFleet3(IList<Voyage> voyages)
{
    var totalRate = 0;
    var previousStdDev = 100.0;
    Ship[] fleet = null;
    foreach (var ship0 in voyages[0].Ships)
    {
        foreach (var ship1 in voyages[1].Ships.Where(s => s.Captain != ship0.Captain && !s.Crew.Intersect(ship0.Crew).Any()))
        {
            foreach (var ship2 in voyages[2].Ships.Where(s => s.Captain != ship0.Captain && s.Captain != ship1.Captain && !s.Crew.Intersect(ship0.Crew).Any() && !s.Crew.Intersect(ship1.Crew).Any()))
            {
                var stdDev = Statistics.Variance(ship0, ship1, ship2);
                if (ship0.Rate + ship1.Rate + ship2.Rate > totalRate || ship0.Rate + ship1.Rate + ship2.Rate == totalRate && stdDev < previousStdDev)
                {
                    totalRate = ship0.Rate + ship1.Rate + ship2.Rate;
                    previousStdDev = stdDev;
                    fleet = new[] { ship0, ship1, ship2 };

                    if (ship0.Rate >= 100 && ship1.Rate >= 100 && ship1.Rate >= 100)
                    {
                        return fleet;
                    }
                }
            }
        }
    }
    return fleet;
}

Answer 1

现在您正在对舰队-船长组合进行详尽搜索(从我从您的嵌套 for 循环中看到的情况来看，我有点不清楚代码是如何运行的)，这是根据您的运行时间来判断的是一个很大的搜索空间。如果你想要运行得更快的东西，但不能保证给你最佳解决方案，你可能想看看元启发式算法，如禁忌搜索、模拟退火或遗传算法。我不推荐 Ant-Colony Optimization，因为我不确定如何将其转化为图表，而且我的一个 friend 遇到过相同类型的问题(飞机和飞行员)并没有看到它表现得很好。

有关此方向的研究，请查看以下论文:

• 多目标机组人员排类问题的模拟退火
• 求解列车乘务员调度问题的多目标遗传算法

或者，您可能想研究并行化穷举搜索，但这样问题会更适合 CodeReview .