优化非常大的列表.Net的递归函数

Question

我已经构建了一个应用程序,用于模拟公司每月可以以不同"模式"生产的产品数量.此模拟用于帮助找到最佳运行模式系列一个月,以最好地满足当月的预计销售预测.该应用程序一直运行良好,直到最近工厂被修改为以其他模式运行.现在可以以16种模式运行.对于22个工作日的一个月,这产生了9,364,199,760种可能的组合.这从过去的8种模式中提升,仅产生1,560,780种可能的组合.运行此应用程序的PC是旧的,在抛出内存不足异常之前无法处理计算次数.事实上,整个应用程序不能支持超过15种模式,因为它使用整数来跟踪模式的数量,并且它超过了整数的上限.面对这个问题,我需要尽我所能降低应用程序的内存利用率并优化它以尽可能高效地运行,即使它无法实现16种模式的既定目标.我正在考虑将数据写入磁盘而不是将列表存储在内存中,但在我承担这一开销之前,我希望得到人们对该方法的看法,看看是否有任何优化空间.

编辑 基于少数人的建议,考虑更具学术性的东西,然后只计算每个可能的答案,下面列出了如何选择最佳运行(模式组合)的简要说明.目前,计算机确定工厂可以在该月的工作日数内运行的每种可能方式.例如,3个模式最多2个工作日将导致(1,1),(1,2),(1,3),(2,2)的组合(其中数字代表所选模式), (2,3),(3,3)对于每种模式,产品以不同的生产率生产,例如在模式1中,产品x可以每小时50个单位生产,其中产品y以每小时30个单位生产,产品z以每小时0个单位产生.然后将每个组合乘以工时和生产率.选择产生与每月产品的预测值最接近匹配的数字的运行.但是,由于工厂的某些月份不符合产品的预测值,因此该算法会提高下个月产品的优先级,以确保产品在年底达到预测值.由于仓库空间紧张,重要的是产品不要过多生产.

谢谢

private List<List<int>> _modeIterations = new List<List<int>>();

private void CalculateCombinations(int modes, int workDays, string combinationValues)
    {
        List<int> _tempList = new List<int>();

        if (modes == 1)
        {
            combinationValues += Convert.ToString(workDays);
            string[] _combinations = combinationValues.Split(',');

            foreach (string _number in _combinations)
            {
                _tempList.Add(Convert.ToInt32(_number));
            }
            _modeIterations.Add(_tempList);
        }
        else
        {
            for (int i = workDays + 1; --i >= 0; )
            {
                CalculateCombinations(modes - 1, workDays - i, combinationValues + i + ",");
            }
        }
    }

Answer 1

这种优化问题很难,但研究得非常好.您可能应该阅读有关它的文献,而不是试图重新发明轮子.您要查找的关键字是"运营研究"和"组合优化问题".

在优化问题的研究中众所周知,找到问题的最优解决方案几乎总是在计算上不可行,因为问题变得越来越大,正如您自己发现的那样.然而,经常出现的情况是找到保证在最佳解决方案的某个百分比内的解决方案是可行的.您应该专注于寻找近似解决方案.毕竟,您的销售目标已经是有根据的猜测,因此找到最佳解决方案已经不可能了; 你还没有完整的信息.)

我要做的是首先阅读背包问题上的维基百科页面:

http://en.wikipedia.org/wiki/Knapsack_problem

这是一个问题:"我有一大堆不同价值和不同重量的物品,我可以携带50磅的背包,在达到我的体重目标时,我可以携带的最大值是多少？"

这不完全是你的问题,但显然它是相关的 - 你有一定数量的"价值"来最大化,并且有限数量的插槽将这个价值包装进去.如果您可以开始了解人们如何找到背包问题的近乎最佳解决方案,您可以将其应用于您的特定问题.

Answer 2

您可以在生成排列后立即处理排列,而不是首先在列表中收集排列:

public delegate void Processor(List<int> args);

private void CalculateCombinations(int modes, int workDays, string combinationValues, Processor processor)
{
    if (modes == 1)
    {
        List<int> _tempList = new List<int>();
        combinationValues += Convert.ToString(workDays);
        string[] _combinations = combinationValues.Split(',');

        foreach (string _number in _combinations)
        {
            _tempList.Add(Convert.ToInt32(_number));
        }
        processor.Invoke(_tempList);
    }
    else
    {
        for (int i = workDays + 1; --i >= 0; )
        {
            CalculateCombinations(modes - 1, workDays - i, combinationValues + i + ",", processor);
        }
    }
}

我在这里假设,你目前的工作模式是有道理的

CalculateCombinations(initial_value_1, initial_value_2, initial_value_3);

foreach( List<int> list in _modeIterations ) {

    ... process the list ...

}

通过直接过程方法,这将是

private void ProcessPermutation(List<int> args) 
{
    ... process ...
}

... 别的地方 ...

CalculateCombinations(initial_value_1, initial_value_2, initial_value_3, ProcessPermutation);

我还建议你尽可能早地修剪搜索树; 如果你已经可以告诉,参数的某些组合永远不会产生可以处理的东西,你应该在生成期间捕获那些,并且如果可能的话,完全避免递归.

在新版本的C#中,使用迭代器(？)函数生成组合可能可用于保留代码的原始结构.我还没有真正使用过这个功能(yield),所以我不能评论它.