3

我正在重新开发一个遗留系统，将一篮子用户选择的零售产品与一个或多个有效促销相匹配。这些促销是行业标准的BOGOF（买一送一），买二送三，购买产品X和Y并获得10％的折扣，等等......但都要求您可以将潜在项目列表过滤到那些满足这些促销活动。

我希望解决方案能够在一次操作中获取一整篮零售商品并对其进行分析，而不是在订购时匹配单个产品的现有方法。（当前的解决方案导致了不良的限制）

每个促销活动都有一系列符合条件的产品，必须存在这些产品才能触发促销活动。它们排列在 n 组（或位置）中，例如：

Example "Buy two get third free" Promotion =

| Item 1 |             | Item 1 |             | Item 2 |
|   or   |             |   or   |             |   or   |
| Item 2 |     AND     | Item 4 |     AND     | Item 6 |
|   or   |             |   or   |             |   or   |
| Item 3 |             | Item 9 |             | Item 4 |

  Set 1                   Set 2                  Set 3

除非该商品多次出现在同一组中，否则每次促销活动必须包含每个组中的一种产品。促销可以有无限（但通常<10）“套”产品。

举个简单的例子，一个购物篮Item 1, Item 4 and Item 6会触发促销，同样的购物篮Item 1, Item 1 and Item 2也会触发它。然而，篮子Item 1, Item 2 and Item 3不会像每套都不满意。

除了检测何时触发促销的最佳方法这一显而易见的问题之外，我还需要恢复该项目已匹配到的集合（位置）以处理定价等细节。这也是可取的如果将更昂贵（以货币计）的商品分配给促销活动时，它们比更便宜（同等匹配）的商品更受青睐。

希望下一部分能帮助解决问题，不要听起来那么不清楚以至于会产生不必要的噪音，请随意忽略！

到目前为止，我最好的解决方案是为“购物篮”中的每个零售项目创建一个新的集合，其中包含该项目将满足的促销集（位置）。IE。

Item 1 satisifies sets: {1,2}
Item 4 satisifies sets: {2,3}
Item 6 satisifies sets: {3}

然后我的理论是你“检查”这个集合列表在每个位置都包含一个独特的项目，并且每个提升位置都被填充。到目前为止，我的工作示例都使用蛮力、循环或递归来生成集合的所有组合（上图），以尝试检查是否存在唯一组合。这非常糟糕，除了一个非常微不足道的例子之外的任何东西在现实世界中根本不起作用。（此函数将在商品添加到购物篮时实时调用，因此需要快速）

许多研究表明，二分匹配会产生一些预期的结果，但我只能找到关于该主题的研究文章和相当复杂的数学文本。一些伪代码或基本逻辑会很棒。

我的两个问题基本上是：

1) 有没有人看到一种更好/更快/更简单的方法来分析客户篮子以产生匹配的促销活动。
2) 假设我已经确定了将商品匹配到相关位置的最有效方式，那么确定要针对促销记录的零售商品清单的最便宜方式是什么。

任何帮助将不胜感激，因为我再也看不到隧道尽头的光了！（最终的解决方案将在 .NET 中，我们使用 SQL server 2008 R2。）

4

1 回答 1

1

检查给定购物车上的每个促销活动的有效性可以减少到Max Flow。在描述我的解决方案时，我假设您能够实现和解决基于图形的最大流量问题。如果不是，那是要解决的第二个问题（幸运的是，这是一个更普遍的问题）。

让算法的输入如下：

  • 一组所有有效项目I。不一定用于算法的最终编码。
  • C大小的购物车，包含物品n的子集。因此对于IC_1 ... C_nC = {C_i}i = 1...n
  • P由子集组成的单个促销活动m，每个子集包含可变数量的项目。每个子集S都是 的子集I。每个子集不能有重复项，但单个项目可以存在于多个子集中。

构造一个图G如下：

  • 添加一个超级源节点，标记为SOURCE
  • 添加一个超级汇节点，标记为SINK
  • C_i对于购物车中的每个唯一商品C，添加一个可用商品节点A_i，然后添加一条边 fromSOURCE到A_i，其容量等于C_iin的出现次数C。
  • S_i对于 Promotion中的每个子集P，添加以下内容：
    • 单个集合节点，以及具有容量S_i的从S_i到边。SINK1
    • 对于每个必需的项目I_j，S_i一个必需的项目节点B_i_j，以及从B_i_j到S_i具有容量的边1。
  • 最后，对于每对节点A_x，并且B_y它们所代表的项目是等价的，一条从A_x到的边B_y具有容量1。

SOURCE最后，以源和SINK汇运行最大流量算法。如果生成的最大流量的值等于子集的数量 ( m)，则输出 true - 此购物车可以满足促销活动。否则输出 false - 此购物车无法满足促销活动。

例如，对于您设置的示例，使用购物车{1,1,4,6}，应创建以下图表：

示例图例如

预期时间复杂度，其中项目n数为 ，促销中的子集数为m：

  • 图构建：
    • 添加SOURCE和SINK-O(1)
    • 从购物车和边缘添加独特的物品 -O(N)
    • 添加子集和所需的项目节点，以及 -O(N*M)
    • 将子集节点的边添加到接收器 -O(M)
    • 在相应的项目节点之间添加边 -O(N^2)
    • 全部的 -O(N^2 + N*M) = O(N * (N+M))
  • 最大流量算法 - 参见维基百科页面。简单的实施成本 - O((N*M)^3). 可以使用更复杂的算法进行改进。
  • 检索解决方案 - O(1)。
于 2016-01-21T18:04:12.497 回答