How do we represent and solve problems?
- Define the problem precisely.
- Isolate and represent.
- Choose algorithm and apply.
What are the key properties of problem representation?
- Make important objects and relations explicit.
- Suppress unimportant and irrelevant detail.
- Expose natural constraints.
- Concise - efficiently describe a given scenario.
- Complete - everything necessary can be described.
T or F. FA model is an example of a problem representation model?
True.
Distinguish between state space and search tree.
The state space is the set of all valid states that can exist in our “problem universe”.
Search trees (used for search algorithms) corresponds to the sequence of paths that can be reached from a given start state.
What are the two important cost considerations in searching?
Search costs: The cost to find a solution.
Solution costs: The cost of a solution
Higher search costs (longer search) = lower solution costs.
Define the four metrics for comparing search methods.
Time Complexity
Space Complexity
Completeness: Is success guaranteed when possible.
Optimality: Is best solution guaranteed to be found.
What are the two categories of search strategies?
Uninformed Search: No problem-specific knowledge. Blind search.
Informed Search: Has problem-specific knowledge to influence search. Heuristic search.
Pseudocode for blind search. Note the differences between, breadth-first and depth-first.
visited.add(start) # changes
path = path + [start]
if start == goal:
return path
for succesor of node
if not visited
result = recursive_call(where start = neighbour)
if result exists:
return result
return None
Breath-First adds at end of queue.
Depth-First adds at start of queue
What is worst case time complexity and space complexity of BFS?
O(2^n) exponential for both
Note 2 is the number of successors of the root and n is the depth of the goal.
Talk about completeness and optimality for BFS.
Complete: Yes for finite depth.
Optimal: Yes when all step costs are identical otherwise No.
What is worst case and best case time complexity and space complexity of DFS?
Time:
Best: O(d) where d is the depth of the goal. Is in the first path we explore.
Worst: O(2^d) where 2 is the number of children of the root. We are assuming the goal is located on the far right at depth d.
Space:
Worst case: O(b * m) as we can reclaim space used by paths we can no longer extend further.
Best case: O(d)
Talk about completeness and optimality for DFS.
Complete: No unless we remove cycles.
Optimal: No
What is random queuing?
Uninformed search that places new nodes at random place in the queue just as likely to deepen as to broaden.
What is depth-limited search?
DFS that cannot go beyond certain depth.
What is iterative deepening DFS?
Executes DFS search with an increasing depth limit (2,3,4 …) until time runs out and program returns current best guess move.
Discuss time & space complexity, completeness and optimality with Iterative Deepening DFS and Depth Limited.
Iterative Deepning DFS:
Time: O(b^d)
Space: O(bd)
Complete: Yes when b is finite
Optimal: Yes when all step costs are identical.
Depth Limited:
Same but not complete or optimal.
What is a heuristic function? What is a heuristic?
Scores a node in a search tree according to how close to the target / goal state it seems to be. Better heuristic = better estimate.
Set of rules that model how to achieve goal in function.
What does h(n) = 0 mean?
n is a goal node
Why are heuristics difficult?
They are problem specific, we can come up with many different heuristics for the same problem but coming up with the perfect one is challenging.
What is greedy search?
“Best-first”
Expands node closest to the goal. Lowest heuristic.
How does greedy search adapt the blind search algorithm?
It sorts the new paths according to the evaluation function before adding them to the queue.
How does branch & bound search alter the blind search algorithm?
It adds the new paths to the queue and then sorts the entire queue.
What is branch & bound search?
Always extend the least-cost partial path. Do this till you reach a goal you are likely to have found optimal solution. But to be certain extend all remaining paths until their path cost equals the optimal suspect.
Explain f(n) = g(n) + h(n)
f(n) is total solution cost
g(n) is partial solution cost so far
h(n) is solution cost remaining
