algorithm - 24游戏/倒计时/数字游戏求解器，但答案中没有括号

Question

我一直在网上浏览一整天的解决方案，从一个数字和运算符列表中为指定的目标号码创建一个等式。
我遇到了很多24个游戏求解器，倒计时求解器和类似的，但它们都是围绕在答案中允许括号的概念而构建的。
例如，对于目标42，使用数字1 2 3 4 5 6，解决方案可以是：

6 * 5 = 30
4 * 3 = 12
30 + 12 = 42

注意算法如何记住子方程的结果，然后重新使用它来形成解（在本例中是30和12），基本上是使用括号来形成解 (6 * 5) + (4 * 3) = 42。
我想要一个不使用括号的解决方案，它是从左到右解决的，例如 6 - 1 + 5 * 4 + 2 = 42，如果我写出来，它将是：

6 - 1 = 5
5 + 5 = 10
10 * 4 = 40
40 + 2 = 42

我有一个大约55个数字（随机数从2到12）、9个运算符（每个基本运算符的2个+1个随机运算符）和一个目标值（0到1000之间的随机数）的列表。我需要一个算法来检查我的目标值是否可解（如果不可解，还可以选择是否可以接近实际值）每个数字和运算符只能使用一次，这意味着最多可以使用10个数字来达到目标值。
我发现了一个蛮力算法，它可以很容易地调整来做我想做的事情（ How to design an algorithm to calculate countdown style maths number puzzle），这是可行的，但是我希望能找到一些更复杂的“解决方案”，比如在这个页面上： http://incoherency.co.uk/countdown/

Answer 1

我写了你在文章结尾提到的解算器，我提前道歉代码可读性不高。
对于任何解决此类问题的人来说，其核心代码只是一个深度优先搜索，这意味着你已经开始工作了。
请注意，如果您使用“不使用括号的解决方案（从左到右求解）”，则有一些输入集是不可解的。例如11,11,11,11,11,11,11，目标是144。解是（（11/11）+11）*（（11/11）+11）我的解算器通过将括号分成不同的行使人们更容易理解这一点，但它仍然有效地使用括号，而不是从左到右求值。
“使用圆括号”的方法是对输入应用操作并将结果放回输入包，而不是对其中一个输入和一个累加器应用操作。例如，如果您的输入包是1,2,3,4,5,6，并且您决定乘以3和4，则该包将变成1,2,12,5,6这样，当您递归时，该步骤可以使用上一步的结果。为输出做好准备只是存储操作历史和包中每个数字的一个例子。
我想您所说的更“复杂”的解决方案只是在我的javascript求解器中使用的简单启发式解算器的工作方式是对整个搜索空间进行深度优先搜索，然后选择“最佳”的解决方案，而不仅仅是使用最少步骤的解决方案。
如果一个解决方案更接近目标（注意，解算器中的任何状态都是候选解决方案，只是大多数都比上一个最佳候选解决方案离目标更远），或者如果它与目标的距离相等且具有更低的值，则认为该解决方案比上一个解决方案“更好”（即将其替换为“答案”解决方案）启发式得分。
启发式得分是“中间值”（即“=”符号右侧的值）的总和，去掉尾随的0例如，如果中间值为1、4、10、150，则启发式得分为1+4+1+15:10和150只对1和15计数，因为它们以零结尾这样做是因为人类发现处理可被10整除的数字更容易，所以解决方案看起来“更简单”。
另一个可以被认为是“复杂”的部分是一些线连接在一起的方式。这只是将“5+3=8”和“8+2=10”的结果加入到“5+3+2=10”中要做到这一点的代码是绝对可怕的，但如果您感兴趣的话，可以在https://github.com/jes/cntdn/blob/master/js/cntdn.js的javascript中找到解决方案，该解决方案以数组形式存储（包含每个数字是如何生成的信息），然后会进行一系列的后处理。大致如下：
将从DFS生成的“解决方案列表”转换为（基本的、基于嵌套数组的）表达式树-这是为了处理多参数情况（即，“5+3+2”不是2个加法操作，它只是一个有3个参数的加法操作）
将表达式树转换为一个步骤数组，包括对参数进行排序，使它们的显示更加一致
将步骤数组转换为字符串表示形式以供用户显示，包括解释结果与目标数字的距离（如果不相等）
很抱歉这么长时间。希望其中一些有用。
詹姆斯
编辑：如果你对倒计时解算器感兴趣，你可能想看看我的字母解算器，因为它远比数字1优雅这是https://github.com/jes/cntdn/blob/master/js/cntdn.js中的前两个函数-对字符串使用call solve_letters（）和对每个匹配单词调用函数这个解算器通过遍历表示字典的trie（由https://github.com/jes/cntdn/blob/master/js/mk-js-dict生成）并在每个结束节点调用回调来工作。