Sample Test #2
This is a practice test. After taking it, check your answers which are also posted.
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.
2. The continuous, identifiable configurations that a problem may take on are states.
3. Initial state: One or more states that represent the point of departure in the search for the goal state(s).
4. Leaves: One or more states that represent a solution to the problem.
5. Actions: Steps that can be taken to move toward the goal.
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.
7. State space: The set of all states reachable from the initial state by any sequence of goals.
8. In the graphical representation of the state space the states are nodes and the actions are arcs.
9. Path: In the goal state, any sequence of actions leading from one state to another.
10. Goal test: a test that can be applied to determine whether the current state is a goal state.
11. Path cost function: a function that assigns a cost to the goal state, denoted g.
12. Solution: A path from the initial state to a state that satisfies the goal test.
13. Branching factor: The number of states (on average) that can be reached from the goal state.
14. Fringe/frontier: The collection of nodes waiting to be expanded.
15. Abstraction: The process of removing irrelevant details from the goal state.
16. The general class of sliding block puzzles is known to be NP-complete.
17. Search strategy: Determines which state to expand next.
18. Search tree: the graph of states (represented by nodes) generated during the search process.
19. A search tree can differ from the state space, since the state space has many more nodes.
20. A finite state space can yield an infinite search tree.
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.
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.
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.
24. Draw a diagram showing the result of expanding the node that would be chosen by the OOP heuristic.
25. How many fringe nodes are there now?
26. Which node would be expanded next, by the OOP heuristic?
27. Expand the node below which represents the initial state of an 8-puzzle problem. Draw all new nodes with corresponding arcs.
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.
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.
30. Draw a diagram showing the result of expanding the node that would be chosen by the Manhattan distance heuristic.
31. How many fringe nodes are there now?
32. Which node would be expanded next, by the Manhattan distance heuristic?
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
(46-50) Write the code for the following BBESS functions:
46. queryans
47. lookinfb
48. tryprompting
49. infproc
50. tryrule
50. checkprems
50. checkprem
50. putinfb