Homework SourseCan you solve this in the simplest way possible with comment
Can you solve this in the simplest way possible with comments for explanation?
Implement a java program that will solve the following travel salesman problem using one of the Informed (HEURISTIC) search Algorithms called \"Greedy best-first search\" Algorithm. In your program suppose the initial state is city \"A\". Start with initial city \"A\" Chose the city with the minimum heuristic value. Print the sequence of cities the travel salesman will visit and the relevant cost for this path.Solution
PROGRAM CODE:
package bestFirstSearch;
import java.util.InputMismatchException;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
public class BestFirstSearch
{
// Instead of A, B, C, D, E ... Im using 1, 2,3,4,5 here to represent the nodes or the cities in this case
private Queue<Node> queue; // Queue structure for storing the nodes
private int heuristicvalues[];// array to store the heuristic values
private int numberOfCities;// total number of nodes(cities)
public int[] cities = new int[5];
public static final int MAX_VALUE = 999;
// setting max value for weights in the weighted matrix - useful when the value for weight matrix is zero (other than where ith and jth cities are same)
// constructor for the class with nodes and queues
public BestFirstSearch(int numCities)
{
this.numberOfCities = numCities;
this.queue = new PriorityQueue<Node>(this.numberOfCities, new Node());
}
//search algorithm
public void bestFirstSearchAlgorithm(int WeightedMatrix[][], int[] heuristicvalues,int source)
{
int evaluationNode; // current city
int destinationNode; // nect city
int visited[] = new int [numberOfCities + 1]; // this holds the values for visited. its either 1 or 0
this.heuristicvalues = heuristicvalues;
int counter = 0; // counter for adding values into the city
// adding the first city with heuristic value into the queue
queue.add(new Node(source, this.heuristicvalues[source]));
visited[source] = 1;
// until queue is empty this loops runs
while (!queue.isEmpty())
{
evaluationNode = getNodeWithMinimumHeuristicValue(); // we are picking the node with min heuristic value
destinationNode = 1;
cities[counter] = evaluationNode; // adding the cities traversed into the array
counter++; //counter for array
while (destinationNode <= numberOfCities) // until the remaining cities are traversed
{
Node Node = new Node(destinationNode,this.heuristicvalues[destinationNode]); // node for the destination city
// checking for three things here
//if the wieght is not > than maxvalue
//whether this city is already visited
//whether the destination is reached
if ((WeightedMatrix[evaluationNode][destinationNode] != MAX_VALUE && evaluationNode != destinationNode)&& visited[destinationNode] == 0)
{
queue.add(Node);// adding node to queue
visited[destinationNode] = 1; // making visited as 1.
}
destinationNode++; // incrementing to move to the next city
}
}
}
// returning the min heuristic value
private int getNodeWithMinimumHeuristicValue()
{
Node Node = queue.remove();
return Node.node;
}
public void DisplayTraversal()
{
for(int i=0; i<cities.length; i++)
{
String city = \"\";
switch(cities[i])
{
case 1: city = \"A\";
break;
case 2: city = \"B\";
break;
case 3: city = \"C\";
break;
case 4: city = \"D\";
break;
case 5: city = \"E\";
break;
}
System.out.println(city + \"\\t\");
}
}
// main function for the class
public static void main(String[] args)
{
// variables - weight matirx, numberofcities, source and heuristic values
int weighted_matrix[][];
int number_of_vertices;
int source = 0;
int heuristicvalues[];
Scanner scan = new Scanner(System.in);
try
{
System.out.println(\"Enter the number of Cities: \");
number_of_vertices = scan.nextInt();
weighted_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];
heuristicvalues = new int[number_of_vertices + 1];
System.out.println(\"Enter the Weighted Matrix for the graph: \");
for (int i = 1; i <= number_of_vertices; i++)
{
for (int j = 1; j <= number_of_vertices; j++)
{
weighted_matrix[i][j] = scan.nextInt();
if (i == j)
{
weighted_matrix[i][j] = 0;
continue;
}
if (weighted_matrix[i][j] == 0)
{
weighted_matrix[i][j] = MAX_VALUE;
}
}
}
//setting weight as one wherever weight = 1 or 0.
// this makes the calculation easier
for (int i = 1; i <= number_of_vertices; i++)
{
for (int j = 1; j <= number_of_vertices; j++)
{
if (weighted_matrix[i][j] == 1 && weighted_matrix[j][i] == 0)
{
weighted_matrix[j][i] = 1;
}
}
}
System.out.println(\"Enter the heuristic values of the cities: \");
for (int Node = 1; Node <= number_of_vertices; Node++)
{
System.out.print(Node + \".\");
heuristicvalues[Node] = scan.nextInt();
System.out.println();
}
System.out.println(\"Enter the source city: \");
source = scan.nextInt();
System.out.println(\"The cities are travelled in the following manner, \");
BestFirstSearch bestFirstSearch = new BestFirstSearch(number_of_vertices);
bestFirstSearch.bestFirstSearchAlgorithm(weighted_matrix, heuristicvalues,source);
bestFirstSearch.DisplayTraversal();
} catch (InputMismatchException inputMismatch)
{
System.out.println(\"Wrong Input Format\");
}
scan.close();
}
}
package bestFirstSearch;
import java.util.Comparator;
public class Node implements Comparator<Node>
{
public int heuristicvalue;
public int node;
// each city has a heuristic value and the node value in integer.
// instead of using A, B, C, D, E Im using1, 2, 3, 4, 5
public Node(int node, int heuristicvalue)
{
this.heuristicvalue = heuristicvalue;
this.node = node;
}
public Node()
{
}
// overriding compare method to check based on heuristic value
@Override
public int compare(Node node1, Node node2)
{
if (node1.heuristicvalue < node2.heuristicvalue)
return -1;
if (node1.heuristicvalue > node2.heuristicvalue)
return 1;
return 0;
}
@Override
public boolean equals(Object obj)
{
if (obj instanceof Node)
{
Node node = (Node) obj;
if (this.node == node.node)
{
return true;
}
}
return false;
}
}
OUTPUT:
Enter the number of Cities:
5
Enter the Weighted Matrix for the graph:
0 2 2 1 4
2 0 3 2 3
2 3 0 2 4
1 2 2 0 4
4 3 2 4 0
Enter the heuristic values of the cities:
1.10
2.8
3.3
4.1
5.5
Enter the source city:
1
The cities are travelled in the following manner,
A
D
C
E
B
