Bab*_*ger 5 java complexity-theory
这个问题相当长.这可能需要很长时间,所以如果你没有我理解的时间.
首先让我解释一下我想要实现的目标:我和一些朋友玩这个数学游戏,我们从一组可能的数字中得到6个随机数:1到10,25,50,75和100. 6个数字被选中其中不允许重复.然后将在[100,999]的范围内选择目标号码.使用上述6个数字,我们只能使用基本操作(加法,减法,乘法和除法)来达到目标.只允许整数,并且不需要所有6个整数来达到解决方案.
一个例子:我们从数字4,8,6,9,25,100开始,需要找到328.可能的解决方案是:((4 x 100) - (9 x 8))= 400 - 72 = 328.这个,我只使用了6个初始数字中的4个而没有使用过两次.这是一个有效的解决方案.
我们并不总能找到自己的解决方案,这就是为什么我认为一个程序会很有用.我编写了一个程序(用Java编写),它已经过几次测试,并且已经有效了.它并不总是提供所有可能的解决方案,但它在自己的限制范围内工作.现在我已经尝试扩展它,所以所有的解决方案都会显示出来.
关于主要问题:我尝试执行的程序运行时间非常长.就像在,我会让它运行15分钟,它看起来不像是在任何接近完成.所以我想到了它,选项确实是无穷无尽的.我从6个数字开始,我将第一个与其他5个进行比较,然后将第二个与其他5个进行比较,依此类推,直到我完成了6次(每次比较我与每个运算符进行比较,再次进行4次).在最初的6个数字的单个状态中,我现在有5次6次4 = 120个状态(每个5个数字).所有这些都必须经历相同的仪式,所以难怪它花了这么长时间.
该程序实际上太大了,无法在此列出,因此我会将其上传给感兴趣的人:http: //www.speedyshare.com/ksT43/MathGame3.jar (点击下载旁边的MathGame3.jar标题)
以下是发生的事情的一般概述:
-6 integers + goal number are initialized
-I use the class StateNumbers that are acting as game states
-> in this class the remaining numbers (initially the 6 starting numbers)
are kept as well as the evaluated expressions, for printing purposes
此方法是主要操作发生的位置:
StateNumbers stateInProcess = getStates().remove(0);
ArrayList<Integer> remainingNumbers = stateInProcess.getRemainingNumbers();
for(int j = 0; j < remainingNumbers.size(); j++){
for(int i = 0; i < remainingNumbers.size(); i++){
for(Operator op : Operator.values()){ // Looping over different operators
if(i == j) continue;
...
}
}
}
我评估了第一个元素所有可能的操作以及该状态的所有剩余数字.然后我用自己写的等于检查它是否已经在状态的arraylist中(它充当队列,但顺序并不重要).如果它不在那里,那么状态将被添加到列表中,然后我对其他元素也这样做.在那之后,我放弃了这个州,并从不断增长的名单中挑选另一个.
该列表在10分钟内增加到8万个状态,并且变得越来越慢.那是因为当我想要添加新状态时,要比较的状态数量越来越多.这让我想知道是否与其他州进行比较以防止重复是一个好主意.
该计划的完成并不是那么重要,但我希望将其视为一种学习体验.我不是要求任何人为我编写代码,但是对我能够处理得更好的友好建议将非常感激.这意味着如果您想要提及有关该计划另一方面的内容,请执行此操作.由于大多数主题处理程序的特定部分,我不确定这个论坛上是否要求太多.虽然我的问题也是具体的,但原因可能很多.
编辑:我不是要找到最快的单一解决方案,而是每个解决方案.因此,如果我找到解决方案,我的程序将不会停止.然而,它会尝试忽略双精度,如:((4 + 5)7)和(7(5 + 4)).只接受两个中的一个,因为加法和乘法的equals方法不关心操作数的定位.
使用递归（即深度优先搜索）来编写它可能会更容易，因为这会简化中间状态的簿记。
如果您想保持呼吸优先的方法，请确保状态列表支持有效删除第一个元素，即使用java.util.Queue诸如java.util.ArrayDeque. 我提到这一点是因为最常用的List实现（即java.util.ArrayList）需要复制其整个内容以删除第一个元素，这使得如果列表很大，则删除第一个元素的成本非常昂贵。
120 个州（每个州 5 个数字）。所有这些都必须经历相同的仪式，所以难怪要花这么长时间。
事实上，这确实令人惊讶。毕竟，2GHz CPU 每秒执行 20 亿个时钟周期。即使检查一个状态需要多达 100 个时钟周期，这仍然意味着每秒 2000 万个状态！
另一方面，如果我正确理解游戏规则，则候选解决方案集由 6 个数字（其中有 6！= 720）的所有排序给出，其中 5 个空格中有 4 个运算符之一之间，以及定义的运算符求值顺序。也就是说，我们一共有6个！* 4^5 * 5！= 88 473 600 个候选解决方案，因此处理应在几秒钟内完成。
PS：完整的解决方案编写起来可能不会很耗时，所以如果您愿意，我也可以发布代码 - 我只是不想破坏您的学习体验。
更新：我已经写了代码。这比我想象的要难，因为找到所有解决方案的要求意味着我们需要在不展开堆栈的情况下打印解决方案。因此，我将每个状态的历史记录保存在堆上。经过测试，我对性能不太满意（大约10秒），所以我添加了memoization，即每组数字只处理一次。这样，运行时间就下降到了 3 秒左右。
由于 Stackoverflow 没有剧透标签，我增加了缩进，所以你必须向右滚动才能看到任何内容:-)
package katas.countdown;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
enum Operator {
plus("+", true),
minus("-", false),
multiply("*", true),
divide("/", false);
final String sign;
final boolean commutes;
Operator(String sign, boolean commutes) {
this.sign = sign;
this.commutes = commutes;
}
int apply(int left, int right) {
switch (this) {
case plus:
return left + right;
case minus:
return left - right;
case multiply:
return left * right;
case divide:
int mod = left % right;
if (mod == 0) {
return left / right;
} else {
throw new ArithmeticException();
}
}
throw new AssertionError(this);
}
@Override
public String toString() {
return sign;
}
}
class Expression implements Comparable<Expression> {
final int value;
Expression(int value) {
this.value = value;
}
@Override
public int compareTo(Expression o) {
return value - o.value;
}
@Override
public int hashCode() {
return value;
}
@Override
public boolean equals(Object obj) {
return value == ((Expression) obj).value;
}
@Override
public String toString() {
return Integer.toString(value);
}
}
class OperationExpression extends Expression {
final Expression left;
final Operator operator;
final Expression right;
OperationExpression(Expression left, Operator operator, Expression right) {
super(operator.apply(left.value, right.value));
this.left = left;
this.operator = operator;
this.right = right;
}
@Override
public String toString() {
return "(" + left + " " + operator + " " + right + ")";
}
}
class State {
final Expression[] expressions;
State(int... numbers) {
expressions = new Expression[numbers.length];
for (int i = 0; i < numbers.length; i++) {
expressions[i] = new Expression(numbers[i]);
}
}
private State(Expression[] expressions) {
this.expressions = expressions;
}
/**
* @return a new state constructed by removing indices i and j, and adding expr instead
*/
State replace(int i, int j, Expression expr) {
Expression[] exprs = Arrays.copyOf(expressions, expressions.length - 1);
if (i < exprs.length) {
exprs[i] = expr;
if (j < exprs.length) {
exprs[j] = expressions[exprs.length];
}
} else {
exprs[j] = expr;
}
Arrays.sort(exprs);
return new State(exprs);
}
@Override
public boolean equals(Object obj) {
return Arrays.equals(expressions, ((State) obj).expressions);
}
public int hashCode() {
return Arrays.hashCode(expressions);
}
}
public class Solver {
final int goal;
Set<State> visited = new HashSet<>();
public Solver(int goal) {
this.goal = goal;
}
public void solve(State s) {
if (s.expressions.length > 1 && !visited.contains(s)) {
visited.add(s);
for (int i = 0; i < s.expressions.length; i++) {