Algorithms讲解、C++程序设计调试、program辅导、讲解c/c++语言
- 首页 >> Database The 8-Puzzle: Search Algorithms
Maximum number of members per group: 3 students
Deadline for submission: 15th of April
Instructions
Your task is to write a C++ program that will solve the 8-puzzle problem using a selection of search algorithms, and their variants.
The successors of a state are to be generated in a FIXED order, namely move the blank tile: Down, Right, Up, then Left.
Words of caution: Note that if you are using a stack data structure (last in, first out) as a container for the Search Nodes, then you will have to push into the stack the Left successor first, followed by the Up, Right, then Down successors so that the Down successor would be the first to be popped out of the stack.
An AnimateSolution() function has been provided that you can use to animate the sequence of moves (i.e. path) calculated by the algorithms. A start-up program (compiles with gcc 9.2) with a graphics library and 2 batch files for generating experiment results are available for downloading from stream.
It is up to you to write any functions, classes or data structures that you may require. However, for each of the algorithm, there is a specific minimum STL data structure that is required. You can use cout statements to trace the algorithms’ execution.
For each implementation of the algorithms below, include codes that will capture the following information during the algorithm’s execution.
a.Max. Q length – e.g. 26
b.Path length - the number of moves to solve the puzzle, e.g. 30
c.Number of state expansions – e.g. 157
d.Actual running time in seconds (use the clock() function as shown in the start-up codes)
Write your algorithm implementations inside the skeleton functions provided for the required algorithms. Do not change the names and input parameters of these skeleton functions as the batch files would refer to them. Each algorithm implementation should return the sequence of moves as a string. Moreover, make sure that your program runs with the supplied batch files for generating the tabulated experiment results. Your assignments will be marked using them.
e.g. string bestFirstSearch_with_VisitedList(string const initialState, string const goalState,
int &numOfStateExpansions, int& maxQLength, float &actualRunningTime)
oNote that the function uses pass by reference to copy the statistical results back to the calling function
Par1t 1: Progressive Deepening Search (PDS)
Use the following Search Node pushing sequence (for a Stack data structure): Left, Up, Right, Down. Effectively, search nodes will be popped out in the following order: Down, Right, Up, Left.
a)PDS with the Visited List – in your implementation, add a facility that checks and avoids local loops
b)PDS with the Non-Strict Visited List
Part 2: Best First Search
Use the following search node pushing sequence (for a Heap data structure): Down, Right, Up, Left.
Implement the Q container using the priority_queue or heap data structure available in the C++ Standard Template Library (STL).
a)Best First Search without the Visited List - in your implementation, add a facility that checks and avoids local loops
b)Best First Search with the Visited List (but not local loop avoidance, as it is not needed)
Part 3: A* Search with the Strict Expanded List
Use the following search node pushing sequence (for a Heap data structure): Down, Right, Up, Left
Implement the Q container using the priority_queue or heap data structure available in the C++ Standard Template Library (STL).
a)Using the Misplaced Tiles heuristic
b)Using the Sum of Manhattan Distance heuristic
Part 4: Experiments
Test your implementation of the different algorithms by performing experiments using the 5 given (start, goal) state combinations below. Run your program until it either returns a solution, the Q becomes empty (no solution), the computer runs out of memory, or until the program crashes. Use the batch files provided to run all the experiments and collect the results easily.
Tabulate the experiment results in an Excel worksheet (convert the output of the batch file into a worksheet). Please check if the format of your tabulation of results matches the template provided (see template.xlsx). Use your surname_forename.xlsx as the name of your Excel file, and assign the name “results” to the sheet name containing the experiment results. For a group submission, just use one of the member’s name.
If there is no solution found for a given (start, goal states), simply leave that section blank in the table, or write 0 in each of the required statistical measure (e.g. path length, no. of state expansions, max q length, running time, etc.).
Specify under the “comments” section of the tabulation of results if any of the following was observed for a given (start, goal state) combination:
the program ran out of memory
program crashed without any warning
the Q turned empty; thus, allowing the program to close properly
BONUS
1 Bonus mark will be given to an original implementation and correct usage of a hash function, to speed up search. The hash value returned must be of numeric type, and there should be an evidence of search speed increase.
(Start, Goal) State Combinations
Note: 0 - blank space
Run the different algorithms on the following START STATES:
1.608435127
2.743286051
3.647850321
4.185024367
5.867254301
Hints:
You can step through the search by including a getch() function (made available via the graphics engine provided in the start-up codes) inside your main loop to pause the program until the user presses any key.
Example Sequence:
Sequence of states and operations.
You may choose to represent states in an array, of size 9. You can represent operations with the 'u' 'd' 'l' 'r' characters.
In notation, the sequence s to get to the goal from the initial state could be represented as:
s = {d,r,u,u,l,d} You may find it helpful to cout something similar to help debug your program.
Criteria for Marking:
Make sure that your program compiles using gcc 9.2 before handing it in.
Make sure that you submit a tabulation of all the experiment results, following the Template.xlsx format that comes with the start-up codes package. This will be used to accurately analyse your implementation of the algorithms and mark your assignment. You will lose 50% of your grade if you fail to submit this file.
You can work in a group (max. 3 members) for this assignment.
Copied work will be given zero marks.
Each algorithm implementation will be assessed based on its performance on the given (start/goal) state combinations.
For each (start, goal) state combination, the following statistical measures will be used in computing the assignment marks:
1.path length (60% of marks)
2.number of state expansions (20% of marks)
3.max Q length (20% of marks)
Checklist/Other technical details
Please accomplish the following check list in order to allow for accurate marking of your assignment.
Item your assignment details Comments
1 Names and ID numbers of Group Members (maximum of 3 members in a group)
2 Operating System used for testing your codes Note: your codes must be tested on Windows 10. The graphics engine only works on Windows.
3 Compiler used Note: gcc 9.2 is required
4 IDE used (e.g. SublimeText 3, ScITE)
5 Complete source codes (cpp, h files), makefile PDS_VList full/partial Indicate ‘full’, if you have completed the implementation of an algorithm, or ‘partial’, if you are only submitting a partial implementation.
PDS_Non_Strict_VList full/partial
Best_First_No_VList full/partial
Best_First_VList full/partial
AStar_ExpList_Manhattan full/partial
AStar_ExpList_MisplacedTiles full/partial
6 Is your program able to run with the 2 batch files provided? Yes/No indicate ‘Yes’ or ‘No’ (batch files: run_all.bat, run_one.bat)
7 Experiment Results in Excel Worksheet Yes/No
(Note: Use your surname_forename.xlsx as the name of your Excel file. The name of the worksheet must be changed to results.) indicate ‘Yes’ or ‘No’
you will lose 50% of your grade if you fail to submit this Excel file
8 Extra work (Bonus): Enhancements/Optimisations included Yes/No. (If Yes, list down all enhancements you have added.) original implementation and correct usage of a hash function, to speed up search. The hash value returned must be of numeric type, and there should be an evidence of search speed increase
Nothing follows.
Maximum number of members per group: 3 students
Deadline for submission: 15th of April
Instructions
Your task is to write a C++ program that will solve the 8-puzzle problem using a selection of search algorithms, and their variants.
The successors of a state are to be generated in a FIXED order, namely move the blank tile: Down, Right, Up, then Left.
Words of caution: Note that if you are using a stack data structure (last in, first out) as a container for the Search Nodes, then you will have to push into the stack the Left successor first, followed by the Up, Right, then Down successors so that the Down successor would be the first to be popped out of the stack.
An AnimateSolution() function has been provided that you can use to animate the sequence of moves (i.e. path) calculated by the algorithms. A start-up program (compiles with gcc 9.2) with a graphics library and 2 batch files for generating experiment results are available for downloading from stream.
It is up to you to write any functions, classes or data structures that you may require. However, for each of the algorithm, there is a specific minimum STL data structure that is required. You can use cout statements to trace the algorithms’ execution.
For each implementation of the algorithms below, include codes that will capture the following information during the algorithm’s execution.
a.Max. Q length – e.g. 26
b.Path length - the number of moves to solve the puzzle, e.g. 30
c.Number of state expansions – e.g. 157
d.Actual running time in seconds (use the clock() function as shown in the start-up codes)
Write your algorithm implementations inside the skeleton functions provided for the required algorithms. Do not change the names and input parameters of these skeleton functions as the batch files would refer to them. Each algorithm implementation should return the sequence of moves as a string. Moreover, make sure that your program runs with the supplied batch files for generating the tabulated experiment results. Your assignments will be marked using them.
e.g. string bestFirstSearch_with_VisitedList(string const initialState, string const goalState,
int &numOfStateExpansions, int& maxQLength, float &actualRunningTime)
oNote that the function uses pass by reference to copy the statistical results back to the calling function
Par1t 1: Progressive Deepening Search (PDS)
Use the following Search Node pushing sequence (for a Stack data structure): Left, Up, Right, Down. Effectively, search nodes will be popped out in the following order: Down, Right, Up, Left.
a)PDS with the Visited List – in your implementation, add a facility that checks and avoids local loops
b)PDS with the Non-Strict Visited List
Part 2: Best First Search
Use the following search node pushing sequence (for a Heap data structure): Down, Right, Up, Left.
Implement the Q container using the priority_queue or heap data structure available in the C++ Standard Template Library (STL).
a)Best First Search without the Visited List - in your implementation, add a facility that checks and avoids local loops
b)Best First Search with the Visited List (but not local loop avoidance, as it is not needed)
Part 3: A* Search with the Strict Expanded List
Use the following search node pushing sequence (for a Heap data structure): Down, Right, Up, Left
Implement the Q container using the priority_queue or heap data structure available in the C++ Standard Template Library (STL).
a)Using the Misplaced Tiles heuristic
b)Using the Sum of Manhattan Distance heuristic
Part 4: Experiments
Test your implementation of the different algorithms by performing experiments using the 5 given (start, goal) state combinations below. Run your program until it either returns a solution, the Q becomes empty (no solution), the computer runs out of memory, or until the program crashes. Use the batch files provided to run all the experiments and collect the results easily.
Tabulate the experiment results in an Excel worksheet (convert the output of the batch file into a worksheet). Please check if the format of your tabulation of results matches the template provided (see template.xlsx). Use your surname_forename.xlsx as the name of your Excel file, and assign the name “results” to the sheet name containing the experiment results. For a group submission, just use one of the member’s name.
If there is no solution found for a given (start, goal states), simply leave that section blank in the table, or write 0 in each of the required statistical measure (e.g. path length, no. of state expansions, max q length, running time, etc.).
Specify under the “comments” section of the tabulation of results if any of the following was observed for a given (start, goal state) combination:
the program ran out of memory
program crashed without any warning
the Q turned empty; thus, allowing the program to close properly
BONUS
1 Bonus mark will be given to an original implementation and correct usage of a hash function, to speed up search. The hash value returned must be of numeric type, and there should be an evidence of search speed increase.
(Start, Goal) State Combinations
Note: 0 - blank space
Run the different algorithms on the following START STATES:
1.608435127
2.743286051
3.647850321
4.185024367
5.867254301
Hints:
You can step through the search by including a getch() function (made available via the graphics engine provided in the start-up codes) inside your main loop to pause the program until the user presses any key.
Example Sequence:
Sequence of states and operations.
You may choose to represent states in an array, of size 9. You can represent operations with the 'u' 'd' 'l' 'r' characters.
In notation, the sequence s to get to the goal from the initial state could be represented as:
s = {d,r,u,u,l,d} You may find it helpful to cout something similar to help debug your program.
Criteria for Marking:
Make sure that your program compiles using gcc 9.2 before handing it in.
Make sure that you submit a tabulation of all the experiment results, following the Template.xlsx format that comes with the start-up codes package. This will be used to accurately analyse your implementation of the algorithms and mark your assignment. You will lose 50% of your grade if you fail to submit this file.
You can work in a group (max. 3 members) for this assignment.
Copied work will be given zero marks.
Each algorithm implementation will be assessed based on its performance on the given (start/goal) state combinations.
For each (start, goal) state combination, the following statistical measures will be used in computing the assignment marks:
1.path length (60% of marks)
2.number of state expansions (20% of marks)
3.max Q length (20% of marks)
Checklist/Other technical details
Please accomplish the following check list in order to allow for accurate marking of your assignment.
Item your assignment details Comments
1 Names and ID numbers of Group Members (maximum of 3 members in a group)
2 Operating System used for testing your codes Note: your codes must be tested on Windows 10. The graphics engine only works on Windows.
3 Compiler used Note: gcc 9.2 is required
4 IDE used (e.g. SublimeText 3, ScITE)
5 Complete source codes (cpp, h files), makefile PDS_VList full/partial Indicate ‘full’, if you have completed the implementation of an algorithm, or ‘partial’, if you are only submitting a partial implementation.
PDS_Non_Strict_VList full/partial
Best_First_No_VList full/partial
Best_First_VList full/partial
AStar_ExpList_Manhattan full/partial
AStar_ExpList_MisplacedTiles full/partial
6 Is your program able to run with the 2 batch files provided? Yes/No indicate ‘Yes’ or ‘No’ (batch files: run_all.bat, run_one.bat)
7 Experiment Results in Excel Worksheet Yes/No
(Note: Use your surname_forename.xlsx as the name of your Excel file. The name of the worksheet must be changed to results.) indicate ‘Yes’ or ‘No’
you will lose 50% of your grade if you fail to submit this Excel file
8 Extra work (Bonus): Enhancements/Optimisations included Yes/No. (If Yes, list down all enhancements you have added.) original implementation and correct usage of a hash function, to speed up search. The hash value returned must be of numeric type, and there should be an evidence of search speed increase
Nothing follows.