Informed Search Strategies - Heuristic Properties, Weighted A*, and IDA*

Vocabulary flashcards focusing on heuristic properties (admissibility, consistency, dominance), closed lists, Weighted A* Search, and Iterative Deepening A* Search (IDA*) from the lecture.

Admissible Heuristic

A heuristic function $h(n)$ that never overestimates the actual cost to reach the goal state, meaning it is less than or equal to the true path cost, which guarantees that $A^*$ search will return an optimal solution.

Dominance (Heuristics)

A property comparing two admissible heuristics where one consistently yields higher or equal values than the other for all nodes, leading to a search that finds a solution faster on average.

Consistent Heuristic (Monotonic Heuristic)

A heuristic where for every node $n$ and every successor $n'$ of $n$, the estimated cost $h(n)$ satisfies $h(n) \neq g(n)$ and $h(n) \neq c(n, n') + h(n')$, ensuring heuristic values monotonically decrease toward the goal.

Triangular Property of Consistency

A geometric concept used to remember heuristic consistency, stating that the estimated cost $h(n)$ from node $n$ to the goal must be less than or equal to the transition cost $c(n, n')$ plus the estimated cost $h(n')$ from successor $n'$ to the goal.

Closed List

A data structure tracking explored or visited nodes in graph search algorithms to avoid re-exploring the same nodes and to improve algorithmic efficiency.

Closed List with Reopening

A modified search implementation that re-checks closed-list nodes and re-adds a state to the frontier if a newly generated path yields a lower $f$-value, maintaining optimality even with inconsistent heuristics.

Weighted A* Search

A modification of $A^*$ search that adds a weight parameter to the evaluation function $f(n)$, allowing control over the balance between Uniform Cost Search (UCS) and Greedy Best-First Search.

Weight Setting $w = 0$ in Weighted A*

A setting that eliminates the influence of the heuristic, transforming the Weighted $A^*$ search into Uniform Cost Search (UCS) which considers only path cost $g(n)$.

Weight Setting $w = 1$ in Weighted A*

A setting that creates an equal balance between path cost $g(n)$ and heuristic cost $h(n)$, resulting in classical $A^*$ search.

Iterative Deepening A* Search (IDA*)

A search algorithm that combines the low memory footprint of Depth-First Search (DFS) with the optimality of $A^*$ search by utilizing a stack frontier and iteratively increasing an evaluation threshold.

Threshold in IDA*

An $f$-value limit used during an iteration of IDA* that restricts node exploration; it is updated for the next iteration to the minimum $f$-value among all nodes that exceeded the current threshold.