Challenge Questions

Question 1

What are the advantages of depth first search over breadth first search?

Answer 1

It uses less memory since it only keeps track of nodes previously stored, but it can end up getting into an infinite loop
DFS may make sense in cases where there are many goals. DFS may be able to hit a goal quickly, though its unlikely to be optimal.

Question 2

What are the advantages of breadth first search over depth first search?

Answer 2

• Complete - Guaranteed to find route in finite space
• If all weights are one, will find optimal route

Problem is that BFS is exponential.

Question 3

Show the simplest example that shows that once you reach the goal, you need to expand every node whose f=g+h < cost of the path to goal you have found so far

Answer 3

h=1 c=100
———–>
S G

Question 4

Are negative path lengths to goal allowable?

Answer 4

If you get a negative one cost, you may not

Question 5

Can we have negative path lengths if graph is directed and acyclic?

Answer 5

No.

                S (<=-5)
           -5 / \ 5
             /     \
(<=8)   L        R (<=-10)
            \      /
          8  \  / -10
               G

cL​=3, cR=−5

Not just A* fails, but Uniform Cost fails, even if they are undirected and acyclic. The heuristic does not have to be monotonic.

Question 6

Suppose we have NNN admissible heuristics, h1,h2,⋯ ,hNh_1, h_2, \cdots, h_Nh1​,h2​,⋯,hN​. Which of the following are admissible? From the admissible ones, rank them by dominance

Answer 6

max(h1​,h2​,⋯,hN​): Yes

min⁡(h1,h2,⋯ ,hN): Yes

sum(h1​,h2​,⋯,hN​): No, you can have unbounded if N was infinite

avg(h1​,h2​,⋯,hN​): Yes

max > avg > min

This is the first example of mixture of experts

Question 7

Consider the problem of morphing one word into another by making one character change at a time. You want to write a program that does this for two, random, 6-letter words. Note that all the intermediary words have to be valid.

Let’s say you represent every word as a node and all words one character change away as its children. Then, you can use a search algorithm in this word space to go from the start to goal node. Note that every step of the path has to be a valid word. However, not all combinations are valid words, so you have an API call that will tell you if an input is a valid word. Assume no more resources than those explicitly mentioned.

Question 8

Part A

You want to try using an uninformed unidirectional search first. Which method will you use (taking into consideration time and space constraints) under the following conditions?

1. It’s guaranteed that a valid solution will be found with exactly 6 changes.

Answer 8

You’d want to use a depth first search. You’d potentially be able to return a solution before having to search whole layers of the graph, potentially saving time.
Since the lions share of the time complexity of a breadth first search is consumed on the last layer, its possible that the depth first could avoid a significant amount of searching.

Question 9

Part A

You want to try using an uninformed unidirectional search first. Which method will you use (taking into consideration time and space constraints) under the following conditions?

2. It’s not guaranteed that a valid solution will be found with exactly 6 changes. (A valid solution is guaranteed.)

Answer 9

Breadth first search would be the way to go here. Without the guarantee of exactly 6 changes, then the solution could be found on any level. Given that the majority of search time in Breadth first search is taken on the final layer, if you could find a solution before that final layer it could save significant time.