Search Quiz
ICS171
Name___________ ID____________

No text, no notes, no questions. Do the best that you can on each question. No questions will be answered about the quiz questions. If you think a question is ambiguous, write your interpretation and answer your modified question. Be reasonable.

The following abbreviations are used: BF = branching factor, DFS = depth first search, BFS = breadth first search, IDS = iterative deepening search,
A* = A* search, LI = local improvement search, HC = hill-climbing search.

[pic]

1. For the 8-tile puzzle, what is the average branching factor, assuming the blank is equally likely to occur in any position. Show your work. (4*2 + 4*3 +1*4)/9 = 24/9 = 2 & 2/3.

2. Suppose that you are solving the 8-tile puzzle where it has solution. Which of the methods (DFS, BFS, IDS) is guaranteed to find a solution, assuming no computational limits are reached. List all that are correct. DFS, BFS, IDS

3. For the same puzzle, which of the methods (DFS,BFS,IDS) is guaranteed to find the shortest solution? List all that are correct. BFS, IDS

4. For the same puzzle, which methods are guaranteed to use no more than O(BF * length of solution) amount of memory. DFS, IDS

5. Suppose you apply the A* algorithm to the same problem. You decide to let f = current cost of the path. Would it be appropriate to let h = 0 for all states? Yes or no and why. Yes. h is admissible.

6. Suppose you apply A* to the same puzzle, with f = current cost of path and h = 0. A* would then behave the same as DFS or BFS or IDS? BFS. ------ The next question all relate to the same problem. Suppose you have forgotten everything you learned in your theory classes and decided to apply an AI search technique to the problem of sorting an array of N different integers. There are multiple correct answers.

7. Describe the initial state a) An array (list) of the number. Or b) a pair or similar.

8. Describe the goal state All the numbers are in the right order.

9. Describe a set of legal operators a) swap two values if out-of-order or move out-of-order element b) insert number so that order is maintained (yields insertion sort)

10. What to cost (O notation) of finding and applying your operators. (2pts) a) O(N*N) to find; trivial to O(N) to apply b) O(N) if numbers in a list; O(N*N) if numbers in an array.

The next questions refer to the diagram on page 1. The diagram illustrates a search tree where the oval nodes (10 and 12) are the goal nodes.

11. What solution will BFS find? 10 12. What solution will DFS find? 12 13. What solution will IDS find? 10 14. What solution will depth limited search find, where the search limit is 3. 12.

-----------------------
10

12

14

13

11

9

8

7

6

5

4

3

2

1