CPSC5610讲解、data辅导、讲解Python程序语言、辅导Python
- 首页 >> Java编程 CPSC5610 – Artificial Intelligence
Assignment 1: Problem Solving by State-Space Search
Goals for this assignment
1. Understand the components of a search-based problem solver and see several
implementations
2. Apply concepts of state-space search to several different problems
3. Understand the power of heuristics applied to state-space search problems
Problem 1: PacMan Search Agent
You will work on the Search Agent problems in the Berkeley AI Pacman projects. The page for that
problem is here.
You will complete questions Q1 through Q7.
Problem 2: Pancake Sort
Pancake sort is a sorting algorithm that is especially popular in job interviews because it's simple, and
most of the time candidates have not studied it an algorithms class.
A "flip" of an arry works as follows: if you flip array A at index i
• The elements with an index of 0 to i are reversed
• The elements with an index i+1 or greater are not changed
For example
flip([3, 1, 4, 5, 2], 2) => [4, 1, 3, 5, 2]
flip([3, 1, 4, 5, 2], 0) => [3, 1, 4, 5, 2]
flip([3, 1, 4, 5, 2], 4) => [2, 5, 4, 1, 3]
The pancake sort problem is: take as input an array of elements – assume integers for this assignment,
and return a sequence of flip operations that, when applied to the input array, results in an array that is
in sorted order.
For example
Begin [3, 1, 4, 5, 2]
flip_1 [1, 3, 4, 5, 2]
flip_3 [5, 4, 3, 1, 2]
flip_4 [2, 1, 3, 4, 5]
flip_1 [1, 2, 3, 4, 5]
You will start with the search framework we developed in class. You must use this framework for your
solution. After that you may only add a new
• World state definition class
• Problem definition class
• Evaluation instance (if you implement a heuristic)
You will develop a function solvePancakeSort that takes a list of integers as input, and returns a list
of strings, each one describing a "flip move." In addition your function will return the same stats tuple
returned by aStarSearch. Here is an example of the mapping from input list to output solution.
[3, 1, 4, 5, 2]) => ["flip_1", "flip_3", "flip_4", "flip_1"]
For extra credit, see how much you can improve the performance using heuristics. Look at this paper,
and see whether you can implement its heuristic and how well the heuristic does. I will give up to 5
points extra credit for heuristics that are empirically better than uninformed search (i.e. you have to
demonstrate that your heuristic outperforms DFS and BFS.
Work on a heuristic is worth a maximum of 5 points, but your total score on the assignment cannot
exceed 100 points.
The notebook pancakeSearch.ipynb provides additional detail, and a template for handing in your
work.
Problem 3: Solving the Strimko Puzzle Using Search
Strimko is a number game like Sudoko in that one starts with a game board partially filled with numbers;
to solve the game, numbers are assigned to empty cells. Notice in this example, the board has four
rows, four columns, and four "chains" or "streams," which are connected sequences of cells. The term
"chain" and "stream" are interchangeable – different sources use these two terms to mean the same
thing.
Rows, columns and chains all have the same length (for example 4 for a 4x4 game) and every cell
appears in exactly one chain. To solve the puzzle, assign a number to every cell so that the numbers in
each row, column, and chain are distinct. The left figure is a valid initial board, the right figure is a
solved board. Ignore the R1 and C1 labels to the sides.
You will start with the generic search framework we used in the Search Lab, and build a problem solver
for Strimko using the state-space search implementation.
Here are some requirements about how we will represent the game.
A Strimko problem has two components: the initial board, and the chains.
For a problem of size n, the initial board will be represented by a Python nested list: it will be a list of n
elements, each of which is a list of n elements. Zero will be used to denote empty cells. For the
example above, the initial game board would be represented like this:
[[0,0,0,1], [0,0,2,0], [0,4,0,0], [0,0,0,0]]
The chains will be represented by a list of length n, each element of which is a list of length n of 2-tuples,
each representing a coordinate pair. A coordinate pair is (row, column) and 0-based. The chains for the
example board above would be:
[[(0,0), (1,1), (2,0), (0,2)],
[(1,0), (0,1), (1,2), (0,3)],
[(3,0), (2,1), (3,2), (2,3)],
[(3,1), (2,2), (1,3), (3,3)]]
The order in which coordinates appear in the chains is not significant.
You will develop a function solveStrimko that takes as input two required arguments, an initial board
and chains respectively, and returns a solution game board if one exists, or None otherwise. In addition
your function will return the same stats tuple returned by aStarSearch.
Notice that the A-star search function returns a list of "actions," but your solveStrimko function must
return a game board. You must write the code to convert a list of actions to a game board.
You may assume that the initial board and chains are legal in the sense that the chains and initial
assignment of values obey the rules
Heuristic – Extra Credit
You can receive up to 5 points for this section, but not to exceed 100 points for the assignment.
Develop a heuristic that should guide the A-Star search algorithm to a solution quickly. The point of this
part is just to get you to formulate some heuristic, and implement it within the search framework. The
heuristic can be simple, and it might not work any better than an informed strategy. (Sometimes they
just don't, and that's the way it goes.) Document your solution as follows:
• What is the idea behind your heuristic
• How did you implement it
• How did it run compared to the best uninformed algorithm
The notebook strimko.ipynb provides additional detail, and a template for handing in your work.
Handin Details
Please hand in the following (online Canvas submission)
• A single Zip archive, containing five files. The files are
o search.py, searchAgents.py (for the Pacman problems)
o pancakeSearch.ipynb (for the Strimko problem)
o strimko.ipynb (for the Strimko problem)
o Retrospective.pdf
• Your Retrospective.pdf file must contain the following material
o Your name
o For each of the three questions
▪ Is your solution fully working or not?
▪ Was there anything particularly noteworthy or challenging about the
question
o How much time did you spend on the assignment overall?
o Overall how would you evaluate the homework in terms of understanding and
applying concepts discussed in class
Assignment 1: Problem Solving by State-Space Search
Goals for this assignment
1. Understand the components of a search-based problem solver and see several
implementations
2. Apply concepts of state-space search to several different problems
3. Understand the power of heuristics applied to state-space search problems
Problem 1: PacMan Search Agent
You will work on the Search Agent problems in the Berkeley AI Pacman projects. The page for that
problem is here.
You will complete questions Q1 through Q7.
Problem 2: Pancake Sort
Pancake sort is a sorting algorithm that is especially popular in job interviews because it's simple, and
most of the time candidates have not studied it an algorithms class.
A "flip" of an arry works as follows: if you flip array A at index i
• The elements with an index of 0 to i are reversed
• The elements with an index i+1 or greater are not changed
For example
flip([3, 1, 4, 5, 2], 2) => [4, 1, 3, 5, 2]
flip([3, 1, 4, 5, 2], 0) => [3, 1, 4, 5, 2]
flip([3, 1, 4, 5, 2], 4) => [2, 5, 4, 1, 3]
The pancake sort problem is: take as input an array of elements – assume integers for this assignment,
and return a sequence of flip operations that, when applied to the input array, results in an array that is
in sorted order.
For example
Begin [3, 1, 4, 5, 2]
flip_1 [1, 3, 4, 5, 2]
flip_3 [5, 4, 3, 1, 2]
flip_4 [2, 1, 3, 4, 5]
flip_1 [1, 2, 3, 4, 5]
You will start with the search framework we developed in class. You must use this framework for your
solution. After that you may only add a new
• World state definition class
• Problem definition class
• Evaluation instance (if you implement a heuristic)
You will develop a function solvePancakeSort that takes a list of integers as input, and returns a list
of strings, each one describing a "flip move." In addition your function will return the same stats tuple
returned by aStarSearch. Here is an example of the mapping from input list to output solution.
[3, 1, 4, 5, 2]) => ["flip_1", "flip_3", "flip_4", "flip_1"]
For extra credit, see how much you can improve the performance using heuristics. Look at this paper,
and see whether you can implement its heuristic and how well the heuristic does. I will give up to 5
points extra credit for heuristics that are empirically better than uninformed search (i.e. you have to
demonstrate that your heuristic outperforms DFS and BFS.
Work on a heuristic is worth a maximum of 5 points, but your total score on the assignment cannot
exceed 100 points.
The notebook pancakeSearch.ipynb provides additional detail, and a template for handing in your
work.
Problem 3: Solving the Strimko Puzzle Using Search
Strimko is a number game like Sudoko in that one starts with a game board partially filled with numbers;
to solve the game, numbers are assigned to empty cells. Notice in this example, the board has four
rows, four columns, and four "chains" or "streams," which are connected sequences of cells. The term
"chain" and "stream" are interchangeable – different sources use these two terms to mean the same
thing.
Rows, columns and chains all have the same length (for example 4 for a 4x4 game) and every cell
appears in exactly one chain. To solve the puzzle, assign a number to every cell so that the numbers in
each row, column, and chain are distinct. The left figure is a valid initial board, the right figure is a
solved board. Ignore the R1 and C1 labels to the sides.
You will start with the generic search framework we used in the Search Lab, and build a problem solver
for Strimko using the state-space search implementation.
Here are some requirements about how we will represent the game.
A Strimko problem has two components: the initial board, and the chains.
For a problem of size n, the initial board will be represented by a Python nested list: it will be a list of n
elements, each of which is a list of n elements. Zero will be used to denote empty cells. For the
example above, the initial game board would be represented like this:
[[0,0,0,1], [0,0,2,0], [0,4,0,0], [0,0,0,0]]
The chains will be represented by a list of length n, each element of which is a list of length n of 2-tuples,
each representing a coordinate pair. A coordinate pair is (row, column) and 0-based. The chains for the
example board above would be:
[[(0,0), (1,1), (2,0), (0,2)],
[(1,0), (0,1), (1,2), (0,3)],
[(3,0), (2,1), (3,2), (2,3)],
[(3,1), (2,2), (1,3), (3,3)]]
The order in which coordinates appear in the chains is not significant.
You will develop a function solveStrimko that takes as input two required arguments, an initial board
and chains respectively, and returns a solution game board if one exists, or None otherwise. In addition
your function will return the same stats tuple returned by aStarSearch.
Notice that the A-star search function returns a list of "actions," but your solveStrimko function must
return a game board. You must write the code to convert a list of actions to a game board.
You may assume that the initial board and chains are legal in the sense that the chains and initial
assignment of values obey the rules
Heuristic – Extra Credit
You can receive up to 5 points for this section, but not to exceed 100 points for the assignment.
Develop a heuristic that should guide the A-Star search algorithm to a solution quickly. The point of this
part is just to get you to formulate some heuristic, and implement it within the search framework. The
heuristic can be simple, and it might not work any better than an informed strategy. (Sometimes they
just don't, and that's the way it goes.) Document your solution as follows:
• What is the idea behind your heuristic
• How did you implement it
• How did it run compared to the best uninformed algorithm
The notebook strimko.ipynb provides additional detail, and a template for handing in your work.
Handin Details
Please hand in the following (online Canvas submission)
• A single Zip archive, containing five files. The files are
o search.py, searchAgents.py (for the Pacman problems)
o pancakeSearch.ipynb (for the Strimko problem)
o strimko.ipynb (for the Strimko problem)
o Retrospective.pdf
• Your Retrospective.pdf file must contain the following material
o Your name
o For each of the three questions
▪ Is your solution fully working or not?
▪ Was there anything particularly noteworthy or challenging about the
question
o How much time did you spend on the assignment overall?
o Overall how would you evaluate the homework in terms of understanding and
applying concepts discussed in class