0

我整天都在浏览互联网，寻找现有的解决方案，从指定目标数字的数字和运算符列表中创建方程。

我遇到了很多 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 个数字来达到目标​​值。

我找到了一个蛮力算法，可以很容易地调整它来做我想做的事情（如何设计一个算法来计算倒计时风格的数学数字拼图），而且它很有效，但我希望能找到一些能产生更复杂的“解决方案”的东西，喜欢这个页面：http: //incoherency.co.uk/countdown/

4

2 回答 2

4

我写了你在帖子末尾提到的求解器，我提前道歉，代码不是很可读。

从本质上讲，此类问题的任何求解器的代码都只是深度优先搜索，这意味着您已经在工作。

请注意，如果您使用“不使用括号的解决方案，从左到右解决”，则存在无法解决的输入集。例如，目标为 144 的 11,11,11,11,11,11。解为 ((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 个参数的添加）
  • 将表达式树转换为一系列步骤，包括对参数进行排序，以便更一致地呈现它们
  • 将步骤数组转换为字符串表示形式以显示给用户，包括说明结果与目标数字的距离（如果不相等）

道歉的长度。希望其中一些有用。

詹姆士

编辑：如果您一般对倒计时求解器感兴趣，您可能想看看我的字母求解器，因为它比数字一更优雅。这是https://github.com/jes/cntdn/blob/master/js/cntdn.js上的前两个函数- 使用 call solve_letters() 和一串字母和一个函数来调用每个匹配的单词。该求解器通过遍历表示字典的树（由https://github.com/jes/cntdn/blob/master/js/mk-js-dict生成）并在每个端节点调用回调来工作。

于 2013-05-12T23:27:52.817 回答
0

我在java中使用递归来做数组组合。主要思想只是使用DFS来获得数组组合和操作组合。

我使用一个布尔数组来存储访问的位置，这样可以避免再次使用相同的元素。temp StringBuilder 用于存储当前方程，如果对应的结果等于目标，我将把方程放入结果中。选择下一个数组元素时，不要忘记将临时数组和已访问数组返回到原始状态。

该算法会产生一些重复的答案，因此需要稍后进行优化。

public static void main(String[] args) {
    List<StringBuilder> res = new ArrayList<StringBuilder>();
    int[] arr = {1,2,3,4,5,6};
    int target = 42;
    for(int i = 0; i < arr.length; i ++){
        boolean[] visited = new boolean[arr.length];
        visited[i] = true;
        StringBuilder sb = new StringBuilder();
        sb.append(arr[i]);
        findMatch(res, sb, arr, visited, arr[i], "+-*/", target);
    }

    for(StringBuilder sb : res){
        System.out.println(sb.toString());
    }
}

public static void findMatch(List<StringBuilder> res, StringBuilder temp, int[] nums, boolean[] visited, int current, String operations, int target){
    if(current == target){
        res.add(new StringBuilder(temp));
    }

    for(int i = 0; i < nums.length; i ++){
        if(visited[i]) continue;
        for(char c : operations.toCharArray()){
            visited[i] = true;
            temp.append(c).append(nums[i]);
            if(c == '+'){
                findMatch(res, temp, nums, visited, current + nums[i], operations, target);
            }else if(c == '-'){
                findMatch(res, temp, nums, visited, current - nums[i], operations, target);
            }else if(c == '*'){
                findMatch(res, temp, nums, visited, current * nums[i], operations, target);
            }else if(c == '/'){
                findMatch(res, temp, nums, visited, current / nums[i], operations, target);
            }
            temp.delete(temp.length() - 2, temp.length());
            visited[i] = false;
        }
    }
}
于 2017-06-19T18:40:25.650 回答