17

因此,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 种方法来配置您的系统/三明治”?
4

8 回答 8

5

惠普位于加利福尼亚的高端服务器制造工厂多年来一直使用基于规则的定制系统来做到这一点。

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

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

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

作为副作用,该系统还为工人在构建每个系统时提取的每个订单生成构建文档。它还为构建后的老化过程生成了预期的测试结果,因此测试台可以参考它们并确定一切是否正确构建。

于 2009-10-29T15:38:12.273 回答
4

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

问题定义

好吧,这是一个图形问题(不是全部),您有与其他项目兼容的项目。例如,Pentium i3-2020与any兼容Socket 1155 Motherboard,即Asrock H61M-VS 是a Socket 1155 Motherboard,与2xDDR3(速度= 1066)兼容,需要a 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 Motherboard,H61M-VS has-a DDR3 memory slot(每个插槽都有速度属性)。

其次是分类和组成,你需要确定需求,这很简单。现在简单分类可以让一个简单的 SQL 查询找到所有符合分类的项目。

测试一个令人满意的篮子

要测试篮子,需要创建一个配置,确定哪些项目与哪些项目匹配(即主板的 DDR3 插槽与 4GB 内存模块匹配,SATA HDD 电缆连接到主板 SATA 端口和 PSU 的 SATA 电源线,而 PSU 的 4 pin ATX 12V电源线连接到主板。

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

戴尔电脑配置器

你从一个项目开始,比如一个处理器。处理器需要主板和风扇,因此您可以给他们选择主板(将处理器风扇添加到list_of_things_to_be_satisfied)。这种情况一直持续到 中没有更多的项目list_of_things_to_be_satisfied。当然,这一切都取决于您的确切要求以及您将为用户解决什么问题。

于 2011-12-27T11:26:08.477 回答
3

有很多方法可以在代码中实现这一点,但在我看来,这是在编程之前解决问题的最佳方法:

定义零件和产品(预代码)

在定义所有“部件”时,识别部件的层次结构和分类至关重要。这是正确的,因为某些规则可能是独特的部分(例如“仅棕色芥末”),一些分类(例如“所有芥末”),一些按类型(例如“所有调味品”)等。

构建规则集(预代码)

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

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

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

在花了这么多时间研究“零件”的独特/类别/类型规则之后,许多设计师会忽略仅适用于成品的规则,即使零件没有冲突。

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

这个规则图可以很快变得非常复杂。

构建数据结构的建议(代码)

  1. 确保您的结构适应层次结构和分类。例如:“brown mustard”和“dijon mustard”是单独的对象,它们都是芥末,都是调味品。

    仔细选择继承建模(基类)和对象属性(例如Category属性或HasCondiments标志)的正确组合来完成这项工作。

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

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

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

编写你的算法(代码)

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

这一步的诀窍是如何在代码中实现沿树/图向上传播的规则——例如,当特定部分与超出其范围的另一部分存在问题时,或者当另一部分运行时如何运行验证添加?我的想法:

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

  2. 在 Product 对象上,定义处理程序来处理OnPartAddedand 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.
    }
}

干净整洁。

于 2011-12-28T19:32:19.420 回答
2

生成函数”作为解决此类问题时可以使用的一种结构出现在脑海中。我会注意到,根据您的需要,有几种不同的生成函数。

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

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

L33t可能是另一种在识别不适当的词时带来更多复杂性的方法,因为 ass 被审查 a$$ 或 @ss 可能不一定会以相同的方式处理,即使它基本上是以不同方式表达的相同术语。我不确定车牌上是否会出现许多特殊字符(如 $ 或 @),但可以将网络内容的家长控制视为必须拥有这些算法来识别要审查的术语。

于 2009-10-29T15:50:47.023 回答
2

作为一名程序员,我会做以下事情(尽管我在现实生活中实际上从未这样做过):

  • 计算出组合的总数,通常直接乘以您问题中所述的选项就足够了。无需存储所有这些组合。
  • 然后将您的总数除以例外情况。异常可以存储为一组规则,有效地说明哪些组合是不允许的。
  • 要计算出允许的组合总数,您必须遍历整套例外规则。

如果您将所有组合视为一个集合,那么例外只会删除该集合的成员。但是您不需要存储整个集合,只需要存储例外,因为您可以很容易地计算集合的大小

于 2009-10-29T15:57:24.967 回答
1

您可能希望创建一个数据结构来唯一地表示单个配置。然后,每个兼容性规则都应该以这样的方式定义,即它可以生成一个集合,其中包含所有不符合该规则的单独配置。然后,您将对所有规则生成的所有集合进行并集,以获得所有不符合规则的配置的集合。然后计算该集合的大小,并从集合的所有可能配置的大小中减去它。

困难的部分是以一种可以由您的规则生成的方式定义数据结构,并且可以让集合操作对其进行处理!这对读者来说是一个练习,AKA 我什么都没有。

于 2009-11-03T16:32:55.917 回答
1

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

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

这只是说你有 2 个包子选项(包子或不包子) - 芝麻有 1 个选项(仅当你有包子时 - 表示依赖关系 - 如果你在这里有 7 这意味着如果你只存在 7 种类型吃个面包)

3芥末..等

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

于 2011-12-26T14:56:57.157 回答
1

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

在芥末的情况下,您将为芥末类型添加一个二进制条目“mustard_type”并引入条件:芥末的二进制条目not (not mustard and mustard_type)在哪里mustardmustard_type == 0当您选择时,它将强制执行默认选择not mustard

对于芝麻的选择,这更明确:not (sesame and not bun).

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

于 2011-12-28T17:31:49.280 回答