package com.github.dieterdepaepe.jsearch.search.statespace.solver;

import com.github.dieterdepaepe.jsearch.datastructure.priority.FibonacciHeap;
import com.github.dieterdepaepe.jsearch.search.statespace.*;
import com.github.dieterdepaepe.jsearch.search.statespace.util.BasicSolution;

/**
 * An <a href="http://en.wikipedia.org/wiki/A*">A*</a> implementation of a {@link Solver}. It uses a {@link Heuristic}
 * to minimise the number of expanded nodes. It will always find a single {@link Solution}, which is guaranteed
 * to be optimal.
 * <p>
 * During search, nodes are expanded on a best-first basis: each time, the node with the lowest total estimated cost
 * will be expanded. Because of this, the speed and memory requirements of this solver are greatly depended on
 * the accuracy of the used {@code Heuristic}.
 * <p>
 * This solver assumes an admissible {@code Heuristic}. Should this assumption be violated, and the heuristic
 * overestimates the remaining cost by a factor of {@code e}, the found solution is still guaranteed to be at most
 * <tt>(1 + e)</tt> times more expensive than the actual optimal solution. This technique may be used to speed up
 * the search and decrease memory usage by decreasing the number of visited nodes. Note however that the found
 * solution will still indicate optimality, since the solver assumes an admissible heuristic.
 * <p>
 * This implementation is stateless and therefor thread-safe.
 * @author Dieter De Paepe
 */
public class AStarSolver implements Solver {

    @Override
    public <T extends SearchNode, U> void solve(InformedSearchNode<T> startNode,
                                                U environment,
                                                Heuristic<? super T, ? super U> heuristic,
                                                SearchNodeGenerator<T, U> searchNodeGenerator,
                                                Manager<? super T> manager) {

        FibonacciHeap<InformedSearchNode<T>> heap = new FibonacciHeap<InformedSearchNode<T>>();
        heap.insert(startNode, startNode.getEstimatedTotalCost());

        while (!heap.isEmpty() && manager.continueSearch()) {
            InformedSearchNode<T> informedNodeToExpand = heap.deleteMinimum().getValue();
            double costBound = manager.getCostBound();

            // The cost bound might have been lowered since this state was added to the queue, we need to check it again.
            if (informedNodeToExpand.getEstimatedTotalCost() > costBound)
                return;

            T nodeToExpand = informedNodeToExpand.getSearchNode();
            if (nodeToExpand.isGoal()) {
                manager.registerSolution(new BasicSolution<T>(nodeToExpand, true));
                return;
            }

            for (InformedSearchNode<T> successor : searchNodeGenerator.generateSuccessorNodes(nodeToExpand, environment, heuristic)) {
                if (successor.getEstimatedTotalCost() <= costBound)
                    heap.insert(successor, successor.getEstimatedTotalCost());
            }
        }
    }
}

@@ -530,23 +530,76 @@
  optimal
+ (assuming at least one solution state is reachable)
 .%0A * %3Cp
+/
 %3E%0A * Dur
@@ -868,24 +868,173 @@
 stic%7D.%0A * %3Cp
+/%3E%0A * This solver does not use the %7B@link com.github.dieterdepaepe.jsearch.search.statespace.SearchNode#getSearchSpaceState()%7D%0A * information.%0A * %3Cp/
 %3E%0A * This so
@@ -1192,16 +1192,22 @@
 %7B@code e
+ (%3E 0)
 %7D, the f
@@ -1578,16 +1578,17 @@
 c.%0A * %3Cp
+/
 %3E%0A * Thi
@@ -2213,37 +2213,16 @@
 cciHeap%3C
-InformedSearchNode%3CT%3E
 %3E();%0A   
@@ -2882,17 +2882,16 @@
 olution%3C
-T
 %3E(nodeTo
@@ -3076,24 +3076,125 @@
 uristic)) %7B%0A
+                // Since A* can be very memory expensive, we do a premature purging of search nodes.%0A
             

Update AStarSolver javadoc.