此代码在我的Minesweeper Flags在线游戏中由AI
AI_Hard，AI_Extreme3和AI_Nightmare使用。我目前正在为此使用Java 6，但我可能会制作Java 8版本稍后的。它与其他库没有任何依赖关系。
它如何工作？
假设该板有6个地雷。一种简单的方法是递归放置所有6个地雷，并计算每个字段都有一个地雷的组合数量。尽管这对于像这样的小板来说是可行的，但对于具有相同图案和51个地雷的较大板来说，这并不是最佳选择。
所以，如果仅将地雷放在1号和3号周围怎么办并在我们没有任何线索的情况下，将组合法用于董事会的其余部分？这将有助于使用相同模式的更大的电路板，但是如果您在电路板上像这样分布了很多线索，那对于大多数算法来说，事情就会变得太复杂和太慢。
我的方法
我将通过指导您手动计算上面的4x4示例板来说明我的方法。
板表示。该委员会可以表示为：
abcd
e13f
ghij
klmn
规则。因此，我们有一个
1和一个3，我们知道板上总共有6个地雷。可以表示为：a+b+c+e+g+h+i = 1
b+c+h+i+d+f+j = 3
a+b+c+d+e+f+g+h+i+j+k+l+m+n = 6
这就是我所说的规则（代码中的
FieldRule类）字段组。通过将规则所在的字段分组，可以将其重构为：
(a+e+g) + (b+c+h+i) = 1
(b+c+h+i) + (d+f+j) = 3
(b+c+h+i) + (d+f+j) + (k+l+m+n) = 6
这些组称为字段组（代码中的
FieldGroup类）RootAnalyzeImpl类存储规则的集合，在解决规则时，它首先将字段分成几组，然后创建一个GameAnalyze对象来完成其余工作。GameAnalyze。它首先尝试简化事情（稍后再介绍），但如果再也做不到，它将选择一个组并为其分配值。在这里，我选择
(a+e+g)组。我发现最好是从一个小组开始。选择了
(a+e+g) = 0并创建了GameAnalyze的新实例，这将(a+e+g) = 0添加到其knownValues中。简化（
FieldRule.simplify方法）。现在，我们删除具有已知值的组，并尝试推导组的新已知值。(a+e+g) + (b+c+h+i) = 1
(a+e+g)是已知的，因此(b+c+h+i) = 1仍然存在，这使规则得以解决。将(b+c+h+i) = 1添加到knownValues中。下一条规则：(b+c+h+i) + (d+f+j) = 3
(b+c+h+i) = 1是已知的，因此我们遗忘了(d+f+j) = 2，这条规则也已解决，另一个FieldGroup也已知道。最后一条规则：(b+c+h+i) + (d+f+j) + (k+l+m+n) = 6
这里唯一未知的是
(k+l+m+n)，删除其他组后，其值必须为3，因为(b+c+h+i) + (d+f+j) = 1 +2。解决方案所以我们知道的是：
(a+e+g) = 0
(b+c+h+i) = 1
(d+f+j) = 2
(k+l+m+n) = 3
由于所有规则都已求解且所有组都具有值，因此称为一个解决方案（
Solution类）。在简化为另一种解决方案后，对(a+e+g) = 1引线进行相同的操作：(a+e+g) = 1
(b+c+h+i) = 0
(d+f+j) = 3
(k+l+m+n) = 6 - 3 - 1 = 2
解决方案组合。现在我们有两个解决方案，所有组都具有值。创建解决方案后，它将计算该规则可能的组合。这是通过使用
nCr（二项式系数）完成的。对于第一个解决方案，我们有：(a+e+g) = 0 --> 3 nCr 0 = 1 combination
(b+c+h+i) = 1 --> 4 nCr 1 = 4 combinations
(d+f+j) = 2 --> 3 nCr 2 = 3 combinations
(k+l+m+n) = 3 --> 4 nCr 3 = 4 combinations
将这些组合相乘得到1 *此解决方案的4 * 3 * 4 = 48个组合。
和其他解决方案一样：
(a+e+g) = 1 --> 3 nCr 1 = 3
(b+c+h+i) = 0 --> 4 nCr 0 = 1
(d+f+j) = 3 --> 3 nCr 3 = 1
(k+l+m+n) = 2 --> 4 nCr 2 = 6
3 * 1 * 1 * 6 = 18种组合。
因此，总共有48 + 18 = 66个组合。
概率
(k+l+m+n)组中的一个字段属于我的情况的总组合为：在第一个解决方案中：3个地雷，4个场，48个组合。
在第二个解决方案中：2个地雷，4个场，18个组合中的解决方案。
\ $ 3/4 * 48 + 2/4 * 18 = 45 \ $
要计算概率，请将该值除以整个面板的总组合，得出：\ $ 45/66 = 0.681818181818 \ $
其他算法中的常见问题：
他们以特殊的方式对待“全局规则”，而不是像对待另一条规则一样对待
他们对字段进行单独处理而不是聚类将它们合并到
FieldGroup s ，这导致大多数算法无法在合理的时间内解决超级死亡委员会。我的方法？大约四秒钟。 （我不是在开玩笑！）
类摘要
此处未包括，其中一些将单独发布以供审核
Combinatorics.java：包含用于组合器的方法。
FieldGroupSplit.java：静态方法和用于存储用于分隔字段组的结果的类。
RuntimeTimeoutException.java：扩展
RuntimeException的异常RootAnalyze.java：只是
RootAnalyzeImpl所实现的接口。SimplifyResult.java：
FieldRule.simplify的结果枚举SolvedCallback.java：用于让
GameAnalyze发现任何信息时进行通知的接口解决方案包含在下面
FieldGroup.java：字段的集合。由于字段是通用类型，因此它可以是
MinesweeperField，String或其他任何类型。FieldRule.java：规则，由多个等于数字的FieldGroup组成。
GroupValues.java：用于将值分配给
FieldGroup s。 Map<FieldGroup, Integer> RootAnalyzeImpl.java：一切从哪里开始。包含一组应解决的规则。当求解完成时，也用于访问结果。
GameAnalyze.java：用于分支，递归求解和尝试将值分配给组。
Solution.java：存储分配所有组的方法。
所有代码都可以在http：//找到。 /github.com/Zomis/Minesweeper-Analyze
代码
FieldGroup.java：（51行，1158字节）
/**
* A group of fields that have common rules
*
* @author Simon Forsberg
* @param <T> The field type
*/
public class FieldGroup<T> extends ArrayList<T> {
private static final long serialVersionUID = 4172065050118874050L;
private double probability = 0;
private int solutionsKnown = 0;
public FieldGroup(Collection<T> fields) {
super(fields);
}
public double getProbability() {
return this.probability;
}
public int getSolutionsKnown() {
return this.solutionsKnown;
}
void informAboutSolution(int rValue, Solution<T> solution, double total) {
if (rValue == 0)
return;
this.probability = this.probability + solution.nCr() / total * rValue / this.size();
this.solutionsKnown++;
}
public String toString() {
if (this.size() > 8) {
return "(" + this.size() + " FIELDS)";
}
StringBuilder str = new StringBuilder();
for (T field : this) {
if (str.length() > 0)
str.append(" + ");
str.append(field);
}
return "(" + str.toString() + ")";
}
}
FieldRule.java：（201行，5326字节）
/**
* A constraint of a number of fields or {@link FieldGroup}s that should have a specific sum
*
* @author Simon Forsberg
* @param <T> Field type
*/
public class FieldRule<T> {
private final T cause;
private final List<FieldGroup<T>> fields;
private int result = 0;
/**
* Create a copy of an existing rule.
*
* @param copyFrom Rule to copy
*/
public FieldRule(FieldRule<T> copyFrom) {
this.fields = new ArrayList<FieldGroup<T>>(copyFrom.fields); // Deep copy? Probably not. FieldGroup don't change much.
this.result = copyFrom.result;
this.cause = copyFrom.cause;
}
/**
* Create a rule from a list of fields and a result (create a new FieldGroup for it)
*
* @param cause The reason for why this rule is added (optional, may be null)
* @param rule Fields that this rule applies to
* @param result The value that should be forced for the fields
*/
public FieldRule(T cause, Collection<T> rule, int result) {
this.fields = new ArrayList<FieldGroup<T>>();
this.fields.add(new FieldGroup<T>(rule));
this.result = result;
this.cause = cause;
}
FieldRule(T cause, FieldGroup<T> group, int result) {
this.cause = cause;
this.fields = new ArrayList<FieldGroup<T>>();
this.fields.add(group);
this.result = result;
}
boolean checkIntersection(FieldRule<T> rule) {
if (rule == this)
return false;
List<FieldGroup<T>> fieldsCopy = new ArrayList<FieldGroup<T>>(fields);
List<FieldGroup<T>> ruleFieldsCopy = new ArrayList<FieldGroup<T>>(rule.fields);
for (FieldGroup<T> groupA : fieldsCopy) {
for (FieldGroup<T> groupB : ruleFieldsCopy) {
if (groupA == groupB)
continue;
FieldGroupSplit<T> splitResult = FieldGroupSplit.split(groupA, groupB);
if (splitResult == null)
continue; // nothing to split
FieldGroup<T> both = splitResult.getBoth();
FieldGroup<T> onlyA = splitResult.getOnlyA();
FieldGroup<T> onlyB = splitResult.getOnlyB();
this.fields.remove(groupA);
this.fields.add(both);
if (!onlyA.isEmpty()) {
this.fields.add(onlyA);
}
rule.fields.remove(groupB);
rule.fields.add(both);
if (!onlyB.isEmpty()) {
rule.fields.add(onlyB);
}
return true;
}
}
return false;
}
public T getCause() {
return this.cause;
}
public Collection<FieldGroup<T>> getFieldGroups() {
return new ArrayList<FieldGroup<T>>(this.fields);
}
public int getFieldsCountInGroups() {
int fieldsCounter = 0;
for (FieldGroup<T> group : fields) {
fieldsCounter += group.size();
}
return fieldsCounter;
}
public int getResult() {
return this.result;
}
public FieldGroup<T> getSmallestFieldGroup() {
if (this.fields.isEmpty())
return null;
FieldGroup<T> result = this.fields.get(0);
for (FieldGroup<T> group : this.fields) {
if (group.size() < result.size()) {
result = group;
}
}
return result;
}
public boolean isEmpty () {
return fields.isEmpty() && result == 0;
}
public double nCr() {
if (this.fields.size() != 1)
throw new IllegalStateException("Rule has more than one group.");
return Combinatorics.nCr(this.getFieldsCountInGroups(), this.result);
}
public SimplifyResult simplify(Map<FieldGroup<T>, Integer> knownValues) {
if (this.isEmpty()) {
return SimplifyResult.NO_EFFECT;
}
Iterator<FieldGroup<T>> it = fields.iterator();
int totalCount = 0;
while (it.hasNext()) {
FieldGroup<T> group = it.next();
Integer known = knownValues.get(group);
if (known != null) {
it.remove();
result -= known;
}
else totalCount += group.size();
}
// a + b + c = -2 is not a valid rule.
if (result < 0) {
return SimplifyResult.FAILED_NEGATIVE_RESULT;
}
// a + b = 42 is not a valid rule
if (result > totalCount) {
return SimplifyResult.FAILED_TOO_BIG_RESULT;
}
// (a + b) = 1 or (a + b) = 0 would give a value to the (a + b) group and simplify things.
if (fields.size() == 1) {
knownValues.put(fields.get(0), result);
fields.clear();
result = 0;
return SimplifyResult.SIMPLIFIED;
}
// (a + b) + (c + d) = 0 would give the value 0 to all field groups and simplify things
if (result == 0) {
for (FieldGroup<T> field : fields) {
knownValues.put(field, 0);
}
fields.clear();
result = 0;
return SimplifyResult.SIMPLIFIED;
}
// (a + b) + (c + d) = 4 would give the value {Group.SIZE} to all Groups.
if (totalCount == result) {
for (FieldGroup<T> field : fields) {
knownValues.put(field, result * field.size() / totalCount);
}
return SimplifyResult.SIMPLIFIED;
}
return SimplifyResult.NO_EFFECT;
}
@Override
public String toString() {
StringBuilder rule = new StringBuilder();
for (FieldGroup<T> field : this.fields) {
if (rule.length() > 0) {
rule.append(" + ");
}
rule.append(field.toString());
}
rule.append(" = ");
rule.append(result);
return rule.toString();
}
}
GameAnalyze.java：（85行，2276字节）
public class GameAnalyze<T> {
private final SolvedCallback<T> callback;
private final GroupValues<T> knownValues;
private final List<FieldRule<T>> rules;
GameAnalyze(GroupValues<T> knownValues, List<FieldRule<T>> unsolvedRules, SolvedCallback<T> callback) {
this.knownValues = knownValues == null ? new GroupValues<T>() : new GroupValues<T>(knownValues);
this.rules = unsolvedRules;
this.callback = callback;
}
private void removeEmptyRules() {
Iterator<FieldRule<T>> it = rules.iterator();
while (it.hasNext()) {
if (it.next().isEmpty())
it.remove();
}
}
private boolean simplifyRules() {
boolean simplifyPerformed = true;
while (simplifyPerformed) {
simplifyPerformed = false;
for (FieldRule<T> ruleSimplify : rules) {
SimplifyResult simplifyResult = ruleSimplify.simplify(knownValues);
if (simplifyResult == SimplifyResult.SIMPLIFIED) {
simplifyPerformed = true;
}
else if (simplifyResult.isFailure()) {
return false;
}
}
}
return true;
}
void solve() {
if (Thread.interrupted())
throw new RuntimeTimeoutException();
if (!this.simplifyRules()) {
return;
}
this.removeEmptyRules();
this.solveRules();
if (this.rules.isEmpty()) {
callback.solved(Solution.createSolution(this.knownValues));
}
}
private void solveRules() {
if (this.rules.isEmpty())
return;
FieldGroup<T> chosenGroup = this.rules.get(0).getSmallestFieldGroup();
if (chosenGroup == null) {
throw new IllegalStateException("Chosen group is null.");
}
if (chosenGroup.size() == 0) {
throw new IllegalStateException("Chosen group is empty. " + chosenGroup);
}
for (int i = 0; i <= chosenGroup.size(); i++) {
GroupValues<T> mapCopy = new GroupValues<T>(this.knownValues);
mapCopy.put(chosenGroup, i);
List<FieldRule<T>> rulesCopy = new ArrayList<FieldRule<T>>(); // deep copy!
for (FieldRule<T> rule : this.rules) {
rulesCopy.add(new FieldRule<T>(rule));
}
new GameAnalyze<T>(mapCopy, rulesCopy, this.callback).solve();
}
}
}
GroupValues.java：（32行，687字节）
public class GroupValues<T> extends HashMap<FieldGroup<T>, Integer> {
private static final long serialVersionUID = -107328884258597555L;
private int bufferedHash = 0;
public GroupValues(GroupValues<T> values) {
super(values);
}
public GroupValues() {
super();
}
}
RootAnalyzeImpl.java：（267行，7690字节）
public class RootAnalyzeImpl<T> implements SolvedCallback<T>, RootAnalyze<T> {
private final List<FieldGroup<T>> groups = new ArrayList<FieldGroup<T>>();
private final List<FieldRule<T>> originalRules = new ArrayList<FieldRule<T>>();
private final List<FieldRule<T>> rules = new ArrayList<FieldRule<T>>();
private final List<Solution<T>> solutions = new ArrayList<Solution<T>>();
private double total;
private boolean solved = false;
@Override
public double getTotal() {
return this.total;
}
private RootAnalyzeImpl(Solution<T> known) {
for (Entry<FieldGroup<T>, Integer> sol : known.getSetGroupValues().entrySet()) {
this.rules.add(new FieldRule<T>(null, sol.getKey(), sol.getValue()));
}
}
public RootAnalyzeImpl() {}
public void addRule(FieldRule<T> rule) {
this.rules.add(rule);
}
/**
* Get the list of simplified rules used to perform the analyze
*
* @return List of simplified rules
*/
@Override
public List<FieldRule<T>> getRules() {
return new ArrayList<FieldRule<T>>(this.rules);
}
@Override
public FieldGroup<T> getGroupFor(T field) {
for (FieldGroup<T> group : this.groups) {
if (group.contains(field)) {
return group;
}
}
return null;
}
/**
* Return a random solution that satisfies all the rules
*
* @param random Random object to perform the randomization
* @return A list of fields randomly selected that is guaranteed to be a solution to the constraints
*
*/
@Override
public List<T> randomSolution(Random random) {
if (random == null) {
throw new IllegalArgumentException("Random object cannot be null");
}
List<Solution<T>> solutions = new LinkedList<Solution<T>>(this.solutions);
if (this.getTotal() == 0) {
throw new IllegalStateException("Analyze has 0 combinations: " + this);
}
double rand = random.nextDouble() * this.getTotal();
Solution<T> theSolution = null;
while (rand > 0) {
if (solutions.isEmpty()) {
throw new IllegalStateException("Solutions is suddenly empty. (This should not happen)");
}
theSolution = solutions.get(0);
rand -= theSolution.nCr();
solutions.remove(0);
}
return theSolution.getRandomSolution(random);
}
private RootAnalyzeImpl<T> solutionToNewAnalyze(Solution<T> solution, List<FieldRule<T>> extraRules) {
Collection<FieldRule<T>> newRules = new ArrayList<FieldRule<T>>();
for (FieldRule<T> rule : extraRules) {
// Create new rules, because the older ones may have been simplified already.
newRules.add(new FieldRule<T>(rule));
}
RootAnalyzeImpl<T> newRoot = new RootAnalyzeImpl<T>(solution);
newRoot.rules.addAll(newRules);
return newRoot;
}
@Override
public RootAnalyze<T> cloneAddSolve(List<FieldRule<T>> extraRules) {
List<FieldRule<T>> newRules = this.getOriginalRules();
newRules.addAll(extraRules);
RootAnalyzeImpl<T> copy = new RootAnalyzeImpl<T>();
for (FieldRule<T> rule : newRules) {
copy.addRule(new FieldRule<T>(rule));
}
copy.solve();
return copy;
}
/**
* Get the list of the original, non-simplified, rules
*
* @return The original rule list
*/
@Override
public List<FieldRule<T>> getOriginalRules() {
return this.originalRules.isEmpty() ? this.getRules() : new ArrayList<FieldRule<T>>(this.originalRules);
}
private double getTotalWith(List<FieldRule<T>> extraRules) {
if (!this.solved)
throw new IllegalStateException("Analyze is not solved");
double total = 0;
for (Solution<T> solution : this.getSolutions()) {
RootAnalyzeImpl<T> root = this.solutionToNewAnalyze(solution, extraRules);
root.solve();
total += root.getTotal();
}
return total;
}
@Override
public double getProbabilityOf(List<FieldRule<T>> extraRules) {
if (!this.solved)
throw new IllegalStateException("Analyze is not solved");
return this.getTotalWith(extraRules) / this.getTotal();
}
@Override
public List<Solution<T>> getSolutions() {
if (!this.solved)
throw new IllegalStateException("Analyze is not solved");
return new ArrayList<Solution<T>>(this.solutions);
}
/**
* Separate fields into field groups. Example <code>a + b + c = 2</code> and <code>b + c + d = 1</code> becomes <code>(a) + (b + c) = 2</code> and <code>(b + c) + (d) = 1</code>. This method is called automatically when calling {@link #solve()}
*/
public void splitFieldRules() {
if (rules.size() <= 1)
return;
boolean splitPerformed = true;
while (splitPerformed) {
splitPerformed = false;
for (FieldRule<T> a : rules) {
for (FieldRule<T> b : rules) {
boolean result = a.checkIntersection(b);
if (result) {
splitPerformed = true;
}
}
}
}
}
public void solve() {
if (this.solved) {
throw new IllegalStateException("Analyze has already been solved");
}
List<FieldRule<T>> original = new ArrayList<FieldRule<T>>(this.rules.size());
for (FieldRule<T> rule : this.rules) {
original.add(new FieldRule<T>(rule));
}
this.originalRules.addAll(original);
this.splitFieldRules();
this.total = 0;
new GameAnalyze<T>(null, rules, this).solve();
for (Solution<T> solution : this.solutions) {
solution.setTotal(total);
}
if (!this.solutions.isEmpty()) {
for (FieldGroup<T> group : this.solutions.get(0).getSetGroupValues().keySet()) {
// All solutions should contain the same fieldgroups.
groups.add(group);
}
}
this.solved = true;
}
@Override
public List<FieldGroup<T>> getGroups() {
if (!this.solved) {
Set<FieldGroup<T>> agroups = new HashSet<FieldGroup<T>>();
for (FieldRule<T> rule : this.getRules()) {
agroups.addAll(rule.getFieldGroups());
}
return new ArrayList<FieldGroup<T>>(agroups);
}
List<FieldGroup<T>> grps = new ArrayList<FieldGroup<T>>(this.groups);
Iterator<FieldGroup<T>> it = grps.iterator();
while (it.hasNext()) {
// remove empty fieldgroups
if (it.next().isEmpty()) {
it.remove();
}
}
return grps;
}
@Override
public List<T> getFields() {
if (!this.solved) {
throw new IllegalStateException("Analyze is not solved");
}
List<T> allFields = new ArrayList<T>();
for (FieldGroup<T> group : this.getGroups()) {
allFields.addAll(group);
}
return allFields;
}
@Override
public void solved(Solution<T> solved) {
this.solutions.add(solved);
this.total += solved.nCr();
}
@Override
public List<T> getSolution(double solution) {
if (Math.rint(solution) != solution || solution < 0 || solution >= this.getTotal()) {
throw new IllegalArgumentException("solution must be an integer between 0 and total (" + this.getTotal() + ")");
}
if (solutions.isEmpty()) {
throw new IllegalStateException("There are no solutions.");
}
List<Solution<T>> solutions = new ArrayList<Solution<T>>(this.solutions);
Solution<T> theSolution = solutions.get(0);
while (solution > theSolution.nCr()) {
solution -= theSolution.nCr();
solutions.remove(0);
theSolution = solutions.get(0);
}
return theSolution.getCombination(solution);
}
@Override
public Iterable<Solution<T>> getSolutionIteration() {
return this.solutions;
}
}
Solution.java：（135行，3778字节）
/**
* Represents a solution for a Minesweeper analyze.
*
* @author Simon Forsberg
* @param <T>
*/
public class Solution<T> {
public static <T> Solution<T> createSolution(GroupValues<T> values) {
return new Solution<T>(values).nCrPerform();
}
private static <T> double nCr(Entry<FieldGroup<T>, Integer> rule) {
return Combinatorics.nCr(rule.getKey().size(), rule.getValue());
}
private double mapTotal;
private double nCrValue;
private final GroupValues<T> setGroupValues;
private Solution(GroupValues<T> values) {
this.setGroupValues = values;
}
private List<T> combination(List<Entry<FieldGroup<T>, Integer>> grpValues, double combination) {
if (grpValues.isEmpty()) {
return new LinkedList<T>();
}
grpValues = new LinkedList<Entry<FieldGroup<T>, Integer>>(grpValues);
Entry<FieldGroup<T>, Integer> first = grpValues.remove(0);
double remaining = 1;
for (Entry<FieldGroup<T>, Integer> fr : grpValues) {
remaining = remaining * nCr(fr);
}
double fncr = nCr(first);
if (combination >= remaining * fncr) {
throw new IllegalArgumentException("Not enough combinations. " + combination + " max is " + (remaining * fncr));
}
double combo = combination % fncr;
List<T> list = Combinatorics.listCombination(combo, first.getValue(), first.getKey());
if (!grpValues.isEmpty()) {
List<T> recursive = combination(grpValues, Math.floor(combination / fncr));
if (recursive == null) {
return null;
}
list.addAll(recursive);
}
return list;
}
public Solution<T> copyWithoutNCRData() {
return new Solution<T>(this.setGroupValues);
}
public List<T> getCombination(double combinationIndex) {
return combination(new LinkedList<Map.Entry<FieldGroup<T>,Integer>>(this.setGroupValues.entrySet()), combinationIndex);
}
public double getCombinations() {
return this.nCrValue;
}
public double getProbability() {
if (this.mapTotal == 0)
throw new IllegalStateException("The total number of solutions on map is unknown");
return this.nCrValue / this.mapTotal;
}
public List<T> getRandomSolution(Random random) {
List<T> result = new ArrayList<T>();
for (Entry<FieldGroup<T>, Integer> ee : this.setGroupValues.entrySet()) {
List<T> group = new ArrayList<T>(ee.getKey());
Collections.shuffle(group, random);
for (int i = 0; i < ee.getValue(); i++) {
result.add(group.remove(0));
}
}
return result;
}
public GroupValues<T> getSetGroupValues() {
return new GroupValues<T>(setGroupValues);
}
public double nCr() {
return this.nCrValue;
}
private Solution<T> nCrPerform() {
double result = 1;
for (Entry<FieldGroup<T>, Integer> ee : this.setGroupValues.entrySet()) {
result = result * Combinatorics.nCr(ee.getKey().size(), ee.getValue());
}
this.nCrValue = result;
return this;
}
void setTotal(double total) {
this.mapTotal = total;
for (Entry<FieldGroup<T>, Integer> ee : this.setGroupValues.entrySet()) {
ee.getKey().informAboutSolution(ee.getValue(), this, total);
}
}
@Override
public String toString() {
StringBuilder str = new StringBuilder();
for (Entry<FieldGroup<T>, Integer> ee : this.setGroupValues.entrySet()) {
str.append(ee.getKey() + " = " + ee.getValue() + ", ");
}
str.append(this.nCrValue + " combinations (" + this.getProbability() + ")");
return str.toString();
}
}
用法/测试
测试和用法可以在GitHub上找到。特别是请参阅
General2DTest。问题
即使此代码已经相当快，但它可以使其变得更快吗？ （多项式时间有人吗？）
是否存在另一种实现方式？可以使用任何库来计算此代码吗？
除此之外，有关此代码和/或这种方法的任何常规注释吗？
#1 楼
GroupValuesGroupValues似乎并没有达到除Map之外的目的；除了未使用的字段外，它不添加任何功能。实际上，我认为它所能实现的一切只是掩盖了实际发生的事情。FieldGroup
您正在扩展
ArrayList而不是与其组合，这是代码的味道。我发现自己正在看informAboutSolution。如果列表为空，这里的计算没有任何意义。此外，由于您是公开名单，因此任何人都可以删除您的所有条目，或插入更多条目，或采取各种愚蠢的做法来搞乱您的计算。我认为您应该梳理这里发生的事情的运行提示方面。至少....
void informAboutSolution(int rValue, Solution<T> solution, double total) {
// codestyle: always use braces
if (rValue == 0) {
return;
}
double probabilityChange = solution.nCr() / total * rValue / fields.size();
this.runningTally.update(probabilityChange);
}
这确实需要更好的变量名-您在这里实际上在做什么？给定一个可以为该组分配一定数量炸弹的解决方案，您正在计算该组中任何单元都有炸弹的可能性。
class RunningTally {
private double probability = 0;
private int solutionsKnown = 0;
public double getProbability() {
return this.probability;
}
public int getSolutionsKnown() {
return this.solutionsKnown;
}
public void update(double change) {
probability += change;
solutionsKnown++;
}
}
void informAboutSolution(int bombsAllocated, Solution<T> solution, double total) {
// codestyle: always use braces
if (bombsAllocated == 0) {
return;
}
int cellsAvailable = fields.size();
double probabilityBombed = bombsAllocated / cellsAvailable;
double solutionPercentage = solution.nCr() / total;
double probabilityChange = solutionPercentage * probabilityBombed;
runningTally.update(probabilityChange);
}
分配对象并进行工作在一起是代码的味道-不一定是错误的，但肯定是可疑的。如果您对字符串连接足够关注以至于认为
StringBuilder是个好主意，则允许多个对象共享同一个StringBuilder可能很有意义。void writeTo(StringBuilder str) {
final String START_OBJECT = "(";
final String END_OBJECT = ")";
final String SEPARATOR = " + ";
str.append(START_OBJECT);
if (fields.size() > 8) {
str.append(fields.size());
str.append(" FIELDS");
} else {
final int cursor = str.length();
for (T field : fields) {
// This is really a two state FSM...
if (str.length() > cursor) {
str.append(SEPARATOR);
}
str.append(field);
}
}
str.append(END_OBJECT);
}
GameAnalyze
不必太在意这个名字-类名通常是名词，所以
GameAnalyzer或GameAnalysis也许是这样。void solve() {
if (Thread.interrupted())
throw new RuntimeTimeoutException();
if (!this.simplifyRules()) {
return;
}
this.removeEmptyRules();
this.solveRules();
if (this.rules.isEmpty()) {
callback.solved(Solution.createSolution(this.knownValues));
}
}
检查的主要道具中断。由于
solve()并不是递归的，因此似乎中断检查在错误的位置。将支票放入solveRules可能更有意义。我不喜欢通过抛出运行时异常来取消求解，也不知道为什么您会选择为此实现唯一的
RuntimeException。如果您觉得无法在此处抛出受检查的异常，则也许应该有一个状态对象，各个位用于确定它们是否应继续处理。我还不清楚
Solution.createSolution在正确的位置- -将已知值传递给知道如何应用解决方案的回调似乎更为灵活。我真的不喜欢递归方法的一个方面是您错过了解决的机会平行位置。至少，我想考虑使用另一个内核来创建
Solutions，而不是分解问题。如果没有概要分析，很难说这是否会有所作为，但是您当前的方法不支持这种重构。例如，考虑一个采用knownValues的侦听器。您可能有一个版本可以在线发布解决方案，而另一个版本可以将knownValues放入队列中，另一个线程将在其中将它们转换为它们。解决方案
Solution试图同时成为两种不同的事物-它是计算器，也是解决方案。应该将这两部分分开，这样可以使其中发生的一切更加清晰。在
Random中使用Solution看起来确实很奇怪；您可能希望使用压缩编码，这实际上可以为您提供可能的“随机”解决方案的确定性排序。RootAnalyzeImpl
这里有很多功能正在抛出
IllegalStateExceptions。对我来说，这意味着您在这里拥有一个或多个类，一个构成了已解决状态，而另一个则是未解决状态，它们具有与之相关的不同动词。这很麻烦：
if (Math.rint(solution) != solution || solution < 0 || solution >= this.getTotal()) {
throw new IllegalArgumentException("solution must be an integer between 0 and total (" + this.getTotal() + ")");
}
如果解决方案必须是整数，那么为什么它的类型为double？您似乎正在使用可生成非整数值的组合库。然后让这个决定污染其他所有东西。当然，将您的组合问题视为整数（或长整数），并屏蔽掉所有不同意的库，是否更有意义？
评论
\ $ \ begingroup \ $
我之所以使用double而不是int / long的原因是，当处理这种规模的组合函数时，它变得非常快。唯一的其他选择是BigInteger，它可能会在解决所有问题后用于抓取解决方案，但是在执行实际解决方案时会对性能产生负面影响。
\ $ \ endgroup \ $
–西蒙·福斯伯格
14年6月25日在9:27
\ $ \ begingroup \ $
之所以使用GroupValues
\ $ \ endgroup \ $
–西蒙·福斯伯格
14年6月25日在9:54
#2 楼
我尝试始终遵循的第一个规则是保持一致。您不一定总是在代码中使用相同的模式作为方括号。 if (recursive == null) {
return null;
}
vs
if (groupA == groupB)
continue;
>对于那些没有先阅读您的解释并看到这个小家伙的人，一开始真的不清楚是什么意思。我不建议正常注释，但是在这种情况下，使用javadoc作为方法或注释会很好。
这确实很小，但是我必须指出。
我会挑战您对此类的选择：
public double nCr() {。真的需要扩展public class FieldGroup<T> extends ArrayList<T>吗？您的ArrayList与FieldGroup直接相关吗？它可以与ArrayList一起使用吗？ 在评论中，我总是建议使用接口而不是实现。对于您而言，我不能，因为您需要添加的那些新方法。我真的发现拥有一个不能在不丢失创建类的东西的情况下不能使用的
LinkedList很奇怪。我真的不知道最佳解决方案是什么。我可能只是有一个collection的实例，并向其中添加相关的方法。您还可以直接实现List，添加
List的实例，并通过重定向到ArrayList来实现方法。#3 楼
您有很多对象实例化似乎是多余的，可以删除。考虑将resolveRules重写为类似于以下内容的方法：每个private void solveRules() {
if (this.rules.isEmpty())
return;
FieldGroup<T> chosenGroup = this.rules.get(0).getSmallestFieldGroup();
if (chosenGroup == null) {
throw new IllegalStateException("Chosen group is null.");
}
int groupSize = chosenGroup.size();
if (groupSize == 0) {
throw new IllegalStateException("Chosen group is empty. " + chosenGroup);
}
GroupValues<T> mapCopy = new GroupValues<T>();
List<FieldRule<T>> rulesCopy = new ArrayList<FieldRule<T>>();
int rulesCount = this.rules.size();
for (FieldRule<T> rule : this.rules) {
rulesCopy.add(new FieldRule<T>(rule));
}
for (int i = 0; i <= groupSize; i++) {
mapCopy.copyFrom(this.knownValues);
mapCopy.put(chosenGroup, i);
for (int j = 0; j<rulesCount;j++) {
rulesCopy.get(j).copyFrom(this.rules.get(j));
}
this.solve(mapCopy, rulesCopy, this.callback);
}
}
由于您的
copyFrom本质上是一个带有咖喱参数的函数，您可以跳过所有分析器的实例化，而是将构造函数参数传递给GameAnalyze并让它们沿调用链滴加。我尚未检查所有建议的更改，它们只是为了给您提供总体思路。评论
\ $ \ begingroup \ $
老实说，我是否会提高性能，我什至不确定这种方法是否会产生正确的结果。
\ $ \ endgroup \ $
–西蒙·福斯伯格
14年6月27日在16:58
\ $ \ begingroup \ $
我100％地确定内存分配和垃圾回收是费时的，不会产生任何价值。因此，如果不需要内存分配，那么删除内存分配将始终提高性能。就像我写的那样，我还没有检查所有建议的更改，它们只是为了给您提供总体思路。所以是的，示例实现可能有缺陷，但是根据想法重写它绝对是可行的
\ $ \ endgroup \ $
–Rune FS
14年6月27日在18:27
\ $ \ begingroup \ $
以我的工作生活为例。我们正在创建要以html呈现的网格。我最初为每一行实例化一个对象。我们有几千行。我们花了1分钟以上的时间进行渲染，这比我们想要的还要多。我更改了实现，以便有一个模板行。我对copyFrom建议的种类。优化的最终结果是瓶颈是ToString（），整个网格的渲染时间不到2s
\ $ \ endgroup \ $
–Rune FS
14年6月27日在18:47
评论
getGroups将调用this.getRules，这将创建一个具有所有List@MarcoAcierno我相信最好的做法是制作“防御性副本”，这样就不可能调用object.getRules（）。remove（xxx）;。然后您突然修改了原始文件。尽管可能有些地方可以简化/不同。
将其包装在Collections.unmodifiableList中怎么办？
我相信扫雷艇是NP硬
@BenAaronson您是正确的，它是NP难的，也是NP完整的，这正是我要求提供与P-vs-NP链接的多项式时间解的原因；）我认为在复杂度方面，这会变得很好。