Анализ вероятностей магистралей

Вычисление вероятностей в Minesweeper может показаться легкой задачей, но я видел так много вероятностных калькуляторов, которые либо неправильны, ужасно медленны, либо с уродливым кодом (или все из них), поэтому я должен поделиться своим кодом для этого.

Этот код используется в моей онлайн-игре 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 хранит коллекцию правил , и когда он решается, он начинается с разбиения полей на groups , затем создает a 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: Enum для результата FieldRule.simplify
  • SolvedCallback.java: интерфейс, позволяющий GameAnalyze сообщать, когда он нашел решение

Включено ниже

  • FieldGroup.java: набор полей. Поскольку поля - это общий тип, это может быть MinesweeperField, String или что-то еще.
  • FieldRule.java: правило, состоящее из ряда полевых групп, которое равно числу
  • 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. Даже если этот код будет довольно быстрым, может ли он быть выполнен еще быстрее? ( Полиномиальное время для кого-либо? )
  2. Есть ли другая реализация этого? Можно ли использовать какие-либо библиотеки для расчета этого?
  3. Кроме того, какие-либо общие комментарии к этому коду и /или этот подход?
49 голосов | спросил Simon Forsberg 19 J0000006Europe/Moscow 2014, 20:55:14

3 ответа


29

GroupValues ​​

GroupValues, похоже, не выполняет большую часть цели, кроме того, что вы получаете из 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; вы можете иметь одну версию, которая публикует решения в очереди, и альтернативу, которая ставит известныеValuesв очередь, где другой поток подберет их для их преобразования.

Решение

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() + ")");
}

IF решение должно быть целым числом, почему у него есть тип double? Кажется, вы используете библиотеку combinatorics, которая производит нецелые значения; а затем разрешить это решение заразить все остальное. Разумеется, имеет смысл рассматривать ваши проблемы с комбинаториками как целые (или длинные), так и межсетевые экраны от любых библиотек, которые не согласны?

ответил VoiceOfUnreason 25 J0000006Europe/Moscow 2014, 05:34:16
11

Одно из первых правил, которым я стараюсь всегда следовать, должно быть последовательным. Вы не всегда следуете той же схеме в вашем коде для скобок.

        if (recursive == null) {
            return null;
        }

против

            if (groupA == groupB)
                continue;

Для кого-то, кто первым не прочитал ваше объяснение и не увидел этого маленького парня public double nCr() {, сначала неясно, что это значит. Я не рекомендую нормально комментировать, но в этом случае javadoc для метода или комментария будет хорошим.

Это действительно незначительно, но я должен был указать на это.


Я бы бросил вызов вашему выбору для этого класса: public class FieldGroup<T> extends ArrayList<T>. Действительно ли необходимо расширить ArrayList? Является ли ваш FieldGroup напрямую связан с ArrayList? Будет ли он работать с LinkedList?

В обзорах я всегда предлагаю использовать интерфейс, а не реализацию. В вашем случае я не могу, так как вам нужен новый метод, который вы добавили. Мне действительно странно иметь List, который вы не можете использовать, как один, не теряя того, для чего вы создавали класс.

Я не знаю, какое лучшее решение может быть. Я бы, вероятно, просто имел экземпляр коллекции и добавлял к ней соответствующий метод. Вы также можете реализовать List непосредственно, добавить экземпляр ArrayList и реализовать методы, перенаправляя список list.

ответил Marc-Andre 24 J0000006Europe/Moscow 2014, 17:32:28
6

У вас довольно много объектов, которые кажутся излишними и могут быть удалены. подумайте о том, что rewritting solveRules нужно что-то похожее на:

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 по существу является функцией с карриными аргументами, вы можете пропустить экземпляр всех анализаторов и вместо этого передать аргументы конструктора в solve и позволить им капать цепочку вызовов. Я не проверил все предложенные изменения, они предназначены для того, чтобы дать вам общую идею.

ответил Rune FS 25 J0000006Europe/Moscow 2014, 22:46:33

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132