如何处理数字猜谜游戏(带扭曲)算法？

Question

我正在学习编程(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天,用户在第3天返回$ 152和$ 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%的变化,那么不应该(随着时间的推移)范围变窄和变窄.在上面的例子中,如果价格足够波动,我想我可以强行推出一个解决方案给我一个范围来猜测,但我想弄清楚是否有一个更优雅的解决方案或其他解决方案来保持缩小这个范围时间.

更新2:在阅读并询问后,我相信这是一个隐藏的马尔可夫/维特比问题,它跟踪水果价格的变化以及总和(加权最后的数据点最重).我不知道如何应用这种关系.我认为情况确实如此,但至少我开始怀疑这是某种类型的机器学习问题.

更新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

Answer 1

我们将图论与概率结合起来:

在第一天,建立一套所有可行的解决方案.Lets表示设置为A1 = {a1(1),a1(2),...,a1(n)}的解.

在第二天,您可以再次构建解决方案集A2.

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

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

图中的所有路径都具有相同的可能性.只有当存在从Am到Am + 1的单个边缘时(从Am中的节点到Am + 1中的节点),才能找到精确解.

当然,一些节点出现在比其他节点更多的路径中.可以基于包含该节点的路径的数量直接推导出每个节点的概率.

通过为每个节点分配权重(等于通向此节点的路径数),不需要保留所有历史记录,而只需保留前一天.

另外,看看非负值线性diphantine方程 - 我刚才问过的一个问题.接受的答案是在每个步骤中对所有组合进行enumarte的好方法.

Answer 2

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

假设你确切地知道物品的比例增加了多少,而不仅仅是最大比例是多少.

一个用户有N个水果,你有D天的猜测.

在每一天你得到N个新变量然后你有总共D*N个变量.

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

所有N> 2的2*D <N*D.

Answer 3

免责声明:我暂时删除了我的答案并仔细阅读了问题,因为我误解了问题的一些关键部分,因此我的答案发生了显着变化.虽然仍然引用类似的主题和算法,但在我尝试用C#自己解决一些问题之后,答案得到了极大的改善.

好莱坞版

• 问题是动态约束满足问题(DCSP),约束满足问题(CSP)的变体.
• 如果值和数量范围不小,请使用蒙特卡罗找到给定日期的潜在解决方案.否则,使用蛮力来寻找所有可能的解决方案.
• 使用约束记录(与DCSP相关),级联应用于前几天以限制潜在的解决方案集.
• 根据概率,交叉你的手指,瞄准和射击(猜猜).
• (可选)布鲁斯威利斯获胜.

原始版本

首先,我想说明我看到的两个主要问题:

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

当以某种方式改变问题的原始表述时,[DCSP]是有用的,通常是因为要考虑的一组约束因环境而发展.DCSP被视为一系列静态CSP,每个CSP都是前一个CSP的变换,其中可以添加(限制)或删除(松弛)变量和约束.

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

• 随着环境中的每次更改(用户输入的D _{i + 1}值),查找有关新约束的信息:add-remove约束的可能"已使用"数量是多少.
• 将限制应用于级联中的每个前一天.波纹效应可能会显着减少可能的解决方案.

为此,您需要每天获得一套新的可能解决方案; 使用蛮力或蒙特卡罗.然后,比较D _i到D _i-1的解决方案,并且只保留能够在不违反约束的情况下成功解决前几天解决方案的解决方案.

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

可以采取许多其他步骤来进一步改进您的解决方案.以下是一些想法:

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

鉴于所有这些,尝试找出基于解决方案和启发式的出现的排名系统来确定候选解决方案.