write a C++/Java/Python program for the following assignment: The purpose of thi

Question

write a C++/Java/Python program for the following assignment:

The purpose of this assignment is to implement an algorithm for pathfinding described in the foloowing paper(Tree Adaptive A*):

http://www.ifaamas.org/Proceedings/aamas2011/papers/A1_B44.pdf

ok, so the input format will be an N by N matrix which is actually representing our graph

the starting point is the first vertex and the destination is the last vertex

in the input, the first line give the number of vertices our graph has

the next n lines will be the distance matrix between the vertices of that graph

OUTPUT FORMAT:

the first line in the output will be the minimum path between the starting point and destination

and in the next line, the path for the minimum distance will be printed.

NOTE: the * operand means there is no edge between those two vertices

INPUT EXAMPLE 1:

5
0 2 4 3 *
2 0 * * *
4 * 0 2 3
3 * 2 0 4
* * 3 4 0
OUTPUT FOR EXAMPLE:

8
0 3 2 4

Thanks so much

Explanation / Answer

Below is the java program which is required for you:

import java.util.*;

Output:

Test Case #1
Grid:
SO 0 0 0 BL
0 0 0 0 0   
0 0 BL 0 0   
0 BL DE BL 0   
0 0 0 0 0   


Scores for cells:
0 14 27 41 BL
14 17 29 42 56
27 29 BL 45 59
39 BL 43 BL 0   
52 55 0 0 0   

Path:
[3, 2] -> [2, 1] -> [1, 1] -> [0, 0]


Test Case #2
Grid:
SO 0 0 0 BL
0 0 0 0 0   
0 0 BL 0 0   
0 BL 0 BL 0   
0 0 0 0 DE


Scores for cells:
0 17 33 48 BL
17 20 35 49 62
33 35 BL 52 64
48 BL 52 BL 67
62 65 64 67 77

Path:
[4, 4] -> [3, 4] -> [2, 3] -> [1, 2] -> [1, 1] -> [0, 0]


Test Case #3
Grid:
0 0 0 0 0 0 0   
0 0 0 0 0 0 0   
0 SO 0 BL 0 0 0   
0 0 0 0 0 0 0   
0 BL 0 BL 0 0 0   
0 0 0 BL DE 0 0   
0 0 0 0 0 0 0   


Scores for cells:
40 35 37 40 53 68 0   
22 17 20 34 48 63 0   
17 0 15 BL 48 61 75
20 15 18 31 43 56 70
34 BL 31 BL 46 58 73
48 48 43 BL 56 61 0   
63 61 56 59 0 0 0   

Path:
[5, 4] -> [4, 4] -> [3, 3] -> [3, 2] -> [2, 1]


Test Case #1
Grid:
SO 0 0 0 0   
0 0 0 0 0   
0 0 0 0 0   
0 0 0 BL BL
0 0 0 BL DE


Scores for cells:
0 17 33 48 62
17 20 35 49 62
33 35 38 51 63
48 49 51 BL BL
62 62 63 BL 0   

No possible path

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.