Reference no: EM133020967
Problem description:
Consider the graph presented below (fig. 1). Each node represents a single state (or the District of Columbia (DC)). If two states are neighbors, there is an edge between them.
Figure 1: A graph representing all 48 contiguous US states and District of Columbia.
Assume that edge weights represent driving distances between state capitals.
Your task is to implement in Python two informed search algorithms:
• Greedy Best First Search algorithm, and
• A* algorithm,
and apply them to find a path between two state capitals using provided data.
Your program should:
• Accept two (2) command line arguments corresponding to two states / state capitals (initial and goal states) so your code could be executed with
python cs480_P01_AXXXXXXXX.py INITIAL GOAL
where:
• cs480_P01_AXXXXXXXX.py is your python code file name,
• INITIAL is the label/name of the initial state,
• GOAL is the label/name of the initial state.
If the number of arguments provided is NOT two (none, one, or more than two), your program should display the following error message:
ERROR: Not enough or too many input arguments. and exit.
• Load and process both input data files provided (assume that input data files are ALWAYS in the same folder as your code - this is REQUIRED!). Make sure your program is flexible enough to accommodate different input data sets (with a different graph of states and distances). Your submission will be tested using a different set of files!
• Run Greedy Best First Search and A* algorithms searches to find a path between INITIAL and GOAL states and measure execution time (in seconds) for both methods.
• Report results on screen in the following format:
Last Name, First Name, AXXXXXXXX solutiocxn:
Initial state: INITIAL
Goal state: GOAL
Greedy Best First Search:
Solution path: STATE1, STATE2, STATE3, ..., STATEN-1, STATEN
Number of states on a path: X1
Path cost: Y1
Execution time: T1 seconds
A* Search:
Solution path: STATE1, STATE2, STATE3, ..., STATEN-1, STATEN
Number of states on a path: X2
Path cost: Y2
Execution time: T2 seconds
Attachment:- Programming Assignment.rar