import java.util.*;
class Node {
int no;
String name;
Node left, right;
boolean hasleft, hasright;
float Hn, Gn, Fn;
}
public class BEST {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
LinkedList open = new LinkedList();
LinkedList close = new LinkedList();
LinkedList demo = new LinkedList();
int n, i, k, j, temp2;
String goal, ch;
float temp;
String temp1;
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);
}
else if(nd[g].hasleft==true &&
nd[g].hasright==false) {
open.add(nd[g].left.name);demo.add(nd[g].left.Hn);track.add(nd[g].left.no);
}
else if(nd[g].hasleft==false &&
nd[g].hasright==true) {
open.add(nd[g].right.name);demo.add(nd[g].right.Hn);track.add(nd[g].right.no);
}}
if(open.size()>1 &&track.size()>1
&&demo.size()>1) {
int tr[] = new int[track.size()];
float[] array = new float[demo.size()];
String[] arr = new String[open.size()];
for(k=0;k<demo.size();k++) {
array[k] = (float) demo.get(k);
arr[k] = (String) open.get(k);
tr[k] = (int) track.get(k);
}
for(int z=0;z<array.length;z++) {
for(j=z+1;j<array.length;j++) {
if(array[z]>array[j]) {
temp = array[z];
temp1 = arr[z];
temp2 = tr[z];
array[z] = array[j];
arr[z] = arr[j];
tr[z] = tr[j];
array[j] = temp;
arr[j] = temp1;
tr[j] = temp2;
}}
}
open.clear(); demo.clear(); track.clear();
for(k=0;k<array.length;k++) {
open.add(arr[k]);
demo.add(array[k]);
track.add(tr[k]); }
}}
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:
5
Enter ROOT node
A
Enter h(A):
1
A Has Left Child? (y/n)
y
Enter Child nodes:
B
Enter h(B):
3
A Has Right Child? (y/n)
y
Enter Child nodes:
C
Enter h(C):
2
B Has Left Child? (y/n)
y
Enter Child nodes:
D
Enter h(D):
5
B Has Right Child? (y/n)
y
Enter Child nodes:
E
Enter h(E):
4
Enter Goal State:
E
1.
OPEN: [A] X = A
CLOSE: []
2.
OPEN: [C, B] X = C
CLOSE: [A]
3.
OPEN: [B] X = B
CLOSE: [A, C]
4.
OPEN: [E, D] X = E
CLOSE: [A, C, B]
GOAL STATE E found
0 comments:
Post a Comment