Frontier Search Algorithm - Java: Artificial Intelligence; Made Easy, w/ Java Programming; Learn to Create your * Problem Solving * Algorithms! TODAY! w/ Machine Learning & Data Structures, 1st Edition (2015)

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;

}

}