Assignment代做 | 算法代写 – B351 Programming

Assignment代做 | 算法代写 – 本次代写是涉及A*算法等搜索算法的代写任务

B351 / Q

In this assignment you will work with heuristic admissibility and uninformed and A* search by applying and testing a general search procedure to the traditional 8-puzzle generalized to anyn^2 1 puzzle.

1. You may collaboratewith one partneron this assignment (optional).
2. Your files will be run against Moss to check for plagiarism within the class outside of your partnership.
``````3.If you are working with a partner, each of you have to submit
work with a partner and name said partner.
``````
1. Keep your git updated by pushing your files when youre done (and within the submission period). Extra credit is given for this step.

1.1 What to Submit

Push your code to github when you are done, submit a file named a3.py to the autograder.

2 Background

The 8-puzzle is one of a family of classic sliding tile puzzles dating to the late 1800s and still played today. A puzzle is solved when the numbered tiles are in order from the top left to the bottom right with the blank in the bottom right corner.

A legal move is made by simply moving a tile into the blank space. We will be denoting the blank space with a 0 to make computation simpler. If you want to familiarize yourself with the game, you can here.

3 Programming

3.1 Data Structures

3.1.1 Board

The class Board, implemented in theBoard.pyfile has two attributes:

• matrix- a double subscripted list containing the current puzzle state
• blankPos- a tuple containing the (row, column) position of the blank.

The following are Boards object methods:

1. init (self, matrix): Constructor for the board class. Takes a double- subscripted list as an argument.
2. str (self ): The string representation of a board.
3. eq (self, other): Checks two boards for equality.
``````4.duplicate(self ): Creates a copy of given board.
``````
``````5.findelement(self, elem): Returns a tuple (row, col) that gives the
position of the element in the board.
``````
``````6.slideblank(self, move): Function for sliding the blank space around.
Takes a tuple (Delta x, Delta y) that represents how far you want to move
in each direction.
``````
1. hash (self ): Hash function that maps a board to a number.

3.1.2 State

This class is implemented in the State.py file. This class encapsulates the fol- lowing data members:

• board- The board that belongs to this state.
• parent- The parent state that this state came from.
• fValue- The heuristic value of the board and the cost to get from the initial board to this board.
• depth- The depth in the move tree from the original board that this board can be found in (the number of moves the puzzle has undergone thus far).
1. init (self, board, parent, fValue, depth): Constructor for a State object. This function takes as arguments the board that corresponds to this state, the parent state, the fValue of the state, and the depth of the state in the state tree.
2. eq (self, other): Checks if two states are equivalent.
3. lt (self, other): Checks if a states fValue is less than that of another state.
4. str (self ): The string representation of a given state.
5. bool (self ): Establishes the fact that the boolean value of a state should be considered True.
``````6.printPath(self ): Prints the path to the given state.
``````
1. hash (self ): A hash function mapping the given state to a real number.

3.1.3 a3.py

This is the main file in which you will be writing code. The following is a list of functions that are provided for you:

``````Already Completed Functions
``````
• uninformedsolver(board, limit, goalboard, mode) Looping function that calls either depth-first search or breadth-first search until a goal state has been found or until the limit has been reached. – boardThe starting board. – limitThe maximum times the function is allowed to check if a state contains the goal board,NOTthe maximum depth of the state tree. – goalboardThe solved board. – modeIf True, the function uses breadth-first search (BFS) to expand the fringe, otherwise it uses depth-first search (DFS).
• findManhattanDist(currentboard, goalboard)
• currentboardThe board for which we are calculating a heuristic value
• goalboardThe solved board.
``````Example heuristic function that we have provided you with so that you
can test the other functions you have to implement.
``````
• informedsearches(fringe, limit, goalboard, explored, mode)
• fringeList of states that are in the fringe. States that have not yet been explored.
• limitThe limit on how many times the function check if a state is the goal state.
• goalboardThe solved board.
• exploredThe set of states that have already been explored.
• modeIf True A* is used to expand the fringe and uniform cost search is used otherwise.
• informedsolver(currentboard, limit, goalboard, mode)
• currentboardThe starting board.
• limitThe limit on how many times the function check if a state is the goal state.
• goalboardThe solved board.
• modeIf True A* is used to expand the fringe and uniform cost search is used otherwise.
3.2 Objective

Your goal is to provide implementations to the following functions:

1. fringeexpansion
3. depthfirstsearch
4. ucsexpansion
5. astarexpansion
6. myownheuristic

to the following specifications:

The following functions have to do with uninformed search.

3.2.1 fringeexpansion(currentstate, fringe, goalboard)

Add all possible successive children states of the currentstate to the end of the fringe.

• currentstateThe current state that is to be used to generate children to add to the end of the fringe.
• fringeA list that holds the states that have been added to the fringe.
• goalboardThe solved board.

TO DO: Write code that adds new game States to the end of the fringe.

Explore the fringe using BFS.

• fringe- The list of states that are in the fringe.
• limit- The limit on how many times the function check if a state is the goal state.
• goalboard- The solved board.
TO DO:

Implement breadth-first search to expand the fringe. This function should re- turn the current state if the goal board is found, True if the limit is reached, and it should expand the fringe otherwise.

3.2.3 depthfirstsearch(fringe, limit, goalboard, visited)

Implement the visited call to ignore the visited States. NOTE:There is the possibility that DFS may never find the goal.

• fringe- List of states that are in the fringe. States that have not yet been explored.
• limit- The limit on how many times the function check if a state is the goal state.
• goalboard- The solved board.
• visited- A list that keeps track of what states have already been vis- ited/expanded.

TO DO: This function should grab a state from the fringe and see if it has been visited before, skipping it if so. It should then return the current state if it is equal to the goal board, True if the limit has been reached and it should expand the fringe otherwise.

``````The following functions have to do with informed search.
``````

3.2.4 ucsexpansion(currentstate, fringe, goalboard, explored)

Uniform-cost expansion function.

• currentstateThe current state that we are looking at.
• fringeThe states that havent been explored yet.
• goalboardThe solved board.
• exploredThe set of states that have already been explored.

TO DO: Implement the uniform-cost search algorithm. You should first generate the possible children states of the current state. Add the current state to the set of states that have already been explored and then check if any of the children have already been explored. If a state has already been explored it should be ignored. Then you need to check if each of the child states is in the fringe, adjusting its position according to UCS. Then, all children that are not already in the fringe should be added to it.

3.2.5 astarexpansion(currentstate, fringe, goalboard, explored)

A* expansion function.

• currentstateThe current state that we are looking at.
• fringeThe states that havent been explored yet.
• goalboardThe solved board.
• exploredThe set of states that have already been explored.

TO DO: Implement the A* search algorithm. You should first generate the children states of the current state, being sure to calculate the heuristic value corresponding to each state. Then, you need to check if each of the child states already exists in the fringe, and if so, handle the conflict based on the overall heuristic value of that state. Finally, you need to check if each of the child states exists in the set of explored states. If it does, you either remove it from the set of explored states and add it back to the fringe or leave it alone. Of course at the end, all valid child states should be added to the fringe.

3.2.6 myownheuristic(currentboard, goalboard)

Create your own heuristic function that is to be used with the A* search algo- rithm.

• currentboardThe board for which a heuristic value needs to be calcu- lated.
• goalboardThe solved board.

TO DO: Implement this function. For testing purposes, in the heuristic() method, replace findManhattanDist() with your heuristic. It should pass the same tests for A*.

• fringeexpansion()- 10%
• depthfirstsearch()- 15%
• ucsexpansion()- 20%
• astarexpansion()- 30%
• myownheuristic()- 10%

5 Bonus

Implement IDS with the following parameters:

5.0.1 idssolver(board, limit, goalboard)

Similar to uninformedsolver()

• boardThe starting board.
• limitThe maximum times the function is allowed to check if a state contains the goal board,NOTthe maximum depth of the state tree.
• goalboardThe solved board.

5.0.2 ids(fringe, limit, goalboard, horizon)

• fringe- List of states that are in the fringe. States that have not yet been explored.
• limit- The limit on how many times the function check if a state is the goal state.
• goalboard- The solved board.
• horizon- The depth of the search.