C#有序组合算法

Question

6

我正在尝试开发一个C#应用程序，它将生成所有可能的排列列表，限制在成本范围内。例如，我有一个包含80个工作的列表。每个工作都有一个值（1-5）（通常为3），每个工程师都有一个通常为20的限制。

目前，我已经开始生成所有可能的组合列表（n！/（k！*（n-k）！其中n是总工作数，k是2）。每个工作之间的联系应该带有每个工作之间的距离权重。

从这里开始，我想选择一个初始的起始工作，并生成一个工作的所有可能组合列表（从起始工作开始），直到达到20的限制，然后按权重总和排序。最低权重路线将获胜并分配给工程师。我的问题是我不知道如何处理这个问题 - 什么数据结构最好？

通常有大约6-8名工程师（根据工作量而定），我计划一次路由每个工程师 - 一旦路由被分配给另一位工程师，那些工作将从列表中删除，并选择一个新的起始工作并生成新的组合集。这听起来像一个可接受的方法吗？

欢迎任何帮助。

- markpirvine

1

这基本上听起来像是一个数学问题，而不是一个 C# 问题。（尽管两者非常接近） - Caspar Kleijne

6

这里有一个 C# 库，可以用于排列、组合、笛卡尔积和其他方便的组合数学函数：http://www.codeproject.com/KB/recipes/Combinatorics.aspx。 - Eric Lippert

1

该描述确实让人想起了“背包”或“作业调度”问题。 - ypercubeᵀᴹ

线性规划，即单纯形算法的工作？ - vidstige

@vidstige：你显然读了一个不同于我所读的问题版本。 - sehe

显示剩余4条评论

3个回答

1

你可以看一下微软的求解器基础库： http://msdn.microsoft.com/en-us/devlabs/hh145003.aspx 此外，如果你对 Linq to Anything 感兴趣，也可以看看 Bart de Smet 的 Linq to Z3： http://channel9.msdn.com/Shows/Going+Deep/Bart-De-Smet-LINQ-to-Z3

- RogierBessem

1

目前还没有有效的算法来解决这个问题。我会使用遗传算法（不一定能找到最优解，但可以找到一个可接受的解决方案）。

- coffee_machine

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mzwaal · Accepted Answer

我建议尝试模拟退火算法，这是一种通过根据系统能量随机测试配置来寻找全局最优解的算法。