复杂的组合算法

Question

因此,温迪的通告其夹层具有256个组合 - 这意味着有8种成分,你可以有没有(虽然我不知道为什么他们会算,你什么都不包括作为有效的组合,但我离题).

通用方法允许您将每个选择的各种状态相乘,从而允许更复杂的组合.在这种情况下,Wendy的项目只能包含或排除.但是一些三明治可能有两种芥末的选择(但不是两种,以节省成本).

这些都相当简单.你将选项的数量相乘,所以For Wendy's:

2*2*2*2*2*2*2*2 = 256

如果他们将芥末选择多样化,如上所述:

2*2*3*2*2*2*2*2 = 384

走得更远似乎更难.

如果你将芝麻作为一个单独的项目,那么他们需要发髻项目.只有在包含面包的情况下才可以吃芝麻,并且可以没有芝麻的面包,但是如果没有芝麻,你就不能吃芝麻.这可以简化为具有三种状态的单个发髻物品(无,带有种子的发髻,没有发髻)但是有些情况无法完成.

例如,戴尔的计算机配置器不允许某些组合(可能插槽已满,当放入同一系统时项目不兼容等).

• 在处理项目可能发生冲突的更复杂的系统时,有哪些适当的组合方法？
• 什么是好的,通用的方法来存储这些信息,而无需为每个产品/组合/项目编写代码以捕获冲突？
• 有一种简单的方法可以说,"当系统必须处理复杂的冲突组合时,有X种方法来配置系统/三明治"吗？

Answer 1

惠普在加利福尼亚的高端服务器制造工厂多年来一直使用基于规则的自定义系统来实现这一目标.

工厂车间构建周期过程包括前期检查,以确保在将订单发布给构建者和测试人员之前可以构建订单.

其中一项检查确定订单的物料清单(BOM)是否符合过程工程师指定的规则列表.例如,如果客户订购处理器,请确保他们还订购了足够的直流转换器部件; 或者,如果他们订购了一定数量的内存DIMM,请确保他们还订购了一块子板以容纳额外的容量.

具有编译器背景的计算机科学专业的学生会识别代码.代码解析了BOM,在内部生成按类型分组的线程化零件树.然后,它将规则应用于内部树,以确定订单是否符合.

作为副作用,系统还为每个订单生成构建文档,工作人员在构建每个系统时将其拉出.它还为构建后的老化过程生成了预期的测试结果,因此测试托架可以引用它们并确定是否所有内容都已正确构建.

Answer 2

有很多方法可以在代码中实现这一点，但以我的拙见，在进行任何编程之前解决问题的最佳方法是：

定义零件和产品（预编码）

在定义所有“部件”时，识别部件的层次结构和分类至关重要。这是事实，因为某些规则可能专用于特定部分（例如“仅棕色芥末”），某些规则可能专用于特定部分（例如“所有芥末”），某些规则可能专用于类型（例如“所有调味品”）等。

构建规则集（预编码）

为每个独特的零件、类别、类型和成品定义规则集（先决条件、排除等）。

这可能听起来很愚蠢，但必须非常小心以确保规则的定义范围适当。例如，如果成品是Burger：

• 独特物品规则 - “蘑菇只能与选择的蓝纹奶酪一起使用” prerequisite
• 分类规则 - “只能选择 1 种芥末” exclusive
• 类型规则 - “泡菜与辣椒不相容” exclusive

在花费了大量时间在“零件”的独特/类别/类型规则上之后，许多设计师将忽略仅适用于成品的规则，即使零件没有冲突。

• 产品规则 - “最多 5 种调味品” condition
• 产品规则 - “汉堡必须有一个小圆面包” prerequisite

这个规则图很快就会变得非常复杂。

构建数据结构的建议（代码）

1. 确保您的结构适应层次结构和分类。例如：“棕芥末”和“第戎芥末”是单独的对象，它们都是芥末，都是调味品。

   仔细选择继承建模（基类）和对象属性（例如Category属性或HasCondiments标志）的正确组合以使这项工作有效。

2. 在每个层次对象级别创建一个私有字段RuleSets。

3. 为标志和集合创建公共属性。HasConflictsRuleViolations

4. 将部件添加到产品时，请检查所有级别的规则（其自身、类别、类型和产品）——通过可从产品调用的公共函数来执行此操作。或者为了更好地内部化，您可以在部件本身上创建一个事件处理程序。

编写你的算法（代码）

这就是我糟糕的地方，这是一件好事，因为它有点超出了你的问题的范围。

此步骤的技巧是如何在代码中实现沿着树/图向上传播的规则——例如，当特定部分与超出其范围的另一部分发生问题时，或者当另一部分出现问题时如何运行验证添加？我的想法：

1. 对每个部分使用公共函数方法。将产品的CurrentParts集合传递给它。

2. 在 Product 对象上，定义处理程序来处理OnPartAdded和OnPartRemoved，并让它们枚举集合CurrentParts并调用每个部分的验证函数。

简单原型示例

interface IProduct
{
    void AddPart();
    void OnAddPart();
}
// base class for products
public class Product() : IProduct
{
     // private or no setter. write functions as you like to add/remove parts.
    public ICollection<Part> CurrentParts { get; };
    // Add part function adds to collection and triggers a handler.
    public void AddPart(Part p)
    {
        CurrentParts.Add(p);
        OnAddParts();
    }
    // handler for adding a part should trigger part validations
    public void OnAddPart()
    {
        // validate part-scope rules, you'll want to return some message/exception
        foreach(var part in CurrentParts) {
            part.ValidateRules(CurrentParts); 
        }
        ValidateRules(); // validate Product-scope rules.
    }
}

interface IProduct
{
    // "object" should be replaced with whatever way you implement your rules
    void object RuleSet; 
    void ValidateRules(ICollection<Part> otherParts);
}
// base class for parts
public class Part : IPart
{
    public object RuleSet; // see note in interface.

    public ValidateRules(ICollection<Part> otherParts)
    {
        // insert your algorithms here for validating 
        // the product parts against this part's rule set.
    }
}

漂亮又干净。