Java: Artificial Intelligence; Made Easy, w/ Java Programming; Learn to Create your * Problem Solving * Algorithms! TODAY! w/ Machine Learning & Data Structures, 1st Edition (2015)
ARCHIVE A01: Frontier Search Algorithm
For the procedure below, select an IDE of your choice. You may also use online IDE’s such as rextester.com, ideone.com, or codepad.org.
========================= ======
This is the default Frontier Search Algorithm used by most chapters throughout the book.
It is strongly recommended to view this only after you’ve finished building & successfully testing the algorithm already.
class Node {
String contents;
ArrayList<Node> children;
// CONSTRUCTOR:
public Node(String c) {
this.contents = c;
this.children = new ArrayList<Node>();
}
/*
// MAIN FRONTIER SEARCH ALGORITHM:
*/
public Path search(String query) {
// - frontier:= {new array of Nodes}
ArrayList<Path> frontier = new ArrayList<Path>();
// - create a new Path and put the Start node in it
Path p = new Path();
p.contents.add(this);
// - put the new Path into the frontier
frontier.add(p);
while (!frontier.isEmpty()) {
// - select and remove a Path <s0, s1,….,sk> from frontier;
// (use helper function pickPath() )
Path pick = pickPath(frontier);
// If node (sk) is a goal, return selected Path
if (hasGoal(query, pick)) {
return pick;
}
else {
// For every connected node of end node sk:
// - Make a copy of the selected Path
// - Add connected node of sk onto path copy
// - add copied Path <s0, s1,….,sk, s> to frontier;
int size = pick.contents.size();
Node last = pick.contents.get(size - 1);
for (Node n: last.children) {
Path toAdd = new Path();
toAdd.contents.addAll(pick.contents);
toAdd.contents.add(n);
frontier.add(toAdd);
}
}
}
// - indicate ‘NO SOLUTION’ if frontier empties
// (empty path as 'NO SOLUTION' here)
return new Path();
}
/*
// HELPER FUNCTION #1:
// NOTE: you can modify the position assignment to change the Search Strategy
*/
private Path pickPath(ArrayList<Path> f) {
// int position = 0;
int position = f.size()-1;
Path ret = f.get(position);
f.remove(position);
return ret;
}
/*
// HELPER FUNCTION #2:
*/
private boolean hasGoal(String s, Path p) {
for (Node n: p.contents) {
if (n.contents == s) return true;
}
return false;
}
}
// The Path Class:
class Path {
ArrayList<Node> contents = new ArrayList<Node>();
}
Printer Method:
Make sure to place this inside your Main Java Class.
static String printer(Path p) {
if (p.contents.isEmpty()) return "NOTE: No Solution Found";
else {
// System.out.println("FOUND A SOLUTION!");
String s = "Solution Found! Path: ";
for (int i = 0; i<p.contents.size(); i++) {
s += p.contents.get(i).contents + ", ";
}
return s;
}
}