CPSC5610程序写作、data课程程序辅导、写作Python程序

” CPSC5610程序写作、data课程程序辅导、写作Python程序CPSC5610 Artificial IntelligenceAssignment 1: Problem Solving by State-Space SearchGoals for this assignment1. Understand the components of a search-based problem solver and see severalimplementations2. Apply concepts of state-space search to several different problems3. Understand the power of heuristics applied to state-space search problemsProblem 1: PacMan Search AgentYou will work on the Search Agent problems in the Berkeley AI Pacman projects. The page for thatproblem is here.You will complete questions Q1 through Q7.Problem 2: Pancake SortPancake sort is a sorting algorithm that is especially popular in job interviews because its simple, andmost 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 changedFor exampleflip([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 isin sorted order.For exampleBegin [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]CPSC5610作业写作、data课程作业辅导You will start with the search framework we developed in class. You must use this framework for yoursolution. 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 listof strings, each one Describing a flip move. In addition your function will return the same stats tuplereturned 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 5points extra credit for heuristics that are empirically better than uninformed search (i.e. you have todemonstrate 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 cannotexceed 100 points.The notebook pancakeSearch.ipynb provides additional detail, and a template for handing in yourwork.Problem 3: Solving the Strimko Puzzle Using SearchStrimko 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 fourrows, four columns, and four chains or streams, which are connected sequences of cells. The termchain and stream are interchangeable different sources use these two terms to mean the samething.Rows, columns and chains all have the same length (for example 4 for a 4×4 game) and every cellappears in exactly one chain. To solve the puzzle, assign a number to every cell so that the numbers ineach row, column, and chain are distinct. The left figure is a valid initial board, the right figure is asolved 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 solverfor 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 nelements, each of which is a list of n elements. Zero will be used to denote empty cells. For theexample 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 theexample 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 boardand chains respectively, and returns a solution game board if one exists, or None otherwise. In additionyour 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 mustreturn 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 initialassignment of values Obey the rulesHeuristic Extra CreditYou 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 thispart is just to get you to formulate some heuristic, and implement it within the search framework. Theheuristic can be simple, and it might not work any better than an informed strategy. (Sometimes theyjust dont, and thats 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 algorithmThe notebook strimko.ipynb provides additional detail, and a template for handing in your work.Handin DetailsPlease hand in the following (online Canvas submission) A single Zip archive, containing five files. The files areo 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 materialo Your nameo For each of the three questions Is your solution fully working or not? Was there anything particularly noteworthy or challenging about thequestiono How much time did you spend on the assignment overall?o Overall how Would you evaluate the homework in terms of understanding andapplying concepts discussed in class如有需要，请加QQ：99515681 或邮箱：99515681@qq.com

“