python教程—如何接近一个数字猜谜游戏(与扭转)算法?-Python实用宝典

python教程—如何接近一个数字猜谜游戏(与扭转)算法?

我正在学习编程(Python和算法),并试图从事一个我觉得有趣的项目。我已经创建了一些基本的Python脚本,但Ia€™m不确定如何处理解决一个游戏我试图建立。

I am learning programming (Python and algorithms) and was trying to work on a project that I find interesting. I have created a few basic Python scripts, but I’m not sure how to approach a solution to a game I am trying to build.

Here’s how the game will work:

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

    Apple = 1 Pears = 2 Oranges = 3

They will then get a chance to choose any combo of them they like (i.e. 100 apples, 20 pears, and one orange). The only output the computer gets is the total value (in this example, it's currently $143). The computer will try to guess what they have. Which obviously it won’t be able to get correctly the first turn.

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

The next turn the user can modify their numbers but no more than 5% of the total quantity (or some other percent we may chose. I’ll use 5% for example.). The prices of fruit can change(at random) so the total value may change based on that also (for simplicity I am not changing fruit prices in this example). Using the above example, on day 2 of the game, the user returns a value of $152 and $164 on day 3. Here's an example:

    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%的精确度内所以用户将永远输入它。

我到目前为止所做的一切

Here’s my solution so far (not much). Basically, I take all the values and figure out all the possible combinations of them (I am done this part). Then I take all the possible combos and put them in a database as a dictionary (so for example for $143, there could be a dictionary entry {apple:143, Pears:0, Oranges :0}..all the way to {apple:0, Pears:1, Oranges :47}. I do this each time I get a new number so I have a list of all possibilities.

Here’s where I’m stuck. In using the rules above, how can I figure out the best possible solution? I think I’ll need a fitness function that automatically compares the two days data and removes any possibilities that have more than 5% variance of the previous days data.

<强>问题:< /强>

我的问题是用户改变了总概率而我有一个所有概率的列表,我该怎么做呢?我需要学习什么?有什么算法或理论我可以使用,是适用的吗?或者,为了帮助我理解我的错误,你能给我一些建议吗?我想多加点水果,告诉他们至少要摘3个,等等)?另外,我对遗传算法只有一个模糊的理解,但我想我可以在这里使用它们,如果有什么我可以使用的?

我非常非常渴望学习,所以任何建议或提示将非常感谢(只是请不要告诉我这个游戏是不可能的)。

更新:获得难以解决的反馈。所以我想我应该在游戏中添加另一个不会干扰玩家行为的条件(游戏对他们来说是一样的),但是每天水果的价值都会随机地改变价格。这会更容易解决吗?因为在5%的移动和某些水果价值的变化,只有少数组合可能是随着时间的推移。

第一天,任何事情都是可能的,获得足够的范围几乎是不可能的,但随着水果价格的变化,用户只能选择5%的变化,那么(随着时间的推移)范围不应该越来越窄。在上面的例子中,如果价格波动足够大,我想我可以强行给出一个可以让我猜测的范围的解决方案,但我试图找出是否有一个更优雅的解决方案或其他解决方案可以随着时间的推移不断缩小这个范围。

UPDATE2:在阅读和询问之后,我认为这是一个隐藏的Markov/Viterbi问题,它跟踪水果价格的变化以及总价格的变化(最后一个数据点的权重最大)。但我不确定如何应用这种关系。我认为情况就是这样,可能是错的,但至少我开始怀疑这是某种类型的机器学习问题。

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

回答

我们将结合图表理论和概率:

第一天,建立一套所有可行的解决方案。设解集为A1={A1 (1), A1(2),…,A1 (n)}。

第二天你又可以建立解集A2。

现在,对于A2中的每个元素,您需要检查是否可以从A1的每个元素(给定x%容限)中找到它。如果是这样-连接A2(n)到A1(m)。如果不能从A1(m)中的任何节点访问它,可以删除这个节点。

我们基本上是在建立一个连通有向无环图。

图中的所有路径都是等可能的。只有当从Am到Am+1只有一条边(从Am中的节点到Am+1中的节点)时,才能找到精确的解。

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

通过为每个节点分配一个权值,它等于指向该节点的路径数,不需要保存所有历史记录,只需要保存前一天的历史。

同样,看看非负值线性diphantine方程 -我刚才问的一个问题。公认的答案是列举每个步骤中的所有组合的好方法。

​Python实用宝典 (pythondict.com)
不只是一个宝典
欢迎关注公众号:Python实用宝典

本文由 Python实用宝典 作者:Python实用宝典 发表,其版权均为 Python实用宝典 所有,文章内容系作者个人观点,不代表 Python实用宝典 对观点赞同或支持。如需转载,请注明文章来源。
1

发表评论