Uninformed Search
|
Artificial Intelligence Uninformed Search |
(see PegSolitaireNode.cc)
Description: Traditional 5-on-a-side Triangle Peg Solitaire. 15 peg holes are in a triangular hex grid as follows:
0
/ \
1---2
/ \ / \
3---4---5
/ \ / \ / \
6---7---8---9
/ \ / \ / \ / \
10--11--12--13--14
Initial State: All 15 holes have pegs except for one central vacant hole (position 4).
Operators: Peg removal via linear jump. A peg which jumps over an adjacent peg to an empty peg hole immediately beyond in the same direction results in the removal of the jumped peg. For example, in the initial state, the peg at 13 could jump the peg at 8 on its way to vacant position 4. This results in the removal of the peg at 8. Afterwards, there is a peg at 4, and positions 8 and 13 are vacant.
Goal: Exactly one peg remains after all others have been removed.
(see BucketsNode.cc)
Description: Given a 5 unit and a 3 unit bucket, how can one measure precisely 4 units? With this problem, we use search to develop a plan for measurement.
Initial State: Both buckets are empty.
Operators: Fill or empty the first or second bucket, or pour the contents of one bucket into the other until the source bucket is empty or the recipient bucket is full.
Goal: Exactly 4 units of liquid are in the two buckets.
Description: Lights Out is a puzzle where one seeks to get all lights out in a grid of lights.
Scalable Parameter: size of grid (n-by-n, n >= 2)
Initial State: An initial state is generated by generating a goal state and then randomly applying the operators described below.
Operators: Each light bulb may be selected to toggle on/off. However, all lights horizontally/vertically adjacent will also toggle on/off. For example, in the left figure above, one might select the centermost bulb to toggle. In addition to turning the center bulb on, this would also cause the bulbs above, below, to the left, and to the right of the bulb to turn off.
Goal: All lights are off.
Scalable Parameter: size of grid (n-by-n, n >= 2)
In our version of the puzzle, we code each tile with a number from 1 to n*n - 1. For each grid position, an integer describes the tile at that position, with 0 representing the empty position.
Initial State: An initial state is generated by
generating a goal state and then randomly applying the operators described
below.
Operator: Any tile (1 to n*n - 1) that is horizontally/vertically adjacent to the empty position may be moved into the empty position. For example, in the goal state below, either the 1 tile or the 4 tile may be moved into the empty upper-left corner.
Goal: The empty position is always in the upper left corner with tile numbers ascending left-to-right, top-to-bottom. This formulation is easily generalized to larger grids, and simplifies goal checking. (Assuming zero-based row and column indices, what formula expresses the relationship between the row, column, and goal configuration integer?) For example, a 4-by-4 puzzle, would have the following goal state:
+--+--+--+--+ | 0| 1| 2| 3| +--+--+--+--+ | 4| 5| 6| 7| +--+--+--+--+ | 8| 9|10|11| +--+--+--+--+ |12|13|14|15| +--+--+--+--+
Scalable Parameter: length of list (n >= 2)
Initial State: An initial state is generated by generating a sorted goal state and then randomly applying the operators described below.
Operator: Reversal operation i (1 <= i <= n) reverses the order of the first i integers of the sequence. For example, reversal operation 1 makes no change to the sequence. For the equence of n integers (a1, a2, ..., an), reversal operation 3 yields the sequence (a3, a2, a1, a4, a5, ..., an). Reversal operation n reverses the entire sequence, yielding (an, ..., a2, a1).
Goal: An ascending sorted list (ai = i for all i) of integers 1 ... n. As with other puzzles such as the sliding tile puzzle above, the real challenge is not merely to find a goal state, but rather to find an optimal (shortest) sequence of operations to reach this state.
Scalable Parameter: size of board grid (n-by-n, n >= 4)
Initial State: An empty board grid
To illustrate the importance of search problem formulation, consider the ramifications of the following operator possibilities:
Operators Version 1: Place a queen in any safe position, where a "safe" position is one which does not share the same row, column, or diagonal with an existing queen on the board.
Operators Version 2: Place a queen in any left-most safe position.
Goal: Placement of n queens safely on the board.
Exercise
SearchNode: Study the SearchNode class and the implementations of PegSolitaireNode.cc and BucketsNode.cc. Implement one of the unimplemented scalable search problem nodes. We'll use your implementation to test the characteristics and performance of several search algorithms.
Exercises
Searcher and Search Node: Most AI search techniques follow a similar pattern. Given a data structure and an initial search node, place the node in the data structure and repeat the following:
If the data structure is a queue, then search is breadth-first search. If the data structure is a stack, then search is depth-first search.
Study the Searcher and SearchNode classes and explain how they enable us to easily apply different search algorithms to different problems.
Object-Oriented Problem Solving: Suppose you wish to develop a problem-solving engine for a collection of related problems. However, you are unsure as to the best problem solving technique and will likely need to experiment with several. What would be the first classes you would design and why? (Hint: The Searcher and SearchNode classes were developed from a similar need. How can you generalize from this example?)
Breadth-First Search Implementation: Implement a Queue class. BreadthFirstSearcher.cc contains the breadth-first search algorithm outlined in comments. Complete the implementation and test the implementation with each of your SearchNode classes.
Computational Time versus Node Count: One can always measure a programs time performance using the Unix "time" command or the C/C++ "time.h" library function time(), which returns the current time. Many search researchers instead use the node count as an estimate of the time performance of their algorithms. What are the pros/cons of using node count rather than system time? Consider comparison of results run on different computers. Consider the comparison of two different search node implementations, where one has a smarter, more computationally expensive expand that reduces the need for search.
Breadth-First Search Experimentation: Measure the time and node count performance of your breadth-first search implementation on your scalable problem. For randomly generated problems, measure several runs and report the median value. Plot problem size versus runtime from the smallest size up to the largest size that usually terminates in less than one minute.
Breadth-First Search Properties: What is the time and space complexity of breadth-first search? Is the search optimal? Why or why not? Is the search complete? Why or why not? For this analysis, assume garbage collection (although you don't need to implement it). Languages with garbage collection have no need for "delete" commands. Memory is managed automatically behind the scenes, such that objects that will provably never be used again are deleted for you in an automatic garbage collection process. For this exercise, imagine what the space complexity would be if every node you'll be never able to access again is deleted and the memory reclaimed.
Advanced: Add SearchNode garbage collection capabilities to your breadth-first search implementation.
Depth-First Search Implementation: Implement a Stack class. DepthFirstSearcher.cc contains the depth-first search algorithm outlined in comments. Complete the implementation and test the implementation with your PegSolitaireNode class.
Repeated States: Perform depth-first search with the BucketsNode class. You will observe that search is unsuccessful. Given enough time, it will terminate with an error. What do you observe? Modify your code (temporarily) to print the node being expanded. What do you notice about the sequence of nodes being expanded? How does this explain the error? Does this problem manifest itself with your scalable search problem?
Extra: Devise a way to avoid infinite loops in depth-first search and thoroughly describe the tradeoffs it makes in time and space complexity, optimality, and completeness.
Breadth-First Versus Depth-First: Compare the time and space complexities of these searches. Is depth-first search optimal? Is it complete? How would you summarize the trade-off(s) between breadth-first and depth-first search? For this analysis, assume garbage collection (although you don't need to implement it) for depth-first search as described above.
Advanced: Add SearchNode garbage collection capabilities to your depth-first search implementation.
Recursive Depth-First Search: Implement a class RecursiveDepthFirstSearcher. Rather than placing children on a stack, you'll instead recursively search the children. Be especially careful with initialization. (You may need to create an auxiliary recursive function, or identify conditions under which the goalNode and nodeCount should be initialized.) Be sure to test that the Searcher object is capable of multiple searches in sequence. In this recursive implementation, dynamic memory management is much easier. Use "delete" to prevent memory leaks.
Recursive Versus Stack-based Algorithms 1: Compare and study the relationship between iterative and recursive implementations of depth-first search. Design an iterative version of quicksort that keeps a stack of pending recursive call parameters.
Recursive Versus Stack-based Algorithms 2: Generalize from the iterative and recursive implementations of depth-first search and quicksort. Describe how one can take any recursive algorithm and construct a corresponding stack-based algorithm. Given that recursion isn't strictly necessary, is there any benefit to expressing algorithms recursively? If so, what benefits? If not, why not?
Depth-Limited Search Implementation: Create a new Searcher class based on RecursiveDepthFirstSearcher called DepthLimitedSearcher. Depth-limited search is exactly like depth-first search, except that it limits the depth of search as the name implies. This is accomplished simply by not generating children for search nodes at a given depth limit. In other words, you need to modify your depth-first search code such that (1) you have a constructor that takes a depth-limit parameter, and (2) you expand a node only when its depth is less than the depth-limit. Use "delete" to prevent memory leaks. Test this algorithm with the PegSolitaireNode class for different depth-limits. Which depth limit(s) yield an optimal solution?
Depth-Limited Search versus Depth-First Search: Compare the time and space complexities of these searches. Is depth-limited search optimal? Is it complete? How would you summarize the trade-off(s) between depth-limited and depth-first search?
Iterative-Deepening Depth-First Search Implementation: Create a new Searcher class called IterativeDeepeningDepthFirstSearcher. Iterative-deepening depth-first search searches by iteratively performing depth-limited searches with successive depth-limits 0, 1, 2, etc. until a goal node is found. Thus your implementation will create and apply successive DepthLimitedSearcher objects with increasing depth-limits. Be sure to iteratively update goalNode and nodeCount accordingly. Use "delete" to prevent memory leaks. Test your implementation with BucketsNode, printing your node count and checking that it reflects the node counts of all successive depth-limited searches.
Iterative-Deepening Depth-First Search Experimentation: Measure the time and node count performance of your iterative-deepening depth-first search implementation on your scalable problem. For randomly generated problems, measure several runs and report the median value. Plot problem size versus runtime from the smallest size up to the largest size that usually terminates in less than one minute.
Iterative-Deepening Depth-First Search Versus Depth-First Search: Compare the time and space complexities of these searches. Is iterative-deepening depth-first search optimal? Is it complete? How would you summarize the trade-off(s) between iterative-deepening depth-first search and depth-first search?
The Right Tool for the Right Job: Which search algorithm(s) are most suitable for each of the different search problems you've worked with? Why? For each algorithm, what are the properties of suitable problems for application? Summarize the trade-offs between all of the algorithms you've implemented.
