Link Search Menu Expand Document
REPL
read-eval-print loop
Uninformed search
Search in which we only know the goal test and successor function
State space
All valid configurations
Successor function
States reachable one step away from s, which can be 0 or more
State space graph:
A direct graph showing how applications of the successor function enable us to move from one state to another
Search tree:
A tree data structure showing how a search algorithm navigates a state space graph, generating and expanding states
Generated state:
A state that has been returned by the successor function, meaning we know how to reach it from the initial state
Expanded state:
A state that has been visited during the search
Fringe
Generated states that have not been expanded, also called OPEN
CLOSED states
States that have already been visited (expanded) in the search
BFS
Breadth-first search
Branching factor
Number of states returned by the successor function
UCS
Uniform-cost search
DFS
Depth-first search
IDS
Iterative deepening search
BIBFS
Bidirectional breadth-first search
MEMDFS
Memorizing DFS
PCDFS
Path Check DFS
Priority queue
A data structure that maintains a reference to the item with the minimum value. Can be implemented using a heap.