BFS, DFS, uniform cost, A-star, heuristics, minimax, alpha-beta pruning and constraint satisfaction.
41 cards · basic cards · AI-written, checked twice. Edit anything.
- What order does breadth-first search explore nodes?
Show answer
Level by level, visiting all nodes at distance k before exploring distance k+1- What data structure does breadth-first search use?
Show answer
A queue (FIFO)- Is breadth-first search complete?
Show answer
Yes, it will always find a solution if one exists- Is breadth-first search optimal for path length?
Show answer
Yes, if all edge weights are equal- What is the time complexity of BFS?
Show answer
O(V + E) where V is vertices and E is edges- What is the space complexity of BFS?
Show answer
O(V), proportional to the number of nodes in the queue- What order does depth-first search explore nodes?
Show answer
As far as possible along each branch before backtracking- What data structure does depth-first search use?
Show answer
A stack (LIFO)- Is depth-first search complete in cyclic graphs?
Show answer
No, it may get stuck in a cycle without cycle detection- Is depth-first search optimal?
Show answer
No, it does not guarantee the shortest path- What is the time complexity of DFS?
Show answer
O(V + E) where V is vertices and E is edges- What is the space complexity of DFS?
Show answer
O(h) where h is the maximum depth of the tree- What does uniform cost search optimize?
Show answer
The path with the lowest cumulative cost to reach a node- How does uniform cost search choose which node to expand?
Show answer
It expands the node with the smallest accumulated path cost g(n)- Is uniform cost search complete?
Show answer
Yes, if edge costs are positive and a solution exists
FlashKeepers