人工智能代写: COMP-3703 Homework #1: State Space Implementaon

Homework #1: State Space Implementaon

Submit Assignment

Due Apr 2 by 11:59pm Points 100 Submitting a file upload

In this assignment you will implement the 3×5 sliding tile puzzle state space.

This homework is to be completed individually (4703) or in groups of up to two people (3703). You can discuss the assignment with other students in thinking about how to solve these problems, but all programming and other portions of the assignment must be entirely your own work. You may not show your code to other students. If you are working with another student, you need to designate this by forming a group in Canvas.

The assignment can be implemented in any language, but sample code will be provided in C++. Your assignment should be uploaded to Canvas before the deadline.

Implement your code as follows:

1. Implement a simple data structure to store/represent a single state.

1. States should either be initialized to the goal state, or should be constructed as a copy of an existing

   state.

2. The goal state has the tiles sorted from 0…14, where the 0 tile is the blank.
3. Implement an equality operator to test if two states are equal.
4. Store the current location of the blank tile in the state to make state space operations less expensive.

2. Implement a simple data structure (or enum) to represent an operator. 3. Implement a class/methods to operate on states, providing:

1. a successor function
2. an operator function
3. functions for applying and undoing operators

Your environment might look something like this:

 class STP {
 public:

     void GetSuccessors(STPState &nodeID, std::vector<STPState> &actions);
     void GetOperators(STPState &nodeID, std::vector<STPSlideDir> &operators);
     void ApplyOperator(STPState &s, STPSlideDir o);
     void UndoOperator(STPState &s, STPSlideDir o);

};

Once your code is implemented, write two versions of the function DoRandomWalk, which takes as input a STP class, a STPState, and a walk distance (n). The function should reset to the goal state, perform n random actions, and then return the resulting state.