Determining shortest path

Question

Assignment:

State Space Search

 

Consider a network consisting of 20 nodes (labeled 1 through 20). The x and y coordinates of the nodes are presented below:

 

 

node	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
x-coord	2	45	8	85	69	62	80	90	65	81	1	32	43	38	89	97	12	18	11	91
y-coord	42	37	86	85	48	9	57	59	41	91	9	24	19	48	51	9	74	17	70	12

 

 

The following table presents the cost per unit distance of going directly from node i to node j. Note that the cost per unit distance of going from node i to node j is not necessarily the same as that for going from node j to node i.  For example, the cost/distance of going from node 1 to node 2 is 0.5 while the cost/distance of going from node 2 to node 1 is 0.2.

 

 

Cost/distance	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
1	0.0	0.5	0.1	0.7	0.4	0.5	0.3	0.8	0.9	0.3	0.2	0.7	0.9	0.9	0.2	1.0	0.8	0.1	0.3	0.2
2	0.2	0.0	0.3	0.1	0.1	0.8	0.9	0.1	0.1	0.5	0.9	0.8	0.6	0.3	0.1	0.1	0.5	0.3	0.4	0.6
3	0.5	0.1	0.0	0.3	0.1	0.7	0.5	0.1	0.3	0.9	0.3	0.9	0.1	0.8	0.8	0.2	0.5	0.1	0.8	0.3
4	0.6	0.2	0.6	0.0	0.1	0.3	0.9	0.9	0.1	0.8	0.1	0.1	0.2	0.4	0.8	0.2	0.7	0.7	0.6	0.1
5	0.9	0.9	1.0	0.5	0.0	0.8	0.6	0.8	0.4	0.2	0.8	0.6	1.0	0.3	0.6	0.2	0.4	0.9	0.1	0.2
6	0.7	0.2	0.5	0.1	0.9	0.0	0.1	0.7	0.4	0.6	0.8	0.7	0.4	0.6	0.3	0.3	0.1	1.0	0.3	0.8
7	0.1	0.2	0.1	0.2	0.9	0.7	0.0	0.9	0.3	0.7	1.0	0.1	0.8	0.1	0.2	0.2	0.8	0.3	0.2	0.7
8	0.1	0.5	0.8	0.1	0.9	0.9	0.5	0.0	0.9	0.2	0.9	0.1	0.7	0.6	0.4	1.0	0.8	0.4	0.5	0.8
9	0.2	0.9	0.9	0.4	0.3	0.5	0.2	0.9	0.0	0.8	0.8	0.3	0.7	0.3	0.7	0.4	0.7	0.5	0.3	0.4
10	0.2	0.2	0.9	0.9	0.7	0.4	0.1	0.6	0.9	0.0	1.0	0.4	0.1	0.4	0.8	0.5	0.8	0.1	0.8	0.2
11	0.7	0.9	0.6	0.9	0.5	0.9	0.7	0.4	0.2	0.2	0.0	0.6	0.2	1.0	0.9	1.0	0.7	0.1	0.5	0.7
12	0.7	0.8	0.1	0.4	0.9	0.5	0.9	0.8	0.6	1.0	0.8	0.0	0.8	0.9	0.9	0.9	0.7	0.6	0.1	0.9
13	0.8	0.8	0.5	0.4	0.2	0.4	0.4	0.1	0.3	0.9	0.8	0.5	0.0	0.5	0.8	0.9	0.8	1.0	0.1	0.4
14	0.7	0.8	0.3	0.8	0.4	0.7	0.5	0.6	0.9	0.4	0.7	0.2	0.4	0.0	0.3	0.2	0.9	0.5	0.8	0.2
15	0.5	0.3	0.4	1.0	0.1	0.7	0.3	0.2	0.1	0.3	0.4	0.2	0.6	0.1	0.0	0.2	0.3	0.7	0.4	0.9
16	0.5	0.3	0.6	0.6	0.8	0.2	0.6	0.3	0.8	0.2	0.3	0.8	0.3	0.5	0.1	0.0	0.5	0.5	0.3	0.9
17	0.1	0.2	0.3	0.8	0.5	0.2	0.8	0.7	0.8	0.7	0.2	0.5	0.6	0.4	0.5	0.9	0.0	0.9	0.1	0.8
18	0.8	0.6	0.1	0.7	0.8	0.1	0.9	0.5	0.2	0.1	0.6	0.9	0.5	0.3	0.8	0.7	0.5	0.0	0.2	0.7
19	0.2	0.3	0.7	0.9	0.8	0.1	0.3	0.2	0.3	0.1	0.9	0.4	0.8	0.7	0.4	0.8	0.4	0.5	0.0	0.5
20	0.2	0.5	0.9	0.3	0.1	0.5	0.3	0.2	1.0	0.3	0.8	0.6	0.7	0.3	0.3	0.5	0.5	0.4	0.5	0.0

 

 

The cost of going directly from node i to node j is given by:

 

[distance between i and j] ´ [cost per unit distance for going from i to j].

 

For example the cost of going directly from node 1 to node 2 is approximately 21.645 since the distance between node 1 and node 2 is 43.2897 and the cost per unit distance is 0.5.

 

 

An agent can move between nodes and can visit each node 0 or more times. The agent is currently stationed at node 16. It has to visit both, node 3 and node 11 (it does not matter whether node 11 is visited before or after node 3) and has to return to node 16. Find the minimum cost at which the agent can achieve this goal. In your answer specify the minimum cost achievable and the sequence of nodes visited. Note that the agent should start and end at node 16. Justify that this tour is the lowest cost tour from node 16 that includes both node 3 and node 11.

 

 

You need to write a program to implement one of the state search algorithms to find the answer.

Provide complete and step by step solution for the question and show calculations and use formulas.