复杂的组合算法

Question

所以 Wendy's 宣传他们的三明治有 256 种组合 - 这意味着有 8 种成分你可以要么不吃（虽然我想知道为什么他们会把你不包含任何成分的组合算作有效的，但我离题了）。

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

这些都是相当简单的。将选项数量相乘，对于 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

Adam Davis：如果我理解正确的话，您打算开发某种系统，该系统实际上可以用于购物车，帮助用户购买兼容部件。

问题定义

这是一个图形问题（不是全部），您有与其他项目兼容的项目。例如，Pentium i3-2020 与任何 Socket 1155 主板 兼容，Asrock H61M-VS 是 Socket 1155 主板，兼容 2xDDR3（速度 = 1066），并需要 PCI-Express GPU、DDR3 PC RAM{Total(size) = 16GB}、4 pin ATX 12V power等。

您需要能够 (a) 识别购物篮中的每一项是否满足购物篮中的另一项（即 RAM卡具有兼容的主板），(b) 分配最合适的项目（即，如果主板没有 USB 端口，则将 USB 集线器分配给主板 USB 端口，将打印机分配给 USB 集线器，而不是相反，让集线器保持干燥)，(c) 为用户提供查找满意组件列表的功能。也许 USB 集线器始终可以优先，因为它们是扩展（但请注意这一点）。

您将需要的数据结构

您将需要一个简单的分类系统，即 H61M-VS is-a 主板、H61M-VS has-a DDR3内存插槽（每个插槽都有速度属性）。

除了分类和组合之外，您还需要确定需求，这非常简单。现在，简单的分类可以允许简单的 SQL 查询来查找符合分类的所有项目。

测试满意的篮子

要测试篮子，需要创建一个配置，确定哪些项目与哪些项目匹配（即主板的 DDR3 插槽与 4GB RAM 模块匹配、SATA HDD 电缆连接到主板 SATA 端口以及 PSU 的 SATA 电源线，当PSU的4针ATX 12V电源线连接到主板时，

最简单的事情就是检查是否存在另一个令人满意的项目。

戴尔的计算机配置器

您从一个项目开始，比如说处理器。处理器需要主板和风扇，因此您可以。让他们选择主板（将处理器风扇添加到 list_of_things_to_be_satisfied 中）。这会一直持续到 list_of_things_to_be_satisfied 中不再包含任何项目。当然，这一切都取决于您的情况。 确切的要求并知道您将为用户解决什么问题。

Answer 3

您可以通过多种方法在代码中实现此目的，但以我的拙见，在进行任何编程之前解决问题的最佳方法是：

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

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

构建规则集（预编码）

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

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

• 唯一项目规则 - “蘑菇仅适用于选择的蓝纹奶酪” 先决条件
• 分类规则 - < em>“只能选择 1 种芥末” 排他性
• 类型规则 - “泡菜与辣椒不兼容” 排他性

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

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

此图表规则很快就会变得非常复杂。

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

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

   仔细选择继承建模（基类）和对象属性（例如 Category 属性或 HasCondiments 标志）的正确组合以实现此目的。

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

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

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.
    }
}

漂亮、干净。

Answer 4

作为一名程序员，我会执行以下操作（尽管我在现实生活中实际上从未这样做过）：

• 计算出总数量
  组合，通常是直线
  选项的乘法为
  你的问题中所述就足够了。
  没有必要存储所有这些
  组合。
• 然后将您的总数除以
  例外情况。例外情况可以是
  仅存储为一组规则，
  有效地说出哪些组合
  是不允许的。
• 要计算出总数
  允许的组合，你将有
  来贯穿整个集合
  例外规则。

如果您将所有组合视为一个集合，那么例外只会删除该集合的成员。但您不需要存储整个集合，只需存储例外情况，因为您可以非常轻松地计算集合的大小。

Answer 5

“生成函数”作为解决此类问题时可以使用的一种构造。我注意到，根据您的需要，有几种不同的生成函数。

在北美，汽车牌照在计算所有排列时可能是一个有趣的组合问题，其中 6 或 7 中的每个位置都有 36 个可能的值，这 6 或 7 是牌照的长度，具体取决于人们获得牌照的位置。然而，有些组合由于其中含有脏话或种族主义词语而被取消资格，这使得问题变得稍微困难​​一些。例如，有一个臭名昭著的 N 词，它至少有几种不同的拼写，我认为这些拼写是不允许出现在车牌上的。

另一个例子是使用给定的字母表确定所有不同的单词顺序，该字母表包含一些重复多次的项目。例如，如果有人想要以所有不同的方式来排列“字母”一词的字母，那么它不仅仅是 6 个！这就是“abcdef”的情况，因为有两对字母，这使得计算起来稍微有点棘手。

L33t 可以是另一种方法，可以在识别不当词语方面变得更加复杂，因为屁股会受到审查$$ 或 @ss 可能不一定以相同的方式处理，即使它们基本上是以不同方式表达的相同术语。我不确定像 $ 或 @ 这样的许多特殊字符是否会出现在车牌上，但人们可以认为对网络内容的家长控制必须具有此类算法来识别要审查的术语。

Answer 6

您可能想要创建一个唯一代表单个配置的数据结构。然后，每个兼容性规则应该以一种可以生成包含所有不符合该规则的单独配置的集合的方式进行定义。然后，您将采用所有规则生成的所有集合的并集，以获得不符合规则的所有配置的集合。然后计算该集合的大小，并从该集合的大小中减去所有可能的配置。

困难的部分是以一种可以由您的规则生成的方式定义数据结构，并且可以对其进行集合操作！这是给读者的练习，也就是我什么也没有。

Answer 7

我现在唯一能想到的就是构建，如果你可以构建一个树来定义各部分之间的依赖关系，你就有一个简单的解决方案。

sandwitch
|
|__Bun(2)__sesame(1)
|
|__Mustard(3)
|
|__Mayo(2)
|
|__Ketchup(2)
|
|__Olives(3)

这只是说你有 2 个面包选项（有面包或没有面包） - 1 个芝麻（只有当你有一个面包时 - 表示依赖性 - 如果你这里有 7 则意味着如果你只存在 7 种类型）有一个小圆面包）

3代表芥末..等等，

然后简单地乘以所有分支的总和。

Answer 8

可能可以将问题形式化为 k-sat 问题。在某些情况下，问题似乎是 NP 完全的，您必须枚举所有可能性来检查它们是否满足所有条件。在其他一些情况下，问题很容易解决（例如，当需要很少的条件时）。这是一个活跃的研究领域。你可以在谷歌学术上找到相关参考资料。

对于芥末，您可以为芥末类型添加一个二进制条目“mustard_type”，并引入条件：not（不是芥末和 Mustard_type），其中 mustard 是芥末的二进制条目。当您选择非芥末时，它将强制执行默认选择mustard_type == 0。

对于芝麻的选择，这是更明确的：not（芝麻而不是面包）。

因此，您提出的案例似乎属于 2-sat 系列问题。