A* Search Algorithm
A* search is an informed search algorithm that uses a heuristic function to estimate the cost of reaching the goal from a given state. It combines the cost of reaching the current state and the estimated cost to reach the goal, guiding the search towards the most promising paths.
Greedy Best-First Search
Greedy best-first search selects the node that appears to be closest to the goal based on the heuristic function. It does not consider the cost of reaching the current state, which can lead to suboptimal solutions.
Uniform-Cost Search
Uniform-cost search expands the node with the lowest path cost from the start node. It is guaranteed to find the optimal solution but may explore a large number of nodes if the cost of reaching the goal is high.
Heuristic Functions
Admissibility
A heuristic function is admissible if it never overestimates the cost of reaching the goal from a given state. Admissible heuristics ensure that the A* algorithm finds the optimal solution.
Consistency
A heuristic function is consistent if the estimated cost from a given state to a successor state, plus the estimated cost from the successor state to the goal, is less than or equal to the estimated cost from the initial state to the goal. Consistent heuristics guarantee that A* expands nodes in the correct order.
Monotonicity
A heuristic function is monotonic if the estimated cost from a given state to the goal is non-decreasing along any path. Monotonic heuristics are a special case of consistent heuristics and are particularly useful for certain search algorithms.
Domain-Specific Heuristics
In addition to generic heuristics, domain-specific heuristics tailored to specific problem domains can be developed to improve search efficiency and guide the search towards relevant regions of the state space.