Assignment 1: Search Methods
Submission: 11:59pm, 5 April 2019 (Friday, week 6).
This assignment is worth 10% of your final mark. It is an individual assignment; no group work.
Late submissions policy
Late submissions are allowed for up to 3 days late. A penalty of 5% per day late will apply. Assignments more than 3 days late will not be accepted (i.e. will get 0 marks). The day cut-off time is 11:59pm.
Your implementation can be written in Python, Java, C, C++ or MATLAB. The assignment will be tested using the language versions as described in the “How your program will be run” section below, so it is important that your program can be run in the specified versions.
Your assignment must be completed individually using the submission tool PASTA (https://comp3308.it.usyd.edu.au/PASTA). In order to connect to the website, you’ll need to be connected to the university VPN. You can read this page to find out how to connect to the VPN. PASTA will allow you to make as many submissions as you wish, and each submission will provide you with feedback on each of the components of the assignment. You last submission before the assignment deadline will be marked, and the mark displayed on PASTA will be the final mark for your assignment.
1. The 3-digit puzzle
1. Write a program to find a solution of the puzzle using the following 6 search strategies: BFS, DFS, IDS, Greedy, A* and Hill-climbing. Use the Manhattan heuristic as a heuristic for A* and Greedy and also as the evaluation function in Hill-climbing.The Manhattan heuristic for a move between two numbers A and B is the sum of the absolute differences of the corresponding digits of these numbers, e.g. ℎ(123, 492) = |1 − 4| + |2 − 9| +|3 − 2| = 11.
2. Avoid cycles. When selecting a node from the fringe for expansion, if it hasn’t been expanded yet, expand it, otherwise discard it. Hint: It is not just the three digits that you need to consider when determining if you have expanded a node before. Two nodes are the same if a) they have the same 3 digits; and b) they have the same ‘child’ nodes.
3. Generate the children in the following order:
a. 1 is subtracted from the first digit
b. 1 is added to the first digit
c. 1 is subtracted from the second digit
d. 1 is added to the second digit
e. 1 is subtracted from the third digit
f. 1 is added to the third digit
Example: the order of the children of node 678 coming from parent 668 is 578, 778, 677, 679. Note that there are no children for the second digit as it already has been changed in the previous move (constraint 3).
4. For the heuristic search strategies: if there are nodes with the same priority for expansion, expand the last added node.
5. Set a limit of 1000 expanded nodes maximum, and when it is reached, stop the search and print a message that the limit has been reached (see section “Input and Output” for the exact message required).
3. Input and Output
As your program will be automatically tested, it is important that you adhere to these strict rules for program input and output.
Your program should be called ThreeDigits, and will be run from the command line with the following arguments:
1. A single letter representing the algorithm to search with, out of B for BFS, D for DFS, I for IDS, G for Greedy, A for A*, H for Hill-climbing.
2. A filename of a file to open for the search details. This file will contain the following:
For example, the file puzzle.txt might contain the following:
This file means that the search algorithm will start at state 345, and the goal is state 555. The search may not pass through any of 355, 445 or 554. Remember that the last line may not be present; i.e. there are no forbidden values.
The following examples show how the program would be run for each of the submission languages, assuming we want to run the A* search algorithm, and the input is in a file called sample.txt.
Note: MATLAB must be run this way (compiled first) to speed up MATLAB running submissions.The arguments are passed to your ThreeDigits function as strings. For example, the example above will be executed as a function call like this:
You program will output two lines only. The first line will contain the solution path found from the start node to the goal node (inclusive), in the form of states separated by commas. If no path can be found with the given parameters, then the first line should be “No solution found.”.
The second line should be the order of nodes expanded during the search process, in the form of states separated by commas. If no path was found, this should still print the list of expanded nodes. Remember that this list should never exceed 1000 states (point 5 in the Tasks section).
This assignment is to be submitted electronically via the PASTA submission system.
Your submission files should be zipped together in a single .zip file and include a main program called ThreeDigits. Valid extensions are .java, .py, .c, .cpp, .cc, and .m. Zip only the submission files, not the folder– when your zip file is unzipped there should be only submission files, not a folder with submission files. Only .zip format is accepted; do not use any other format, e.g. .rar or .7z. If your program contains only a single file, then you can just submit the file without zipping it.
Upload your submission on PASTA under Assignment 1.