algorithm - 非重叠购买的最优顺序

Question

我认为这是一个调度问题，但我什至不确定！我想要的是找到非重叠购买决策的最佳顺序，当我完全了解它们的价值以及未来会出现什么机会时。

想象一个批发商销售我想为自己的商店购买的各种商品。在任何时候，他们可能会推出多项特别优惠；我会以全价出售，所以他们的折扣就是我的利润。

我想最大化利润，但问题是我一次只能买一件东西，没有信用这样的东西，更糟糕的是，交货延迟。好消息是商品一到货我就卖掉，然后我就可以再花钱了。因此，通过所有选择的一条路径可能是：我星期一买了 100 公斤的苹果，它们在星期二交货。然后我买了 20 件修女服装，在星期天送来，还算合适。我跳过了几天，因为我知道周三他们会以很大的折扣购买法拉利。所以我买了其中一个，它在下周二交付。等等。

您可以考虑复利或不复利。该算法归结为在选择今天的特别优惠之一或等待一天（因为明天会有更好的东西）之间的每个阶段的决定。

让我们抽象一下。购买和交付成为时代以来的日子。利润写为卖出价格除以买入价格。即 1.00 意味着盈亏平衡，1.10 意味着 10% 的利润，2.0 意味着我的钱翻了一番。

  buy    delivery   profit
    1        2       1.10    Apples
    1        3       1.15    Viagra
    2        3       1.15    Notebooks
    3        7       1.30    Nun costumes
    4        7       1.28    Priest costumes
    6        7       1.09    Oranges
    6        8       1.11    Pears
    7        9       1.16    Yellow shoes
    8       10       1.15    Red shoes
   10       15       1.50    Red Ferrari
   11       15       1.40    Yellow Ferrari
   13       16       1.25    Organic grapes
   14       19       1.30    Organic wine

注意：机会只存在于购买日（例如，如果没有人购买有机葡萄，它们就会被制成葡萄酒！），我可以在交货的同一天出售，但直到第二天才能购买我的下一件商品。所以我不能在 t=7 卖掉我的修女服装，然后立即在 t=7 买黄鞋。

我希望存在一个已知的最佳算法，并且已经有一个 R 模块，但算法或学术文献也会很好，就像任何其他语言的任何东西一样。速度很重要，但主要是当数据变大时，所以我想知道它是 O(n ² ) 还是其他什么。

顺便说一句，如果有最大可能的交付延迟，最好的算法会改变吗？例如，如果delivery - buy <= 7

以下是上述 CSV 格式的数据：

buy,delivery,profit,item
1,2,1.10,Apples
1,3,1.15,Viagra
2,3,1.15,Notebooks
3,7,1.30,Nun costumes
4,7,1.28,Priest costumes
6,7,1.09,Oranges
6,8,1.11,Pears
7,9,1.16,Yellow shoes
8,10,1.15,Red shoes
10,15,1.50,Red Ferrari
11,15,1.40,Yellow Ferrari
13,16,1.25,Organic grapes
14,19,1.30,Organic wine

或作为 JSON：

{"headers":["buy","delivery","profit","item"],"data":[[1,2,1.1,"Apples"],[1,3,1.15,"Viagra"],[2,3,1.15,"Notebooks"],[3,7,1.3,"Nun costumes"],[4,7,1.28,"Priest costumes"],[6,7,1.09,"Oranges"],[6,8,1.11,"Pears"],[7,9,1.16,"Yellow shoes"],[8,10,1.15,"Red shoes"],[10,15,1.5,"Red Ferrari"],[11,15,1.4,"Yellow Ferrari"],[13,16,1.25,"Organic grapes"],[14,19,1.3,"Organic wine"]]}

或作为 R 数据框：

structure(list(buy = c(1L, 1L, 2L, 3L, 4L, 6L, 6L, 7L, 8L, 10L, 
11L, 13L, 14L), delivery = c(2L, 3L, 3L, 7L, 7L, 7L, 8L, 9L, 
10L, 15L, 15L, 16L, 19L), profit = c(1.1, 1.15, 1.15, 1.3, 1.28, 
1.09, 1.11, 1.16, 1.15, 1.5, 1.4, 1.25, 1.3), item = c("Apples", 
"Viagra", "Notebooks", "Nun costumes", "Priest costumes", "Oranges", 
"Pears", "Yellow shoes", "Red shoes", "Red Ferrari", "Yellow Ferrari", 
"Organic grapes", "Organic wine")), .Names = c("buy", "delivery", 
"profit", "item"), row.names = c(NA, -13L), class = "data.frame")

链接

是否有任何 R 图形包（最短路径等）？ （igraph提供了一个 shortest.paths 函数，除了 C 库之外，还有一个R 包和一个 python 接口）

Answer 1

考虑这个问题的最简单方法类似于最短路径问题（尽管将其视为最大流量问题在技术上可能更好）。天数 1 ... 19 可用作节点名称；每个节点j都有一个到节点j+1的链接，权重为 1，列表中的每个产品 ( b,d,g,p ) 都添加了从第b天到第d+1天的链接，权重为g。当我们在寻路时遍历节点时，我们会跟踪迄今为止在每个节点上看到的最佳乘法值。

下面显示的 Python 代码运行时间为 O(V+E)，其中 V 是顶点数（或天数），E 是边数。在这个实现中，E = V + 正在销售的产品数量。 补充说明：i, t in enumerate(graf)的循环：对每个顶点处理一次。在该循环中，for e in edges:将当前顶点的边各处理一次。因此，没有边缘被处理超过一次，因此性能为 O(V+E)。

编辑注释 2： krjampani 声称 O(V+E) 比 O(n log n) 慢，其中 n 是产品数量。但是，除非我们对考虑的天数做出假设，否则这两个订单是不可比较的。请注意，如果交货延迟是有界的并且产品日期重叠，则天数为 O(n)，其中 O(V+E) = O(n)，这比 O(n log n) 快。

但是，在一组给定的假设下，我的方法和 krjampani 的运行时间顺序可能相同：对于大量天数，更改我的方法以仅在 x[0] 和 x[ 的排序联合中创建图节点1] 值，并使用指向 day[i-1] 和 day[i+1] 而不是指向 i-1 和 i+1 的链接。对于少数天数，将 krjampani 的方法更改为使用 O(n) 计数排序。

该程序的输出如下所示：

 16 :   2.36992 [11, 15, 1.4, 'Yellow Ferrari']
 11 :   1.6928 [8, 10, 1.15, 'Red shoes']
 8 :    1.472 [4, 7, 1.28, 'Priest costumes']
 4 :    1.15 [1, 3, 1.15, 'Viagra']

这表明在第 15 天卖出黄色法拉利后，我们在第 16 天获得了 2.36992 的复合利润；在卖出红鞋后到达第 11 天，获利 1.6928；等等。请注意，产品列表开头的虚拟条目以及数字周围引号的删除是与 JSON 数据的主要区别。列表元素中的条目以graf[j]开头[1, j-1, 0, [[j+1,1,0]]]，即形式为 [best-value-so-far, best-from-node#, best-from-product-key, edge-list]。每个边缘列表都是一个列表列表，其形式为 [next-node#, edge-weight, product-key]。将产品 0 设为虚拟产品可简化初始化。

products = [[0,0,0,""],[1,2,1.10,"Apples"],[1,3,1.15,"Viagra"],[2,3,1.15,"Notebooks"],[3,7,1.30,"Nun costumes"],[4,7,1.28,"Priest costumes"],[6,7,1.09,"Oranges"],[6,8,1.11,"Pears"],[7,9,1.16,"Yellow shoes"],[8,10,1.15,"Red shoes"],[10,15,1.50,"Red Ferrari"],[11,15,1.40,"Yellow Ferrari"],[13,16,1.25,"Organic grapes"],[14,19,1.30,"Organic wine"]]
hiDay = max([x[1] for x in products])
graf = [[1, i-1, 0, [[i+1,1,0]]] for i in range(2+hiDay)]

for i, x in enumerate(products):
    b, d, g, p = x[:]
    graf[b][3] += [[d+1, g, i]] # Add an edge for each product

for i, t in enumerate(graf):
    if i > hiDay: break
    valu = t[0]                 # Best value of path to current node
    edges = t[3]                # List of edges out of current node
    for e in edges:
        link, gain, prod = e[:]
        v = valu * gain;
        if v > graf[link][0]:
            graf[link][0:3] = [v, i, prod]

day = hiDay
while day > 0:
    if graf[day][2] > 0:
        print day, ":\t", graf[day][0], products[graf[day][2]]
    day = graf[day][1]

Answer 2

这个问题自然地映射到在一组加权区间中找到最大权重独立区间的问题。输入集中的每个项目对应一个区间，其起点和终点是购买和交货日期，项目的利润代表区间的权重。最大权重独立区间问题是找到一组总权重最大的不相交区间。

该问题可以通过O(n log n)以下方式解决。按它们的端点对间隔进行排序（见图）。然后，我们遍历排序列表中的每个区间i，并计算由排序列表中的区间组成的子问题的最优解1...i。区间问题的最优解1...i是以下的最大值：

1. The optimal solution of the problem for intervals `1...(i-1)` in the 
   sorted list or

2. Weight of interval `i` + the optimal solution of the problem for intervals 
   `1...j`, where j is the last interval in the sorted list whose end-point
   is less than the start-point of `i`.

请注意，该算法运行O(n log n)并计算排序列表的每个前缀的最优解的值。在我们运行这个算法之后，我们可以以相反的顺序遍历排序列表，并根据为每个前缀计算的值找到最优解中存在的区间。

编辑：

为了使其正常工作，间隔的权重应该是相应项目的实际利润（即它们应该是 sell_price - buy_price）。

更新 2：运行时间

设为天数（遵循jwpat7V的符号）。如果V远小于O(n log n)，我们可以使用计数排序对时间间隔进行排序，O(n + V)并使用一个大小数组V来记录子问题的解决方案。这种方法导致时间复杂度为O(V + n)。所以算法的运行时间为min(O(V+n), O(n log n))。

Answer 3

这是一个动态规划问题。做出整体最优选择只需要在每一步都做出最优选择。您可以制作一个表格，描述基于先前状态的每个步骤的最佳选择以及从该状态采取各种步骤的利润。您可以通过消除明显不理想的可能性，将大量可能性合并成一个较小的集合。

在您的问题中，影响选择的唯一状态是交货日期。例如，在第一天，您有三个选择：您可以购买苹果，将利润设置为 1.10，将交货日期设置为 2；购买伟哥，将您的利润设置为 1.15，并将您的交货日期设置为 3；或者什么都不买，将您的利润设置为零，并将交货日期设置为 2。我们可以像这样表示这些替代方案：

(choices=[apples], delivery=2, profit=1.10) or
(choices=[viagra], delivery=3, profit=1.15) or
(choices=[wait],   delivery=2, profit=0.00)

就做出未来决定而言，您在第一天购买伟哥还是什么都不买都没有任何区别。无论哪种方式，您可以购买的第二天是第二天，因此您可以消除等待作为替代方案，因为利润较低。但是，如果您购买苹果，与购买伟哥或等待相比，这将影响未来的决策，因此您必须考虑另一种选择。这只会在第一天结束时为您提供这些替代方案。

(choices=[apples], delivery=2, profit=1.10) or 
(choices=[viagra], delivery=3, profit=1.15)

第二天，您需要根据第一天的替代方案来考虑您的替代方案。这产生了三种可能性：

(choices=[apples,notebooks], delivery=3, profit=2.25) or
(choices=[apples,wait],      delivery=3, profit=1.10) or
(choices=[viagra,wait],      delivery=3, profit=1.15)

就考虑未来的决定而言，所有这三个选择都使您处于相同的状态，因为它们都将交货日期设置为 3，因此您只需选择具有最大利润的一个：

(choices=[apples,notebooks], delivery=3, profit=2.25)

继续第三天，你有两个选择

(choices=[apples,notebooks,wait],         delivery=4, profit=2.25)
(choices=[apples,notebooks,nun costumes], delivery=7, profit=3.55)

这两种选择都必须保留，因为它们将以不同的方式影响未来的决定。

请注意，我们只是根据交货日期和利润来做出未来的决定。我们跟踪选择，以便我们可以在最后报告最佳选择集。

现在也许你可以看到模式。你有一组备选方案，当你有多个备选方案具有相同的交货日期时，你只需选择利润最大的一个，并消除其他的。这种折叠替代方案的过程可以防止问题呈指数级增长，从而使其得到有效解决。

Answer 4

您可以将其作为线性规划问题来解决。这是解决物流问题的标准方法，例如航空公司和公司面临的问题，问题空间比您的要大得多。我不会在这里正式定义您的问题，而是从广义上讲：您的目标函数是利润最大化。您可以将购买天数和“每天仅购买一次”表示为线性约束。

标准的线性规划算法是单纯形法。尽管它具有指数级的最坏情况行为，但在实践中，它往往对实际问题非常有效。有很多很好的免费实现。我最喜欢的是GNU 线性编程工具包。R 有一个到 GLPK 的接口。Lp_solve是另一个著名的项目，它也有一个R 接口。每种情况下的基本方法是正式定义您的问题，然后将其交给第三方解决方案来完成。

要了解更多信息，我建议您查看算法设计手册，它应该为您提供足够的背景来进行在线进一步研究。p.412 以后是对线性规划及其变体的全面总结（例如，如果您有完整性约束，则为整数规划）。

如果您以前从未听说过线性规划，您可能想看看一些如何使用它的示例。我真的很喜欢这组简单的 Python 教程问题。它们包括最大化猫粮罐头的利润，以及解决数独问题。