Sample Test #2
Answers
CIS447 – 2006
Name ________________________
All answers go in the places provided below.
State Space Search
Enhanced True/False
(1-20) For each statement, indicate whether it is true or false. Correct those that are false to make them true.
1. A search algorithm takes a problem as input and returns a solution in the form of a queue.
False: an action sequence
2. The continuous, identifiable configurations that a problem may take on are states.
False: discrete
3. Initial state: One or more states that represent the point of departure in the search for the goal state(s).
True
4. Leaves: One or more states that represent a solution to the problem.
False: Goal state(s)
5. Actions: Steps that can be taken to move toward the goal.
True
6. Operator: A specialized description of an action which may specify the conditions necessary for an action to be taken and the state that results from that action.
True
7. State space: The set of all states reachable from the initial state by any sequence of goals.
False: actions
8. In the graphical representation of the state space the states are nodes and the actions are arcs.
True
9. Path: In the goal state, any sequence of actions leading from one state to another.
False: state space
10. Goal test: a test that can be applied to determine whether the current state is a goal state.
True
11. Path cost function: a function that assigns a cost to the goal state, denoted g.
False: a path
12. Solution: A path from the initial state to a state that satisfies the goal test.
True
13. Branching factor: The number of states (on average) that can be reached from the goal state.
False: a given state
14. Fringe/frontier: The collection of nodes waiting to be expanded.
True
15. Abstraction: The process of removing irrelevant details from the goal state.
False: a problem representation
16. The general class of sliding block puzzles is known to be NP-complete.
True
17. Search strategy: Determines which state to expand next.
True
18. Search tree: the graph of states (represented by nodes) generated during the search process.
True
19. A search tree can differ from the state space, since the state space has many more nodes.
False: the search tree can contain the same state several times.
20. A finite state space can yield an infinite search tree.
True
A* Search
(21-32) For the questions below, assume that the goal configuration is:
123
456
780
21. Expand the node below which represents the initial state of an 8-puzzle problem. Draw all new nodes with corresponding arcs.
Answer:
22. For each of the new nodes calculate h(n), where h is the OOP (number of tiles out of place) heuristic. Write the answer next to each node of your diagram.
Answer:
23. For each of the new nodes calculate f(n) based on the OOP heuristic. Write the answer on your diagram directly below the h values.
Answer:
24. Draw a diagram showing the result of expanding the node that would be chosen by the OOP heuristic.
Answer:
25. How many fringe nodes are there now?
Answer: 6
26. Which node would be expanded next, by the OOP heuristic?
Answer:
Any of these:
853 803 853
264 254 240
701 761 761
27. Expand the node below which represents the initial state of an 8-puzzle problem. Draw all new nodes with corresponding arcs.
Answer:
28. For each of the new nodes calculate h(n), where h is the Manhattan distance heuristic. Write the answer next to each node of your diagram.
Answer:
29. For each of the new nodes calculate f(n) based on the Manhattan distance heuristic. Write the answer on your diagram directly below the h values.
Answer:
30. Draw a diagram showing the result of expanding the node that would be chosen by the Manhattan distance heuristic.
Answer:
31. How many fringe nodes are there now?
Answer: 6
32. Which node would be expanded next, by the Manhattan distance heuristic?
Answer:
Either of these:
062 620
453 453
781 781
BBESS
33-45. Draw a diagram showing the relationship of the functions listed below. Draw connecting arcs to illustrate the execution flow and label the arcs showing data flow.
run {user interface}
queryans
lookinfb
tryprompting
askfor
infproc
tryrule
checkprems
checkprem
putinfb
Answer:
(46-50) Write the code for the following BBESS functions:
46. queryans
(defun queryans (query)
(cond ((lookinfb query))
((tryprompting query))
((infproc (getrules query)))
(t "Sorry. No rules for that!")))
47. lookinfb
(defun lookinfb (query)(getval query *fb*))
48. tryprompting
(defun tryprompting (query)
(let ((prompt (getprompt query)))
(if prompt (putinfb (list query (askfor prompt (getokvals query)))))
))
49. infproc
(defun infproc (rules)
(if rules
(or (tryrule (car rules))(infproc (cdr rules)))))
50. tryrule
(defun tryrule (rule)
(if (checkprems (premsof rule))(putinfb (conclusionof rule))))
50. checkprems
(defun checkprems (prems)
(if (null prems)
t
(and (checkprem (car prems)) (checkprems (cdr prems)))))
50. checkprem
(defun checkprem (prem)
(eq (queryans (atrbof prem))(valof prem)))
50. putinfb
(defun putinfb (avpair)
(setf *fb* (cons avpair *fb*))
(valof avpair))