Any help with this would be greatly appreciated, Im not too sure how to start this, preferably in Python or C++ code, thank you for your time.
For this lab assignment, you are given a starting location and goal location (or destination), and must find a path to the goal location. In this problem, the optimal path is the one which has the shortest travel time. You will be implementing the following four search algorithms: Breadth- First Search (BFS), Depth-First Search (DFS), Uniform Cost Search (UCS), and A* Search. You are required to follow the algorithm definitions/pseudocode which we have covered during lecture (please see the lecture slides on Blackboard). Your program will read an input.txt file. The input.txt file will specify one of the four searching algorithms, as well as starting and goal locations. In addition, the input.txt file will contain live traffic information, which is a list of current traveling times in minutes) between different locations. For example, suppose the starting location is your home and the destination is Staples Center. An example of live traffic data is as follows: Home CA73/Newport Coast Dr 5 CA73/NewportCoast Dr 1405/CA73 10 1405/CA73 1110/1405 25 I110/1405 110/1110 20 110/1110 1110/1405 30 110/1110 110/1405 9 1105/1110 110/1110 7 110/1110 StaplesCenter 3 Here, each line indicates the current traveling time between two locations. For example, line 3 indicates that it takes 25 minutes to go from 1405/CA73 to 1110/1405. Note that the location can be an intersection (such as 1405/CA73). Traveling time may not be the same for both directions. For example, 1110/1405 110/1110 20 indicates that it takes 20 minutes to travel from 1110/1405 to 110/1110, but 110/1110 1110/1405 30 indicates that it takes 30 minutes in the other direction. Beside the live traffic information, you also have an idea of how long it takes on a traffic-free Sunday from each location to your goal location. Hence, the input.txt file will also contain the Sunday traffic estimate of traveling time from each location listed in the file to your destination. For the example above, the Sunday traffic data may look like this: Home 55 CA73/NewportCoast Dr 50 1405/CA73 40 1110/1405 28 110/1110 8 110/1405 39 1105/1110 23 StaplesCenter 0 Your program should write, in an output.txt file, the list of locations traveled over in your solution path (including the starting and goal locations) and the accumulated time from start to each location, in order of travel. The following is an example of output.txt: Home 0 CA73/NewportCoastDr 5 1405/CA73 15 1110/1405 40 110/1110 60 StaplesCenter 63 The full specification of input.txt and output.txt is shown on the next page. Full specification for input.txt:
<... sunday traffic lines ...> where: is the algorithm to use and will be one of the following: "BFS", "DFS", "UCS", "A*". is a string with the name of the start location (e.g., "Home"). is a string with the name of the goal location (e.g., "StaplesCenter"). is the number of lines of live traffic information that follow. <... live traffic lines ...> are lines of live traffic information in the format previously described, i.e., is the number of lines of Sunday traffic estimates that follow. <... sunday traffic lines ...> are lines of Sunday traffic information in the format previously described, i.e., Full specification for output.txt: Any number of lines with the following format for each line: ****Important guidelines on next two pages**** Guidelines (Continued) Guidelines: Your program should not require any command-line argument. It should read a text file called "input.txt" in the current directory that contains a problem definition. It should write a file called "output.txt" in the current directory) with your solution Format for input.txt and output.txt is specified in the previous page. State names (such as "StaplesCenter") will not have any white spaces in them and will consist of any number of the following characters: a-zA-Z0-9./ There will not be any duplicate entries in the live traffic data, There will be exactly one entry in the Sunday traffic data for each state mentioned in the live traffic data. Samples of input and output are shown on the last few pages of this assignment description The goal of the samples is to check that you can correctly parse the problem definitions, and generate a correctly formatted output. Your output should match the specified format exactly Failure to do so will most certainly cost some points. It should not be assumed that if your program works on the samples it will work on all test cases. We will run your program on additional test cases and it is your task to make sure that your program will work correctly on any valid input. You are encouraged to come up with additional test cases and test your program on them. In output.bxt, the first line should always be " 0' and the last line's state should always be (and the total accumulated travel time should follow). Hence, If the start state is the same as the goal state, you should output a single line " 0". The goal state will always be reachable from the start state, so you do not need to worry about cases where no path can be found from start to goal. There are multiple definitions around the web and in various textbooks for the algorithms that you will implement. Different implementations may sometimes give different results. You are required to follow the algorithm definitions/pseudocode which we have covered during lecture (please see the lecture slides on Blackboard). You will be required to submit your source code to a dropbox on Blackboard. For this assignment, your source code should be contained in a single file (in other words, you should submit only one file). Please use the following format for the filename: "labi _.xxx" where "xXx" is the extension for the programming language you used I'py" for python, "cpp" for C++, and "Java" for Java). A couple of additional notes are as follows. If you are using CH11, then the name of your file should be "lab1___v11.cpp" (if you are using the earlier version of C++, then you do not need to include the version number). If you are using Python, then the name of your file should be "abi_cfirst name>__.py, where <... sunday traffic lines ...> where: is the algorithm to use and will be one of the following: "BFS", "DFS", "UCS", "A*". is a string with the name of the start location (e.g., "Home"). is a string with the name of the goal location (e.g., "StaplesCenter"). is the number of lines of live traffic information that follow. <... live traffic lines ...> are lines of live traffic information in the format previously described, i.e., is the number of lines of Sunday traffic estimates that follow. <... sunday traffic lines ...> are lines of Sunday traffic information in the format previously described, i.e., Full specification for output.txt: Any number of lines with the following format for each line: ****Important guidelines on next two pages**** Guidelines (Continued) Guidelines: Your program should not require any command-line argument. It should read a text file called "input.txt" in the current directory that contains a problem definition. It should write a file called "output.txt" in the current directory) with your solution Format for input.txt and output.txt is specified in the previous page. State names (such as "StaplesCenter") will not have any white spaces in them and will consist of any number of the following characters: a-zA-Z0-9./ There will not be any duplicate entries in the live traffic data, There will be exactly one entry in the Sunday traffic data for each state mentioned in the live traffic data. Samples of input and output are shown on the last few pages of this assignment description The goal of the samples is to check that you can correctly parse the problem definitions, and generate a correctly formatted output. Your output should match the specified format exactly Failure to do so will most certainly cost some points. It should not be assumed that if your program works on the samples it will work on all test cases. We will run your program on additional test cases and it is your task to make sure that your program will work correctly on any valid input. You are encouraged to come up with additional test cases and test your program on them. In output.bxt, the first line should always be " 0' and the last line's state should always be (and the total accumulated travel time should follow). Hence, If the start state is the same as the goal state, you should output a single line " 0". The goal state will always be reachable from the start state, so you do not need to worry about cases where no path can be found from start to goal. There are multiple definitions around the web and in various textbooks for the algorithms that you will implement. Different implementations may sometimes give different results. You are required to follow the algorithm definitions/pseudocode which we have covered during lecture (please see the lecture slides on Blackboard). You will be required to submit your source code to a dropbox on Blackboard. For this assignment, your source code should be contained in a single file (in other words, you should submit only one file). Please use the following format for the filename: "labi _.xxx" where "xXx" is the extension for the programming language you used I'py" for python, "cpp" for C++, and "Java" for Java). A couple of additional notes are as follows. If you are using CH11, then the name of your file should be "lab1___v11.cpp" (if you are using the earlier version of C++, then you do not need to include the version number). If you are using Python, then the name of your file should be "abi_cfirst name>__.py, where
