import java.util.*;
class Node {
int no
String name;
Node left, right;
boolean hasleft, hasright;
float Hn;
}
public class Hill {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
LinkedList open = new LinkedList();
LinkedList close = new LinkedList();
LinkedList demo = new LinkedList();
LinkedList track = new LinkedList();
int n, i, k, temp2;
String goal, ch, temp1;
float temp;
System.out.println("Enter number of
nodes:");
n = sc.nextInt();
Node nd[] = new Node[n];
for(i=0, k=0;i<n-1;k++) {
if(i==0) {
nd[i] = new Node();
nd[i].no = i;
System.out.println("Enter ROOT
node");
nd[i].name = sc.next();
System.out.println("Enter
h("+nd[i].name+"): ");
nd[i].Hn = sc.nextFloat();
}
System.out.println(nd[k].name + "
Has Left Child? (y/n)");
ch = sc.next();
if(ch.charAt(0)=='y' || ch.charAt(0)=='Y') {
i++;
nd[i] = new Node();
nd[i].no = i;
System.out.println("Enter
Child nodes:");
nd[i].name = sc.next();
System.out.println("Enter
h("+nd[i].name+"): ");
nd[i].Hn = sc.nextFloat();
nd[k].left = nd[i];
nd[k].hasleft = true;
}
System.out.println(nd[k].name + "
Has Right Child? (y/n)");
ch = sc.next();
if(ch.charAt(0)=='y' || ch.charAt(0)=='Y')
{
i++;
nd[i] = new Node();
nd[i].no = i;
System.out.println("Enter
Child nodes:");
nd[i].name = sc.next();
System.out.println("Enter
h("+nd[i].name+"): ");
nd[i].Hn = sc.nextFloat();
nd[k].right = nd[i];
nd[k].hasright = true;
}
}
System.out.println("Enter Goal
State:");
goal = sc.next();
for(i=0;i<n;i++) {
if(i==0) {
open.add(nd[i].name);
track.add(nd[i].no);
demo.add(nd[i].Hn);
}
System.out.println((i+1)+".\n"+
"OPEN: "+open+"\t\t X = "+open.getFirst()+"\nCLOSE:
"+close);
if(goal.equals(open.getFirst())) {
System.out.println("GOAL STATE
"+open.getFirst()+" found");
break;
}
else {
close.add(open.getFirst());
open.removeFirst();
demo.removeFirst();
int g = (int)track.getFirst();
track.removeFirst();
if(nd[g].hasleft==true &&
nd[g].hasright==true) {
open.add(nd[g].left.name);open.add(nd[g].right.name);
demo.add(nd[g].left.Hn);demo.add(nd[g].right.Hn);
track.add(nd[g].left.no);track.add(nd[g].right.no); int tr[] = new int[track.size()];
float[] array = new float[demo.size()];
String[] arr = new String[open.size()];
for(k=0;k<2;k++) {
array[k] = (float) demo.get(k);
arr[k] = (String) open.get(k);
tr[k] = (int) track.get(k);
}
if(array[0]<array[1]) {
temp = array[0];
temp1 = arr[0];
temp2 = tr[0];
array[0] = array[1];
arr[0] = arr[1];
tr[0] = tr[1];
array[1] = temp;
arr[1] = temp1;
tr[1] = temp2;
}
open.removeFirst();open.removeFirst();
demo.removeFirst();demo.removeFirst();
track.removeFirst();track.removeFirst();
for(k=0;k<2;k++) {
open.add(k, arr[k]);
demo.add(k, array[k]);
track.add(k, tr[k]); }
}
else if(nd[g].hasleft==true && nd[g].hasright==false)
{
open.add(0,
nd[g].left.name);demo.add(0, nd[g].left.Hn);track.add(0, nd[g].left.no);
}
else if(nd[g].hasleft==false &&
nd[g].hasright==true) {
open.add(0,
nd[g].right.name);demo.add(0, nd[g].right.Hn);track.add(0, nd[g].right.no);
}
}
}
if(open.isEmpty()==true) {
System.out.println((i+1)+".\n"+
"OPEN: "+open+"\nCLOSE: "+close);
System.out.println("Goal State not
found");
}
}
}
OUTPUT:
Enter number of nodes:
6
Enter ROOT node
A
Enter h(A):
10
A Has Left Child? (y/n)
y
Enter Child nodes:
B
Enter h(B):
9
A Has Right Child? (y/n)
y
Enter Child nodes:
C
Enter h(C):
11
B Has Left Child? (y/n)
y
Enter Child nodes:
D
Enter h(D):
7
B Has Right Child? (y/n)
y
Enter Child nodes:
E
Enter h(E):
9
C Has Left Child? (y/n)
y
Enter Child nodes:
F
Enter h(F):
5
C Has Right Child? (y/n)
n
Enter Goal State:
E
1.
OPEN: [A] X = A
2.
OPEN: [C, B] X = C
CLOSE: [A]
3.
OPEN: [F, B] X = F
CLOSE: [A, C]
4.
OPEN: [B] X = B
CLOSE: [A, C, F]
5.
OPEN: [E, D] X = E
CLOSE: [A, C, F, B]
GOAL STATE E found
Enter number of
nodes:
3
Enter ROOT node
A
Enter h(A):
10
A Has Left Child?
(y/n)
y
Enter Child
nodes:
B
Enter h(B):
5
A Has Right
Child? (y/n)
y
Enter Child
nodes:
C
Enter h(C):
8
Enter Goal State:
D
1.
OPEN: [A] X = A
CLOSE: []
2.
OPEN: [C, B] X = C
CLOSE: [A]
3.
OPEN: [B] X = B
CLOSE: [A, C]
4.
OPEN: []
CLOSE: [A, C, B]
Goal State not
found
