Instructions Write a program that implements the A* algorithm to find a path fro
ID: 3857890 • Letter: I
Question
Instructions
Write a program that implements the A* algorithm to find a path from any two given nodes. Use Java.
Problem Overview & Algorithm Description
In a fully-observable environment where there are both pathable and blocked nodes, an agent must find a good path from their starting node to the goal node. The agent must use the A* algorithm to determine its path. For this program, you must use the Manhattan method for calculating the heuristic.
Remember: your heuristic function is a representation of how good or close you are to the goal state.
Program Requirements
No graphics are required for this program. Your environment should be a 15x15 tile-based world that randomly generates nodes that are unpathable (blocks) in 10% of the nodes. This should be done each time the program compiles ensuring that there are different environment makeups each run. The program should display the generated environment when the program runs, and should allow the user to select a starting node and goal node. This can be done via text input into the console or with a GUI. Once the start and goal nodes have been defined, the program should run the A* algorithm to find a path. The path should be displayed (series of [x,y] nodes, highlighting nodes, or actually moving the agent) if one exists, or a message indicating that a path could not be found. The user should be able to continue specifying starting and goal nodes after paths have been found.
You are also to use this node class for the program:
public class Node {
private int row, col, f, g, h, type;
private Node parent;
public Node(int r, int c, int t){
row = r;
col = c;
type = t;
parent = null;
//type 0 is traverseable, 1 is not
}
//mutator methods to set values
public void setF(){
f = g + h;
}
public void setG(int value){
g = value;
}
public void setH(int value){
h = value;
}
public void setParent(Node n){
parent = n;
}
//accessor methods to get values
public int getF(){
return f;
}
public int getG(){
return g;
}
public int getH(){
return h;
}
public Node getParent(){
return parent;
}
public int getRow(){
return row;
}
public int getCol(){
return col;
}
public boolean equals(Object in){
//typecast to Node
Node n = (Node) in;
return row == n.getRow() && col == n.getCol();
}
public String toString(){
return "Node: " + row + "_" + col;
}
}
Explanation / Answer
Hi Team,
please have look on the beow code and run
/This is a sample program to find the minimum wire length between two component in a electrical circuits
import java.util.*;
class Node
{
public int label; // this node's label (parent node in path tree)
public int weight; // weight of edge to this node (distance to start)
public Node(int v, int w)
{
label = v;
weight = w;
}
}
public class ShortestPath
{
public static Scanner in; // for standard input
public static int n, m; // n = #vertices, m = #edges
public static LinkedList[] graph; // adjacency list representation
public static int start, end; // start and end points for shortest path
public static void main(String[] args)
{
in = new Scanner(System.in);
// Input the graph:
System.out
.println("Enter the number of components and wires in a circuit:");
n = in.nextInt();
m = in.nextInt();
// Initialize adjacency list structure to empty lists:
graph = new LinkedList[n];
for (int i = 0; i < n; i++)
graph[i] = new LinkedList();
// Add each edge twice, once for each endpoint:
System.out
.println("Mention the wire between components and its length:");
for (int i = 0; i < m; i++)
{
int v1 = in.nextInt();
int v2 = in.nextInt();
int w = in.nextInt();
graph[v1].add(new Node(v2, w));
graph[v2].add(new Node(v1, w));
}
// Input starting and ending vertices:
System.out
.println("Enter the start and end for which length is to be minimized: ");
start = in.nextInt();
end = in.nextInt();
// FOR DEBUGGING ONLY:
displayGraph();
// Print shortest path from start to end:
shortest();
}
public static void shortest()
{
boolean[] done = new boolean[n];
Node[] table = new Node[n];
for (int i = 0; i < n; i++)
table[i] = new Node(-1, Integer.MAX_VALUE);
table[start].weight = 0;
for (int count = 0; count < n; count++)
{
int min = Integer.MAX_VALUE;
int minNode = -1;
for (int i = 0; i < n; i++)
if (!done[i] && table[i].weight < min)
{
min = table[i].weight;
minNode = i;
}
done[minNode] = true;
ListIterator iter = graph[minNode].listIterator();
while (iter.hasNext())
{
Node nd = (Node) iter.next();
int v = nd.label;
int w = nd.weight;
if (!done[v] && table[minNode].weight + w < table[v].weight)
{
table[v].weight = table[minNode].weight + w;
table[v].label = minNode;
}
}
}
for (int i = 0; i < n; i++)
{
if (table[i].weight < Integer.MAX_VALUE)
{
System.out.print("Wire from " + i + " to " + start
+ " with length " + table[i].weight + ": ");
int next = table[i].label;
while (next >= 0)
{
System.out.print(next + " ");
next = table[next].label;
}
System.out.println();
} else
System.out.println("No wire from " + i + " to " + start);
}
}
public static void displayGraph()
{
for (int i = 0; i < n; i++)
{
System.out.print(i + ": ");
ListIterator nbrs = graph[i].listIterator(0);
while (nbrs.hasNext())
{
Node nd = (Node) nbrs.next();
System.out.print(nd.label + "(" + nd.weight + ") ");
}
System.out.println();
}
}
}