Part 2: Uninformed Search
Now we move on to some actual algorithms.
2.1) [4pts] Using your initial state from Part 1, show how Breadth First Search (BFS) would explore states.
Show your work in detail, including the contents of the Open and Closed sets after each iteration.
Because the open set will grow quite large, you may abbreviate by leaving out parts of the open and closed sets which don’t change. However, make sure it is clear what is leaving the open set and what enters the open/closed sets (and where!).
Hint: As you work through the BFS operation, trace which states it explores on your tree from Part 1. Is it following the pattern you expect? If not, maybe you’ve made a mistake?
If you find yourself needing to do more than 10 iterations to find a goal state, then after the 10th iteration, you may simply report which state is visited, rather than the entire contents of the Open & Closed sets.
2.2) [0.5pts] If you had used Uniform Cost Search (UCS) instead of BFS above, how would your results change?
2.3) [4pts] Now repeat (2.1) but using Depth-Limited Search (DLS) with a depth limit of 4.
Remember that DLS needs to know the depth in the search tree of each state (number of actions to reach), so you will need to include that extra information in your open set. (The formatting is up to you, but you could use the UCS example on the slides for inspiration.)
Hint: When you generate successor (children) states, how do you know what their depth is? Can you calculate their depth if you know the predecessor (parent) depth?
2.4) [4pts] Again, repeat (2.1) using Iterative Deepening Search (IDS).
Keep in mind, IDS runs DLS multiple times with increasing depth limits, so this problem will be somewhat like repeating (2.3) multiple times. Make sure it is clear each time where the depth limit changes (and a new run of DLS starts).
Hint: You may be able to re-use (copy-paste) many pieces of your work from (2.3) to save time.
Part 3: Informed Search
3.1) [6pts] Finally, repeat (2.1) using A* search using the “misplaced tiles” heuristic (see slide 25).
Note, as with DLS, A* requires tracking extra information about a state in order to operate. At a minimum, you will need to track the total estimated path cost for each node ( f ). But I highly recommend tracking the path cost so far ( g ) as well, as it will make you’re job significantly easier.
Hint: The path cost so far ( g ) has a very strong relationship with the depth from DLS…
Assignment status: Solved by our experts