artificialInteligence_java_python/E2/src/CSP_SolverBacktracking.java at master · ksproska/artificialInteligence_java_python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
import consts.HeuristicEnum;

import java.time.Duration;
import java.time.Instant;
import java.util.ArrayList;


public class CSP_SolverBacktracking<P, D extends P, E extends HeuristicEnum, T extends CSP_Problem<P, D, E>, S extends CSP_PartialSolution<P, D, E>> implements CSP_Solver<P, D, E, T, S> {
    private final T cspProblem;
    private int visitedNodesCounter, tillFirstVisitedNodesCounter, returnsCounter, tillFirstReturnsCounter;
    public CSP_SolverBacktracking(T cspProblem) {
        this.cspProblem = cspProblem;
    }
    private E chosenHeuristic;
    private ArrayList<S> accumulator;
    private Duration timeCounter;

    public ArrayList<S> getResults(E chosenHeuristic) {
        this.chosenHeuristic = chosenHeuristic;
        visitedNodesCounter = 0;
        tillFirstReturnsCounter = 0;
        returnsCounter = 0;
        tillFirstVisitedNodesCounter = 0;
        accumulator = new ArrayList<>();
        Instant start = Instant.now();
        var initialPartialSolution = cspProblem.getInitialPartialSolution();
        var firstVariableInx = initialPartialSolution.getNextVariableIndex(chosenHeuristic, -1);
        getResultsRecursive((S) initialPartialSolution, firstVariableInx);
        Instant end = Instant.now();
        timeCounter = Duration.between(start, end);
        return accumulator;
    }

    private void getResultsRecursive(S cspPartialSolution,
                                     Integer currentVariableInx) {
        if(cspPartialSolution.isSatisfied()) {
            accumulator.add(cspPartialSolution.deepClone());
            returnsCounter++;
            return;
        }
        if(currentVariableInx == null) {
            returnsCounter++;
            if(accumulator.isEmpty()) { tillFirstReturnsCounter++; }
            return;
        }
        var currentVariable = cspPartialSolution.getCspVariables().get(currentVariableInx);
        for (var domainItem : currentVariable.getVariableDomain()) {
            visitedNodesCounter++;
            if(accumulator.isEmpty()) { tillFirstVisitedNodesCounter++; }
            var changedVariableInx = currentVariable.variableIndex;
            boolean areValuesCorrect = cspPartialSolution.setNewValueAtIndexOf(domainItem, changedVariableInx);
            cspPartialSolution.setVariableUsed(changedVariableInx);
//            System.out.println("\nvi:" + changedVariableInx + " d: " + domainItem);
//            System.out.println(cspPartialSolution);
//            System.out.println("ALL  Nodes: " + visitedNodesCounter + "\tReturns: " + returnsCounter);
//            System.out.println("TILL Nodes: " + tillFirstVisitedNodesCounter + "\tReturns: " + tillFirstReturnsCounter);

            if(areValuesCorrect) {
                var nextVariableIndex = cspPartialSolution.getNextVariableIndex(chosenHeuristic, currentVariableInx);
                if (nextVariableIndex == null) {
                    getResultsRecursive(cspPartialSolution, null);
                }
                else {
                    getResultsRecursive(cspPartialSolution, nextVariableIndex);
                }
            }
            cspPartialSolution.removeValueAtIndexOf(changedVariableInx);
            cspPartialSolution.setVariableReleased(changedVariableInx);
        }
        returnsCounter++;
        if(accumulator.isEmpty()) { tillFirstReturnsCounter++; }
    }

    @Override
    public int getVisitedNodesCounter() { return visitedNodesCounter; }

    @Override
    public int getTillFirstVisitedNodesCounter() { return tillFirstVisitedNodesCounter; }

    @Override
    public int getReturnsCounter() { return returnsCounter; }

    @Override
    public int getTillFirstReturnsCounter() { return tillFirstReturnsCounter; }

    @Override
    public String toString() {
        return "Backtracking\t" +
                chosenHeuristic +
//                "\n" + accumulator.get(0) +
//                "\nFound:      1/" + accumulator.size() +
                "\t" + visitedNodesCounter + "\t" + returnsCounter +
                "\t" + tillFirstVisitedNodesCounter + "\t" + tillFirstReturnsCounter +
                "\t" + timeCounter.toMillis()*0.001;
    }
}