Informed search step by step: greedy, A*, IDA*
What the exam asks you to produce: the frontier written out at every step as an ordered list of paths , each with its g (cost so far), h (heuristic estimate of the rest) and f = g + h, plus a statement of which value the queue is sorted by, which loop breaking rule you used, and whether the heuristic is admissible and consistent.
Part 5: Informed Search (chapter) | Part 4: Uninformed Search | Study pack index
|◀
◀
▶
▶|
play
speed
step 0 of 0
problem
algorithm
A*, orders by f = g + h
greedy, orders by h
IDA*, f-bounded depth first
search
tree search
graph search, closed set
graph search, path deletion
ties
newest path first
oldest path first
mistake
none, run the correct rule
stop when the goal is generated
sort by h while calling it A*
Heuristic values, editable
Type any number. Every edit re-runs the search and the two checks below.
What the mode toggle is testing
Frontier: the ordered list of paths
Written answer, one row per step
Keys: ← and → step, space toggles autoplay. Arrow keys do nothing while you are typing in a heuristic box.
Terms used here, plain meaning in brackets once: frontier (the paths waiting to be expanded, kept in order), node = path (a node of the search tree stands for the whole path taken from the start), admissible (h never overestimates the true remaining cost), consistent (h drops by at most the arc cost along every arc, and h at the goal is 0), closed set (the set of states already expanded, also called the reached or explored set), path deletion (a new path to a state is kept only when it is cheaper than the best one known, and the paths built on the old route are thrown away).
Sources: problem 1 and problem 2 and problem 4 are from FAI_Part5_InformedSearch_25-26.pdf, PDF pages 22 to 23, 46 and 55 to 57. Problem 3 is exercise session 3, question 1.5, from FAI_Exercises3_Informed_Search.pdf with the trace and the repair in FAI_ExerciseSession3_Informed_Search_SOLUTIONS.pdf, PDF pages 94 to 119. Problem 5 is constructed for this pack.