63

更新（2020 年 7 月）：问题已有 9 年历史，但仍然是我非常感兴趣的问题。从那以后，机器学习（RNN、CNN、GANS 等）、新方法和廉价 GPU 的兴起使新方法成为可能. 我认为重新审视这个问题以查看是否有新方法会很有趣。

我正在学习编程（Python 和算法），并试图从事一个我觉得有趣的项目。我已经创建了一些基本的 Python 脚本，但我不确定如何为我正在尝试构建的游戏找到解决方案。

以下是游戏的运作方式：

用户将获得具有值的项目。例如，

Apple = 1
Pears = 2
Oranges  = 3

然后他们将有机会选择他们喜欢的任何组合（即 100 个苹果、20 个梨和一个橙子）。计算机获得的唯一输出是总值（在本例中，当前为 143 美元）。计算机将尝试猜测他们拥有什么。显然它无法在第一回合正确地获得。

         Value    quantity(day1)    value(day1)
Apple      1        100                100
Pears      2         20                 40
Orange     3          1                  3
Total               121                143

下一回合，用户可以修改他们的数字，但不超过总量的 5%（或者我们可能选择的其他百分比。我将使用 5% 为例。）。水果的价格可以（随机）变化，因此总价值也可能基于此变化（为简单起见，我在此示例中没有更改水果价格）。使用上面的例子，在游戏的第 2 天，用户返回值 152 美元，在第 3 天返回 164 美元。下面是一个例子：

Quantity (day2)   %change (day2)    Value (day2)   Quantity (day3)   %change (day3)   Value(day3)
 104                                 104            106                                106
  21                                  42             23                                 46
   2                                   6              4                                 12
 127               4.96%             152            133               4.72%            164

*（我希望表格显示正确，我必须手动将它们隔开，所以希望它不仅仅是在我的屏幕上进行，如果它不起作用，请告诉我，我会尝试上传屏幕截图。）

我想看看我是否能弄清楚随着时间的推移数量是多少（假设用户有耐心继续输入数字）。我现在知道我唯一的限制是总值不能超过 5%，所以我现在不能达到 5% 的准确度，所以用户将永远输入它。

到目前为止我做了什么

到目前为止，这是我的解决方案（不多）。基本上，我获取所有值并找出它们的所有可能组合（我已经完成了这部分）。然后我将所有可能的组合作为字典放入数据库中（例如，对于 143 美元，可能有一个字典条目 {apple:143, Pears:0, Oranges:0}.. 一直到 {apple :0, Pears:1, Oranges:47}. 每次我得到一个新号码时我都会这样做，这样我就有了所有可能性的列表。

这就是我卡住的地方。在使用上述规则时，我怎样才能找出最好的解决方案？我想我需要一个适应度函数来自动比较这两天的数据，并消除任何与前几天数据的方差超过 5% 的可能性。

问题：

所以我的问题是用户更改总数并且我有一个所有概率的列表，我应该如何解决这个问题？我需要学习什么？是否有任何适用的算法或我可以使用的理论？或者，为了帮助我理解我的错误，你能建议我可以添加哪些规则来使这个目标可行（如果它不是当前状态。我在考虑添加更多水果并说他们必须至少选择 3 个，等等。） ? 另外，我对遗传算法只有模糊的了解，但我认为我可以在这里使用它们，如果有什么我可以使用的吗？

我非常非常渴望学习，所以任何建议或提示将不胜感激（只是请不要告诉我这个游戏是不可能的）。

更新：得到反馈，这很难解决。所以我想我会在游戏中添加另一个不会干扰玩家正在做的事情的条件（游戏对他们来说保持不变）但是每天水果的价值都会改变价格（随机）。这样会更容易解决吗？因为在 5% 的移动和某些水果值的变化内，随着时间的推移，只有少数组合是可能的。

第 1 天，一切皆有可能，获得足够接近的范围几乎是不可能的，但随着水果价格的变化，用户只能选择 5% 的变化，那么（随着时间的推移）范围不应该越来越窄。在上面的例子中，如果价格波动足够大，我想我可以暴力破解一个给我一个猜测范围的解决方案，但我试图弄清楚是否有更优雅的解决方案或其他解决方案来不断缩小这个范围时间。

UPDATE2：在阅读和询问之后，我相信这是一个隐藏的马尔科夫/维特比问题，它跟踪水果价格的变化以及总和（最后一个数据点的权重最重）。我不确定如何应用这种关系。我认为情况就是这样，可能是错误的，但至少我开始怀疑这是某种机器学习问题。

更新 3：我创建了一个测试用例（数字较小）和一个生成器来帮助自动化用户生成的数据，我正在尝试从中创建一个图表以查看更有可能发生的情况。

这是代码，以及用户实际水果数量的总值和评论。

#!/usr/bin/env python
import itertools

# Fruit price data
fruitPriceDay1 = {'Apple':1, 'Pears':2, 'Oranges':3}
fruitPriceDay2 = {'Apple':2, 'Pears':3, 'Oranges':4}
fruitPriceDay3 = {'Apple':2, 'Pears':4, 'Oranges':5}

# Generate possibilities for testing (warning...will not scale with large numbers)
def possibilityGenerator(target_sum, apple, pears, oranges):
    allDayPossible = {}
    counter = 1
    apple_range = range(0, target_sum + 1, apple)
    pears_range = range(0, target_sum + 1, pears)
    oranges_range = range(0, target_sum + 1, oranges)
    for i, j, k in itertools.product(apple_range, pears_range, oranges_range):
        if i + j + k == target_sum:
            currentPossible = {}

            #print counter
            #print 'Apple', ':', i/apple, ',', 'Pears', ':', j/pears, ',', 'Oranges', ':', k/oranges
            currentPossible['apple'] = i/apple
            currentPossible['pears'] = j/pears
            currentPossible['oranges'] = k/oranges

            #print currentPossible
            allDayPossible[counter] = currentPossible
            counter = counter +1
    return allDayPossible

# Total sum being returned by user for value of fruits
totalSumDay1=26 # Computer does not know this but users quantities are apple: 20, pears 3, oranges 0 at the current prices of the day
totalSumDay2=51 # Computer does not know this but users quantities are apple: 21, pears 3, oranges 0 at the current prices of the day
totalSumDay3=61 # Computer does not know this but users quantities are apple: 20, pears 4, oranges 1 at the current prices of the day
graph = {}
graph['day1'] = possibilityGenerator(totalSumDay1, fruitPriceDay1['Apple'], fruitPriceDay1['Pears'], fruitPriceDay1['Oranges'] )
graph['day2'] = possibilityGenerator(totalSumDay2, fruitPriceDay2['Apple'], fruitPriceDay2['Pears'], fruitPriceDay2['Oranges'] )
graph['day3'] = possibilityGenerator(totalSumDay3, fruitPriceDay3['Apple'], fruitPriceDay3['Pears'], fruitPriceDay3['Oranges'] )

# Sample of dict = 1 : {'oranges': 0, 'apple': 0, 'pears': 0}..70 : {'oranges': 8, 'apple': 26, 'pears': 13}
print graph
4

7 回答 7

23

我们将结合图论和概率：

第一天，建立一套所有可行的解决方案。让我们将解集表示为 A1={a1(1), a1(2),...,a1(n)}。

第二天，您可以再次构建解决方案集 A2。

现在，对于 A2 中的每个元素，您需要检查是否可以从 A1 的每个元素中到达它（给定 x% 容差）。如果是这样 - 将 A2(n) 连接到 A1(m)。如果无法从 A1(m) 中的任何节点访问它 - 您可以删除此节点。

基本上我们正在构建一个连通的有向无环图。

图中所有路径的可能性均等。只有从 Am 到 Am+1（从 Am 中的一个节点到 Am+1 中的一个节点）只有一条边，才能找到精确解。

当然，一些节点出现在比其他节点更多的路径中。每个节点的概率可以直接根据包含该节点的路径数推导出来。

通过为每个节点分配一个权重，该权重等于通向该节点的路径数，无需保留所有历史记录，只需保留前一天。

另外，看看非负值线性diphantine equations - 我刚才问的一个问题。接受的答案是枚举每个步骤中所有组合的好方法。

于 2011-10-08T11:06:58.987 回答
10

免责声明：由于我误读了问题的一些关键部分，因此在暂时删除我的答案并仔细重新阅读问题后，我大大改变了我的答案。虽然仍然引用了类似的主题和算法，但在我尝试自己解决 C# 中的一些问题后，答案得到了很大的改进。

好莱坞版

原版

首先，我想说明我在这里看到的两个主要问题：

  1. 可能的解决方案的绝对数量。只知道项目的数量和总值，例如 3 和 143，将产生很多可能的解决方案。另外，要让算法选择有效解决方案而不不可避免地尝试无效解决方案（总数不等于 143）并不容易。

  2. 当为给定的一天 D i找到可能的解决方案时，必须找到一种方法来消除具有由 { D i+1 .. D i+n } 给出的附加信息的潜在解决方案。

让我们为即将到来的示例奠定一些基础：

  • 让我们在整个游戏中保持相同的项目值。它可以是随机的，也可以由用户选择。
  • 可能的项目值绑定在 [1-10] 的非常有限的范围内，其中没有两个项目可以具有相同的值。
  • 任何项目的数量都不能超过 100。这意味着：[0-100]。

为了更容易解决这个问题，我冒昧地改变了一个约束，这使得算法收敛得更快：

  • “总量”规则被此规则覆盖：您可以在一天内添加或删除 [1-10] 范围内的任意数量的项目，总计。但是，您不能添加或删除相同数量的项目，总计超过两次。这也使游戏的最长生命周期为 20 天。

该规则使我们能够更轻松地排除解决方案。而且，对于非微小范围，使回溯算法仍然无用，就像您最初的问题和规则一样。

在我看来，这条规则不是游戏的本质，而只是一个促进者，使计算机能够解决问题。

问题 1：寻找潜在的解决方案

首先，问题 1.可以使用蒙特卡洛算法来解决，以找到一组潜在的解决方案。该技术很简单：为项目值和数量（在其各自可接受的范围内）生成随机数。对所需数量的项目重复该过程。验证解决方案是否可接受。这意味着验证项目是否具有不同的值并且总数等于我们的目标总数（例如，143。）

虽然这种技术具有易于实现的优点，但它也有一些缺点：

  • 不保证用户的解决方案会出现在我们的结果中。
  • 有很多“失误”。例如，考虑到我们的限制，大约需要 3,000,000 次尝试才能找到 1,000 个潜在解决方案。
  • 这需要很多时间：在我懒惰的笔记本电脑上大约需要 4 到 5 秒。

如何绕过这些缺点？出色地...

  • 将范围限制为较小的值和
  • 找到足够数量的潜在解决方案，以便用户的解决方案很有可能出现在您的解决方案集中。
  • 使用启发式方法更容易找到解决方案（稍后会详细介绍。）

请注意，您对范围的限制越多，蒙特卡洛算法的用处就越少，因为在合理的时间内将没有足够的有效解决方案来迭代它们。对于约束 { 3, [1-10], [0-100] }，大约有 741,000,000 个有效解决方案（不限于目标总值）。蒙特卡洛在那里可用。对于 { 3, [1-5], [0-10] }，只有大约 80,000 个。无需使用蒙特卡洛；蛮力for循环会做得很好。

我相信问题 1就是您所说的约束满足问题（或 CSP。）

问题 2：限制潜在解决方案的集合

鉴于问题 1是 CSP，我会继续调用问题 2以及一般的问题，即动态 CSP（或 DCSP）。

当问题的原始公式以某种方式改变时，[DCSPs] 很有用，通常是因为要考虑的约束集因环境而变化。DCSP 被视为一系列静态 CSP，每一个都是前一个 CSP 的转换，其中可以添加（限制）或删除（放松）变量和约束。

与 CSP 一起使用的一种可能对这个问题有用的技术称为约束记录：

  • 随着环境的每次变化（用户为 Di +1输入的值），查找有关新约束的信息：添加-删除约束可能“使用”的数量是多少。
  • 将约束应用于级联的每一天。涟漪效应可能会显着减少可能的解决方案。

为此，您需要每天获得一组新的可能解决方案；使用蛮力或蒙特卡洛。然后，将 D i与 D i-1的解进行比较，并仅保留可以在不违反约束条件的情况下继承前几天解的解。

您可能必须保留哪些解决方案导致其他解决方案的历史记录（可能在有向图中）。约束记录使您能够记住可能的添加 - 删除数量并基于此拒绝解决方案。

可以采取许多其他步骤来进一步改进您的解决方案。这里有一些想法：

  • 记录前几天解决方案中发现的项目值组合的约束。立即拒绝其他解决方案（因为项目值不得更改。）您甚至可以为每个现有解决方案找到较小的解决方案集，使用解决方案特定的约束来更早地拒绝无效的解决方案。
  • 每天生成一些“突变的”、完整的历史解决方案，以“修复” D 1解决方案集不包含用户解决方案的情况。您可以使用遗传算法根据现有的解决方案集找到突变种群。）
  • 使用启发式方法轻松找到解决方案（例如，当找到有效解决方案时，尝试通过替换数量来找到该解决方案的变体。）
  • 使用行为启发法来预测一些用户行为（例如，每个项目的相同数量、极端模式等）
  • 在用户输入新数量时继续进行一些计算。

考虑到所有这些，尝试根据解决方案的出现和启发式方法找出一个排名系统，以确定候选解决方案。

于 2011-10-10T19:29:31.493 回答
8

这个问题是不可能解决的。

假设您确切知道项目数量增加的比例，而不仅仅是最大比例是多少。

一个用户有 N 个水果，你有 D 天的猜测时间。

每天你会得到 N 个新变量，然后你总共有 D*N 个变量。

对于每一天，您只能生成两个方程。一个等式是 n_item*price 的总和，另一个是基于已知比率。如果它们都是独立的，那么总共最多有 2*D 方程。

2*D < N*D 对于所有 N > 2

于 2011-10-08T15:02:56.613 回答
4

我写了一个程序来玩这个游戏。当然，我必须自动化人类方面，但我相信我所做的一切都是为了在与真正的人类比赛时不应该使我的方法无效。

我从机器学习的角度来处理这个问题，并将问题视为一个隐藏的马尔可夫模型，其中总价格是观察值。我的解决方案是使用粒子过滤器。此解决方案是使用 NumPy 和 SciPy 用 Python 2.7 编写的。

我在注释中明确或在代码中隐含地陈述了我所做的任何假设。为了让代码以自动化方式运行，我还设置了一些额外的约束。它不是特别优化，因为我试图在可理解性而不是速度上犯错。

每次迭代都会输出当前的真实数量和猜测。我只是将输出通过管道传输到一个文件中，这样我就可以轻松地查看它。一个有趣的扩展是将输出绘制在 2D（2 个水果）或 3D（3 个水果）的图形上。然后您将能够看到粒子过滤器在解决方案上的磨练。

更新：

编辑代码以在调整后包含更新的参数。包括使用 matplotlib 的绘图调用（通过 pylab）。在 Linux-Gnome 上绘图工作，您的里程可能会有所不同。默认 NUM_FRUITS 为 2 以支持绘图。只需注释掉所有 pylab 调用以删除绘图并能够将 NUM_FRUITS 更改为任何内容。

可以很好地估计由 UnknownQuantities X 价格 = TotalPrice 表示的当前 fxn。在 2D（2 个水果）中，这是一条线，在 3D（3 个水果）中，它是一个平面。对于粒子过滤器而言，似乎数据太少，无法可靠地确定正确的数量。在粒子过滤器之上需要更多的智慧才能真正汇集历史信息。您可以尝试将粒子过滤器转换为二阶或三阶。

更新 2：

我一直在玩我的代码，很多。我尝试了很多东西，现在展示我将要制作的最终程序（开始对这个想法感到厌烦）。

变化：

粒子现在使用浮点而不是整数。不确定这是否有任何有意义的影响，但这是一个更通用的解决方案。仅在进行猜测时才进行整数舍入。

绘图将真实数量显示为绿色方块，当前猜测显示为红色方块。目前认为的粒子显示为蓝点（大小取决于我们相信它们的程度）。这使得很容易看到算法的工作情况。（绘图也在 Win 7 64 位上进行了测试和工作）。

添加了关闭/打开数量变化和价格变化的参数。当然，两者的“关”都没什么意思。

它做得非常好，但是，正如已经指出的那样，这是一个非常棘手的问题，所以很难得到准确的答案。关闭 CHANGE_QUANTITIES 会产生最简单的情况。您可以通过关闭 CHANGE_QUANTITIES 运行 2 个水果来了解问题的难度。看看它在正确答案上的速度有多快，然后看看当你增加水果的数量时它有多难。

您还可以通过保持 CHANGE_QUANTITIES 打开来了解难度，但将 MAX_QUANTITY_CHANGE 从非常小的值 (.001) 调整为“大”值 (.05)。

它挣扎的一种情况是维度（一个水果数量）接近于零。因为它使用粒子的平均值来猜测它总是会偏离像零这样的硬边界。

一般来说，这是一个很棒的粒子过滤器教程。

from __future__ import division
import random
import numpy
import scipy.stats
import pylab

# Assume Guesser knows prices and total
# Guesser must determine the quantities

# All of pylab is just for graphing, comment out if undesired
#   Graphing only graphs first 2 FRUITS (first 2 dimensions)

NUM_FRUITS = 3
MAX_QUANTITY_CHANGE = .01 # Maximum percentage change that total quantity of fruit can change per iteration
MAX_QUANTITY = 100 # Bound for the sake of instantiating variables
MIN_QUANTITY_TOTAL = 10 # Prevent degenerate conditions where quantities all hit 0
MAX_FRUIT_PRICE = 1000 # Bound for the sake of instantiating variables
NUM_PARTICLES = 5000
NEW_PARTICLES = 500 # Num new particles to introduce each iteration after guessing
NUM_ITERATIONS = 20 # Max iterations to run
CHANGE_QUANTITIES = True
CHANGE_PRICES = True

'''
  Change individual fruit quantities for a random amount of time
  Never exceed changing fruit quantity by more than MAX_QUANTITY_CHANGE
'''
def updateQuantities(quantities):
  old_total = max(sum(quantities), MIN_QUANTITY_TOTAL)
  new_total = old_total
  max_change = int(old_total * MAX_QUANTITY_CHANGE)

  while random.random() > .005: # Stop Randomly    
    change_index = random.randint(0, len(quantities)-1)
    change_val = random.randint(-1*max_change,max_change)

    if quantities[change_index] + change_val >= 0: # Prevent negative quantities
      quantities[change_index] += change_val
      new_total += change_val

      if abs((new_total / old_total) - 1) > MAX_QUANTITY_CHANGE:
        quantities[change_index] -= change_val # Reverse the change

def totalPrice(prices, quantities):
  return sum(prices*quantities)

def sampleParticleSet(particles, fruit_prices, current_total, num_to_sample):
  # Assign weight to each particle using observation (observation is current_total)
  # Weight is the probability of that particle (guess) given the current observation
  # Determined by looking up the distance from the hyperplane (line, plane, hyperplane) in a
  #   probability density fxn for a normal distribution centered at 0 
  variance = 2
  distances_to_current_hyperplane = [abs(numpy.dot(particle, fruit_prices)-current_total)/numpy.linalg.norm(fruit_prices) for particle in particles]
  weights = numpy.array([scipy.stats.norm.pdf(distances_to_current_hyperplane[p], 0, variance) for p in range(0,NUM_PARTICLES)])

  weight_sum = sum(weights) # No need to normalize, as relative weights are fine, so just sample un-normalized

  # Create new particle set weighted by weights
  belief_particles = []
  belief_weights = []
  for p in range(0, num_to_sample):
    sample = random.uniform(0, weight_sum)
    # sum across weights until we exceed our sample, the weight we just summed is the index of the particle we'll use
    p_sum = 0
    p_i = -1
    while p_sum < sample:
      p_i += 1
      p_sum += weights[p_i]
    belief_particles.append(particles[p_i])
    belief_weights.append(weights[p_i])

  return belief_particles, numpy.array(belief_weights)

'''
  Generates new particles around the equation of the current prices and total (better particle generation than uniformly random)
'''
def generateNewParticles(current_total, fruit_prices, num_to_generate):
  new_particles = []
  max_values = [int(current_total/fruit_prices[n]) for n in range(0,NUM_FRUITS)]
  for p in range(0, num_to_generate):
    new_particle = numpy.array([random.uniform(1,max_values[n]) for n in range(0,NUM_FRUITS)])
    new_particle[-1] = (current_total - sum([new_particle[i]*fruit_prices[i] for i in range(0, NUM_FRUITS-1)])) / fruit_prices[-1]
    new_particles.append(new_particle)
  return new_particles


# Initialize our data structures:
# Represents users first round of quantity selection
fruit_prices = numpy.array([random.randint(1,MAX_FRUIT_PRICE) for n in range(0,NUM_FRUITS)])
fruit_quantities = numpy.array([random.randint(1,MAX_QUANTITY) for n in range(0,NUM_FRUITS)])
current_total = totalPrice(fruit_prices, fruit_quantities)
success = False

particles = generateNewParticles(current_total, fruit_prices, NUM_PARTICLES) #[numpy.array([random.randint(1,MAX_QUANTITY) for n in range(0,NUM_FRUITS)]) for p in range(0,NUM_PARTICLES)]
guess = numpy.average(particles, axis=0)
guess = numpy.array([int(round(guess[n])) for n in range(0,NUM_FRUITS)])

print "Truth:", str(fruit_quantities)
print "Guess:", str(guess)

pylab.ion()
pylab.draw()
pylab.scatter([p[0] for p in particles], [p[1] for p in particles])
pylab.scatter([fruit_quantities[0]], [fruit_quantities[1]], s=150, c='g', marker='s')
pylab.scatter([guess[0]], [guess[1]], s=150, c='r', marker='s')
pylab.xlim(0, MAX_QUANTITY)
pylab.ylim(0, MAX_QUANTITY)
pylab.draw()

if not (guess == fruit_quantities).all():
  for i in range(0,NUM_ITERATIONS):
    print "------------------------", i

    if CHANGE_PRICES:
      fruit_prices = numpy.array([random.randint(1,MAX_FRUIT_PRICE) for n in range(0,NUM_FRUITS)])

    if CHANGE_QUANTITIES:
      updateQuantities(fruit_quantities)
      map(updateQuantities, particles) # Particle Filter Prediction

    print "Truth:", str(fruit_quantities)
    current_total = totalPrice(fruit_prices, fruit_quantities)

    # Guesser's Turn - Particle Filter:
    # Prediction done above if CHANGE_QUANTITIES is True

    # Update
    belief_particles, belief_weights = sampleParticleSet(particles, fruit_prices, current_total, NUM_PARTICLES-NEW_PARTICLES)
    new_particles = generateNewParticles(current_total, fruit_prices, NEW_PARTICLES)

    # Make a guess:
    guess = numpy.average(belief_particles, axis=0, weights=belief_weights) # Could optimize here by removing outliers or try using median
    guess = numpy.array([int(round(guess[n])) for n in range(0,NUM_FRUITS)]) # convert to integers
    print "Guess:", str(guess)

    pylab.cla()
    #pylab.scatter([p[0] for p in new_particles], [p[1] for p in new_particles], c='y') # Plot new particles
    pylab.scatter([p[0] for p in belief_particles], [p[1] for p in belief_particles], s=belief_weights*50) # Plot current particles
    pylab.scatter([fruit_quantities[0]], [fruit_quantities[1]], s=150, c='g', marker='s') # Plot truth
    pylab.scatter([guess[0]], [guess[1]], s=150, c='r', marker='s') # Plot current guess
    pylab.xlim(0, MAX_QUANTITY)
    pylab.ylim(0, MAX_QUANTITY)
    pylab.draw()

    if (guess == fruit_quantities).all():
      success = True
      break

    # Attach new particles to existing particles for next run:
    belief_particles.extend(new_particles)
    particles = belief_particles
else:
  success = True

if success:
  print "Correct Quantities guessed"
else:
  print "Unable to get correct answer within", NUM_ITERATIONS, "iterations"

pylab.ioff()
pylab.show()
于 2011-10-13T23:20:37.350 回答
2

对于您的初始规则：

从我的学生时代，我会说，如果我们对 5% 的变化进行抽象，我们每天都有一个具有三个未知值的方程（对不起，我不知道英语中的数学词汇），这些值与以前的值相同天。在第 3 天，你有三个方程，三个未知值，并且解决方案应该是直接的。

我猜如果三个元素的值足够不同，每天 5% 的变化可能会被遗忘，因为正如你所说，我们将使用近似值并对数字进行四舍五入。

对于您适应的规则：

在这种情况下，太多的未知数和变化的值，所以我知道没有直接的解决方案。在这点上我相信 Lior；他的方法看起来不错！（如果您的价格和数量范围有限。）

于 2011-10-12T20:49:50.743 回答
1

我意识到我的答案变得很冗长，所以我将代码移到了顶部（这可能是大多数人感兴趣的）。在它下面有两件事：

  1. 解释为什么（深度）神经网络不是解决这个问题的好方法，以及
  2. 解释为什么我们不能用给定的信息唯一地确定人类的选择。

对于那些对任一主题感兴趣的人，请参阅下文。对于你们其他人，这里是代码。

找到所有可能解决方案的代码

正如我在答案中进一步解释的那样，您的问题未确定。在平均情况下，有许多可能的解决方案，并且随着天数的增加，这个数字至少呈指数增长。对于原始问题和扩展问题都是如此。尽管如此，我们可以（某种程度上）有效地找到所有解决方案（这很难，所以不要期望太多）。

回溯（从 1960 年代开始，所以不完全是现代的）是这里选择的算法。在python中，我们可以把它写成递归生成器，其实挺优雅的：

def backtrack(pos, daily_total, daily_item_value, allowed_change, iterator_bounds, history=None):
    if pos == len(daily_total):
        yield np.array(history)
        return

    it = [range(start, stop, step) for start, stop, step in iterator_bounds[pos][:-1]]
    for partial_basket in product(*it):
        if history is None:
            history = [partial_basket]
        else:
            history.append(partial_basket)

        # ensure we only check items that match the total basket value
        # for that day
        partial_value = np.sum(np.array(partial_basket) * daily_item_value[pos, :-1])
        if (daily_total[pos] - partial_value) % daily_item_value[pos, -1] != 0:
            history.pop()
            continue

        last_item = (daily_total[pos] - partial_value) // daily_item_value[pos, -1]
        if last_item < 0:
            history.pop()
            continue

        basket = np.array([*partial_basket] + [int(last_item)])
        basket_value = np.sum(basket * daily_item_value[pos])
        history[-1] = basket
        if len(history) > 1:
            # ensure that today's basket stays within yesterday's range
            previous_basket = history[-2]
            previous_basket_count = np.sum(previous_basket)
            current_basket_count = np.sum(basket)
            if (np.abs(current_basket_count - previous_basket_count) > allowed_change * previous_basket_count):
                history.pop()
                continue

        yield from backtrack(pos + 1, daily_total, daily_item_value, allowed_change, iterator_bounds, history)
        history.pop()

这种方法本质上将所有可能的候选者构造成一棵大树，然后在违反约束时执行深度优先搜索并进行修剪。每当遇到叶节点时，我们都会产生结果。

树搜索（通常）可以并行化，但这超出了这里的范围。如果没有太多额外的见解，它将使解决方案的可读性降低。这同样适用于减少代码的持续开销，例如，将约束处理if ...: continue到iterator_bounds变量中并减少检查。

我将完整的代码示例（包括游戏人性化的模拟器）放在这个答案的底部。

针对这个问题的现代机器学习

问题已有 9 年历史，但仍然是我非常感兴趣的问题。从那以后，机器学习（RNN、CNN、GANS 等）、新方法和廉价 GPU 的兴起使新方法成为可能。我认为重新审视这个问题以查看是否有新方法会很有趣。

我真的很喜欢你对深度神经网络世界的热情；不幸的是，由于以下几个原因，它们根本不适用于这里：

  1. （精确性）如果您需要一个精确的解决方案，例如您的游戏，NN 无法提供。
  2. （整数约束）当前主流的 NN 训练方法是基于梯度下降的，因此问题必须是可微的，或者您需要能够以使其变得可微的方式重新表述它；将自己限制为整数会扼杀摇篮中的 GD 方法。您可以尝试进化算法来搜索参数化。这确实存在，但这些方法目前还不太成熟。
  3. （非凸性）在典型的公式中，训练 NN 是一种局部方法，这意味着如果您的算法收敛，您将准确找到 1 个（局部最优）解。在一般情况下，您的游戏对于原始版本和扩展版本都有许多可能的解决方案。这不仅意味着 - 平均而言 - 你无法弄清楚人类的选择（篮子），而且你无法控制 NN 会找到众多解决方案中的哪一个。当前的神经网络成功案例也遭受了同样的命运，但他们往往并不在意，因为他们只想要一些解决方案而不是特定的解决方案。一些好的解决方案完全没有解决方案。
  4. （专家领域知识）对于这个游戏，你有很多领域知识可以用来改进优化/学习。充分利用 NN 中的任意领域知识并非易事，对于这个游戏，构建自定义 ML 模型（不是神经网络）会更容易、更高效。

为什么游戏不能唯一解决 - 第 1 部分

让我们首先考虑一个替代问题并取消整数要求，即篮子（人类在N一天内选择的水果）可以有分数水果（0.3 个橙子）。

总价值约束np.dot(basket, daily_price) == total_value限制了篮子的可能解决方案；它将问题减少了一维。自由选择N-1水果的数量，你总能找到第 N 个水果的值来满足约束。所以，看似N一天可以做出的选择，其实只有N-1我们可以自由做出的选择，而最后的选择完全取决于我们之前的选择。因此，对于游戏进行的每一天，我们都需要估计一个额外的N-1选择/变量。

我们可能希望强制所有选项都大于 0，但这只会减少我们可以从中选择数字的区间；任何实数的开区间都有无限多的数字，所以我们永远不会因为这个而没有选择。仍然N-1需要做出选择。

在两天之间，篮子的总交易量np.sum(basket)最多只变化some_percent前一天的大部分时间，即np.abs(np.sum(previous_basket) - np.sum(basket)) <= some_percent * np.sum(previous_basket)。我们在某一天可以做出的一些选择将比前一天改变更多的篮子some_percent。为了确保我们永远不会违反这一点，我们可以自由地做出N-2选择，然后必须选择N-1-th 变量，以便添加它并添加N-the 变量（从我们之前的选择中固定）保持在some_percent. （注意：这是一个不等式约束，所以它只会在我们相等的情况下减少选择的数量，即篮子的变化恰好是some_percent。在优化理论中，这被称为约束是活动的。）

我们可以再次考虑所有选择都应该大于 0 的约束，但争论仍然是，这只是改变了我们现在可以自由选择N-2变量的区间。

因此，D几天后，我们可以N-1选择从第一天开始进行估算（没有变化约束），并(D-1)*(N-2)可以选择在接下来的每一天进行估算。不幸的是，我们没有进一步减少这个数字的限制，并且未知数的数量至少N-2每天都在增长。这本质上就是 Luka Rahne 所指的“ 2*D < N*D for all N > 2”。我们很可能会找到许多同样可能的候选人。

每天的确切食品价格对此无关紧要。只要它们具有一定的价值，它们就会限制其中一种选择。因此，如果您以您指定的方式扩展您的游戏，那么总是有机会获得无限多的解决方案；不管天数。

为什么游戏仍然无法唯一解决 - 第 2 部分

有一个我们没有看到的约束可能有助于解决这个问题：只允许整数解作为选择。整数约束的问题在于它们处理起来非常复杂。然而，我们在这里主要关心的是，如果添加这个约束将允许我们在足够的天数下唯一地解决问题。为此，有一个相当直观的反例。假设您有连续 3 天，并且对于第 1 天和第 3 天，总价值约束只允许一个篮子。换句话说，我们知道第 1 天和第 3 天的篮子，但不知道第 2 天的篮子。在这里，我们只知道它的总值，它在some_percent第 1 天之内，而第 3 天在some_percent第 2 天之内。这样就够了吗总能计算出第 2 天篮子里有什么的信息？

some_percent = 0.05
Day 1: basket: [3 2]  prices: [10 7]  total_value: 44
Day 2: basket: [x y]  prices: [5  5]  total_value: 25
Day 3: basket: [2 3]  prices: [9  5]  total_value: 33

Possible Solutions Day 2: [2 3], [3 2]

上面是一个例子，由于总价值限制，我们知道两天的价值，但这仍然不允许我们在第 2 天计算出篮子的确切组成。因此，虽然它可能工作它在某些情况下是不可能的，一般来说是不可能的。在第 3 天之后添加更多天数根本无助于计算第 2 天。它可能有助于缩小第 3 天的选择范围（这将缩小第 2 天的选择范围），但我们已经只剩下第 3 天的 1 个选择，所以没有用。

完整代码

import numpy as np
from itertools import product
import tqdm


def sample_uniform(n, r):
    # check out: http://compneuro.uwaterloo.ca/files/publications/voelker.2017.pdf
    sample = np.random.rand(n + 2)
    sample_norm = np.linalg.norm(sample)
    unit_sample = (sample / sample_norm)
    change = np.floor(r * unit_sample[:-2]).astype(np.int)
    return change


def human(num_fruits, allowed_change=0.05, current_distribution=None):
    allowed_change = 0.05
    if current_distribution is None:
        current_distribution = np.random.randint(1, 50, size=num_fruits)
    yield current_distribution.copy()

    # rejection sample a suitable change
    while True:
        current_total = np.sum(current_distribution)
        maximum_change = np.floor(allowed_change * current_total)

        change = sample_uniform(num_fruits, maximum_change)
        while np.sum(change) > maximum_change:
            change = sample_uniform(num_fruits, maximum_change)

        current_distribution += change
        yield current_distribution.copy()


def prices(num_fruits, alter_prices=False):
    current_prices = np.random.randint(1, 10, size=num_fruits)
    while True:
        yield current_prices.copy()
        if alter_prices:
            current_prices = np.random.randint(1, 10, size=num_fruits)


def play_game(num_days, num_fruits=3, alter_prices=False):
    human_choice = human(num_fruits)
    price_development = prices(num_fruits, alter_prices=alter_prices)

    history = {
        "basket": list(),
        "prices": list(),
        "total": list()
    }
    for day in range(num_days):
        choice = next(human_choice)
        price = next(price_development)
        total_price = np.sum(choice * price)

        history["basket"].append(choice)
        history["prices"].append(price)
        history["total"].append(total_price)

    return history


def backtrack(pos, daily_total, daily_item_value, allowed_change, iterator_bounds, history=None):
    if pos == len(daily_total):
        yield np.array(history)
        return

    it = [range(start, stop, step) for start, stop, step in iterator_bounds[pos][:-1]]
    for partial_basket in product(*it):
        if history is None:
            history = [partial_basket]
        else:
            history.append(partial_basket)

        # ensure we only check items that match the total basket value
        # for that day
        partial_value = np.sum(np.array(partial_basket) * daily_item_value[pos, :-1])
        if (daily_total[pos] - partial_value) % daily_item_value[pos, -1] != 0:
            history.pop()
            continue

        last_item = (daily_total[pos] - partial_value) // daily_item_value[pos, -1]
        if last_item < 0:
            history.pop()
            continue

        basket = np.array([*partial_basket] + [int(last_item)])
        basket_value = np.sum(basket * daily_item_value[pos])
        history[-1] = basket
        if len(history) > 1:
            # ensure that today's basket stays within relative tolerance
            previous_basket = history[-2]
            previous_basket_count = np.sum(previous_basket)
            current_basket_count = np.sum(basket)
            if (np.abs(current_basket_count - previous_basket_count) > allowed_change * previous_basket_count):
                history.pop()
                continue

        yield from backtrack(pos + 1, daily_total, daily_item_value, allowed_change, iterator_bounds, history)
        history.pop()


if __name__ == "__main__":
    np.random.seed(1337)
    num_fruits = 3
    allowed_change = 0.05
    alter_prices = False
    history = play_game(15, num_fruits=num_fruits, alter_prices=alter_prices)

    total_price = np.stack(history["total"]).astype(np.int)
    daily_price = np.stack(history["prices"]).astype(np.int)
    basket = np.stack(history["basket"]).astype(np.int)

    maximum_fruits = np.floor(total_price[:, np.newaxis] / daily_price).astype(np.int)
    iterator_bounds = [[[0, maximum_fruits[pos, fruit], 1] for fruit in range(num_fruits)] for pos in range(len(basket))]
    # iterator_bounds = np.array(iterator_bounds)
    # import pdb; pdb.set_trace()

    pbar = tqdm.tqdm(backtrack(0, total_price,
                               daily_price, allowed_change, iterator_bounds), desc="Found Solutions")
    for solution in pbar:
        # test price guess
        calculated_price = np.sum(np.stack(solution) * daily_price, axis=1)
        assert np.all(calculated_price == total_price)

        # test basket change constraint
        change = np.sum(np.diff(solution, axis=0), axis=1)
        max_change = np.sum(solution[:-1, ...], axis=1) * allowed_change
        assert np.all(change <= max_change)

        # indicate that we found the original solution
        if not np.any(solution - basket):
            pbar.set_description("Found Solutions (includes original)")
于 2020-07-08T09:54:32.997 回答
0

当玩家选择将可能性数量减少到1的组合时，计算机将获胜。否则，玩家可以选择总和在一定百分比内变化的约束的组合，该计算机可能永远不会获胜。

import itertools
import numpy as np


def gen_possible_combination(total, prices):
    """
    Generates all possible combinations of numbers of items for
    given prices constraint by total
    """
    nitems = [range(total//p + 1) for p in prices]
    prices_arr = np.array(prices)
    combo = [x for x in itertools.product(
        *nitems) if np.dot(np.array(x), prices_arr) == total]

    return combo


def reduce(combo1, combo2, pct):
    """
    Filters impossible transitions which are greater than pct
    """
    combo = {}
    for x in combo1:
        for y in combo2:
            if abs(sum(x) - sum(y))/sum(x) <= pct:
                combo[y] = 1

    return list(combo.keys())


def gen_items(n, total):
    """
    Generates a list of items
    """
    nums = [0] * n
    t = 0
    i = 0
    while t < total:
        if i < n - 1:
            n1 = np.random.randint(0, total-t)
            nums[i] = n1
            t += n1
            i += 1
        else:
            nums[i] = total - t
            t = total

    return nums


def main():
    pct = 0.05
    i = 0
    done = False
    n = 3
    total_items = 26  # np.random.randint(26)
    combo = None
    while not done:
        prices = [np.random.randint(1, 10) for _ in range(n)]
        items = gen_items(n, total_items)

        total = np.dot(np.array(prices),  np.array(items))
        combo1 = gen_possible_combination(total, prices)

        if combo:
            combo = reduce(combo, combo1, pct)
        else:
            combo = combo1
        i += 1
        print(i, 'Items:', items, 'Prices:', prices, 'Total:',
              total, 'No. Possibilities:', len(combo))

        if len(combo) == 1:
            print('Solution', combo)
            break
        if np.random.random() < 0.5:
            total_items = int(total_items * (1 + np.random.random()*pct))
        else:
            total_items = int(
                np.ceil(total_items * (1 - np.random.random()*pct)))


if __name__ == "__main__":
    main()
于 2020-07-12T10:15:26.297 回答