Informed Search Strategies and A* Search Flashcards

Vocabulary flashcards covering informed search strategies, A* search mechanics, heuristic properties like admissibility and consistency, and examples from the 8-puzzle problem.

Informed Search Strategies

Search strategies that utilize external information provided by a domain expert or specific information about the domain to guide the search closer to the goal state.

Heuristic

A function that provides an estimated cost to reach the goal state from a specific node in the state space.

Greedy Best-First Search

An informed search algorithm that sorts paths in its frontier based solely on the heuristic value, moving in the direction it estimates is closest to the goal.

Admissibility

A property of a heuristic where the estimated cost to the goal is always less than or equal to the real path cost, mathematically expressed as $h(n) \leq h^*(n)$.

A* Search

An algorithm that uses an evaluation function $f(n) = g(n) + h(n)$ to order nodes in the priority queue, where $g(n)$ is the real path cost from the start and $h(n)$ is the heuristic estimation.

$$\text{g(n)}$$

The real path cost from the start state to the current node $n$.

$$\text{f(n)}$$

The evaluation function used in A* search representing the estimated total path cost through node $n$ to the goal state.

Euclidean distance

The straight line distance between two points, serving as an admissible heuristic in navigation problems because it identifies the shortest possible path.

Relaxed problem

A technique for designing heuristics by removing certain rules or constraints from the original problem, such as picking up 8-puzzle tiles directly instead of sliding them.

Misplaced tiles heuristic

An admissible heuristic for the 8-puzzle game that counts the total number of tiles currently positioned in the wrong spot compared to the goal state.

Manhattan distance

An admissible heuristic calculated by finding the differences in the x and y coordinates between current and goal states and summing them up.

Dominance property

A property where, for two admissible heuristics $h_1$ and $h_2$, if $h_1(n) \geq h_2(n)$ for all nodes, then $h_1$ is superior as it is closer to the true cost and will likely expand fewer nodes.

Closed list

A data structure (also known as a visited, explored, or expanded list) that stores states already generated to prevent the algorithm from revisiting redundant nodes.

Consistency

A property, also known as monotonicity, where the heuristic value satisfies the triangular property, ensuring the evaluation function $f(n)$ never decreases along any path.

Time and Space Complexity of A*

In the worst-case scenario, both are represented as $b^d$, which is similar to Uniform Cost Search ($UCS$).