CSCI 485 --- Fall 2023

Lab 1

Given the following graph table:

	Value	1	2	3	4
1	'A'	-1	0	5	7
2	'B'	0	-1	3	10
3	'C'	9	2	-1	0
4	'D'	4	8	0	-1

coded in a csv file as:

,value,1,2,3,4
1,A,-1,0,5,7
2,B,0,-1,3,10
3,C,9,2,-1,0
4,D,4,8,0,-1

Where in the 4 by 4 section at the right bottom cornor of the graph, a positive number N means the corresponding nodes are connected with the distance/cost of N, 0 means they are not connected and -1 means that it's unapplicable.

Interpret the above graph as a map of cities. Assume that the node 3 (node 'C') is the start city and node 4 (node 'D') is the destination city, do the following things:

• Give a formal definition of the problem implied by the above graph data;
• Design the interface of the class Problem in order to be used by a search agent later;
• Give a concrete implementation of the Problem class for the problem of finding a path from start city to the destination city.
• (Optional) It would be the best if your Problem class allows user to enter/generate heuristic information for each of its states (assuming the goal state is known).