Package org.drip.graph.astar

Class FHeuristic

java.lang.Object
org.drip.graph.astar.FHeuristic
All Implemented Interfaces:
VertexFunction
Direct Known Subclasses:
DynamicWeightFHeuristic, StaticWeightFHeuristic
public class FHeuristic
extends java.lang.Object
implements VertexFunction
FHeuristic implements the A* F-Heuristic Value at a Vertex. The References are:

  • Dechter, R., and J. Pearl (1985): Generalized Best-first Search Strategies and the Optimality of A* Journal of the ACM 32 (3) 505-536
  • Hart, P. E., N. J. Nilsson, and B. Raphael (1968): A Formal Basis for the Heuristic Determination of the Minimum Cost Paths IEEE Transactions on Systems Sciences and Cybernetics 4 (2) 100-107
  • Kagan, E., and I. Ben-Gal (2014): A Group Testing Algorithm with Online Informational Learning IIE Transactions 46 (2) 164-184
  • Russell, S. J. and P. Norvig (2018): Artificial Intelligence: A Modern Approach 4th Edition Pearson
  • Wikipedia (2020): A* Search Algorithm https://en.wikipedia.org/wiki/A*_search_algorithm




Author:
Lakshmi Krishnamurthy

  • Constructor Details

    • FHeuristic

      public FHeuristic​(VertexFunction gHeuristic, VertexFunction hHeuristic) throws java.lang.Exception
      FHeuristic Constructor
      Parameters:
      gHeuristic - The G Heuristic
      hHeuristic - The H Heuristic
      Throws:
      java.lang.Exception - Thrown if the Inputs are Invalid

  • Method Details

    • gHeuristic

      public VertexFunction gHeuristic()
      Retrieve the G Heuristic
      Returns:
      The G Heuristic

    • hHeuristic

      public VertexFunction hHeuristic()
      Retrieve the H Heuristic
      Returns:
      The H Heuristic

    • evaluate

      public double evaluate​(Vertex vertex) throws java.lang.Exception
      Description copied from interface: VertexFunction
      Compute the Value at the Vertex
      Specified by:
      evaluate in interface VertexFunction
      Parameters:
      vertex - The Vertex
      Returns:
      The Value
      Throws:
      java.lang.Exception - Thrown if the Input are Invalid

    • isMonotone

      public boolean isMonotone​(Network graph, Edge edge) throws java.lang.Exception
      Indicate if the Heuristic is Monotone
      Parameters:
      graph - The Graph
      edge - The Edge
      Returns:
      TRUE - The Heuristic is Monotone
      Throws:
      java.lang.Exception - Thrown if the Inputs are Invalid

    • isConsistent

      public boolean isConsistent​(Network graph, Edge edge) throws java.lang.Exception
      Indicate if the Heuristic is Consistent
      Parameters:
      graph - The Graph
      edge - The Edge
      Returns:
      TRUE - The Heuristic is Consistent
      Throws:
      java.lang.Exception - Thrown if the Inputs are Invalid

    • reducedWeight

      public double reducedWeight​(Network graph, Edge edge) throws java.lang.Exception
      Compute the Reduced Weight of the Edge
      Parameters:
      graph - The Graph
      edge - The Edge
      Returns:
      The Reduced Weight of the Edge
      Throws:
      java.lang.Exception - Thrown if the Inputs are Invalid