IDAStarSearch

IDAStarSearch.java

    @Override
    public Solution search(Problem problem) {
        statistics.reset();
        stopped = false;

        this.heuristic = problem.getHeuristic();
        limit = heuristic.compute(problem.getInitialState());

        Solution solution;
        do {
            solution = graphSearch(problem);
        } while (solution == null);

        return solution;
    }

    @Override
    protected Solution graphSearch(Problem problem) {
        newLimit = Double.POSITIVE_INFINITY;

        frontier.clear();
        frontier.add(new Node(problem.getInitialState()));

        while (!frontier.isEmpty() && !stopped) {
            Node n = frontier.poll();

            if (problem.isGoal(n.getState())) {
                return new Solution(problem, n);
            }

            List<State> successors = problem.executeActions(n.getState());
            addSuccessorsToFrontier(successors, n);
            computeStatistics(successors.size());
        }

        limit = newLimit;
        return null;
    }

    @Override
    public void addSuccessorsToFrontier(List<State> successors, Node parent) {
        for (State successor : successors) {
            double g = parent.getG() + successor.getAction().getCost();

            if (!frontier.containsState(successor)) {
                double f = g + heuristic.compute(successor);

                if (f <= limit) {
                    Node node = new Node(successor, parent, g, f);
                    if (!node.isCycle()) {
                        frontier.add(node);
                    }
                } else {
                    newLimit = Math.min(newLimit, f);
                }
            } else if (frontier.getNode(successor).getG() > g) {
                frontier.removeNode(successor);
                frontier.add(new Node(successor, parent, g, g + heuristic.compute(successor)));
            }
        }
    }