I have make create the following files using the type of search algorithms titled:

GoodHeuristic.java, UniformCostSearch.java, GreedySearch.java, and AStarSearch.java. The first of these files should implement an extention of the provided Heuristic class, called GoodHeuristic, which implements a good admissible heuristic function for the map search problem. A skeletal template for this file.

1. a complete Map object, encoding the map to be searched 2. a String providing the name of the starting location 3. a String providing the name of the destination location 4. an integer depth limit for the search if this depth is ever reached during a search (i.e., a node at this depth or deeper is considered for expansion), the search should be abandoned and null (indicating search failure) should be returned

a method that actually performs the search, called search, with the following properties: it takes a single boolean argument if this argument is true, then repeated state checking should be performed, otherwise no such checking should be done during search it returns a Waypoint object from the search tree that corresponds to the target destina- tion, or null if no solution was found

an integer instance variable called expansionCount that contains the number of node expansions performed during the last call to the search method

In general, your classes should allow the main method in the provided Pone class to output correct solutions (including path cost and expansion count statistics) for any map search problem provided as input to it.

In addition to these search algorithm classes, you must also provide a utility class, called GoodHeuristic, in a file named GoodHeuristic.java that extends the Heuristic class (see below) and implements an admissible heuristic function that can be quickly calculated.

Any help would be greatly appreciated, I have created a BFS algorithm prior but have not been able to implement and convert into the next algorithms. I can provided my previous work if that helps as well.

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

// // SortedFrontier.java // // This class implements a priority queue of Waypoint objects, with the next // object to be removed from the queue being determined by a sorting of // the contained Waypoint objects. There are three ways in which the // contents might be sorted, with the sorting strategy determined at the // time that the priority queue is created. The contents of the priority // queue can be sorted by partial path cost, by heuristic value, or by the // sum of these two statistics. The contained object with the lowest value // is the first to be removed. Note that the insertion method is overloaded // to accept either an individual Waypoint or a list of multiple Waypoint // objects. This class is intended to to be used to implement the frontier // (i.e., the "fringe" or "open list") of nodes in a search tree. // // //

import java.util.*; import java.io.*;

enum SortBy { g, h, f }

class WaypointComparator implements Comparator, Serializable { static final long serialVersionUID = 1; // Version 1 SortBy statistic;

// Default constructor ... public WaypointComparator() { this.statistic = SortBy.g; }

// Constructor with sorting criterion argument ... public WaypointComparator(SortBy strategy) { this.statistic = strategy; }

// compare -- Determine which of two Waypoints is "larger", according // to the Comparator protocol. public int compare(Waypoint wp1, Waypoint wp2) { // Extract the appropriate statistics ... double val1 = 0.0; double val2 = 0.0; switch (statistic) { case g: val1 = wp1.partialPathCost; val2 = wp2.partialPathCost; break; case h: val1 = wp1.heuristicValue; val2 = wp2.heuristicValue; break; case f: val1 = wp1.partialPathCost + wp1.heuristicValue; val2 = wp2.partialPathCost + wp2.heuristicValue; break; } // Compare values ... if (val1 < val2) return (-1); if (val1 > val2) return (1); if (wp1.equals(wp2)) { // This is the exact same Waypoint ... return (0); } else { // These are two Waypoint objects with the same value, but we // still need to put them in some order. Otherwise, two nodes // with the same value will "overwrite" each other ... if (wp1.loc.equals(wp2.loc)) { // Even the locations are the same, so order the two nodes // based on the ordering of their parents in the search // tree ... return (this.compare(wp1.previous, wp2.previous)); } else { // The locations differ, so we can use the alphabetical // ordering of their names to order the nodes ... return (wp1.loc.name.compareTo(wp2.loc.name)); } } }

}

public class SortedFrontier { SortBy sortingStrategy; SortedSet fringe;

// Default constructor ... public SortedFrontier() { this.sortingStrategy = SortBy.g; Comparator sortingComparator = new WaypointComparator(this.sortingStrategy); this.fringe = new TreeSet(sortingComparator); }

// Constructor with sorting strategy specified ... public SortedFrontier(SortBy strategy) { this.sortingStrategy = strategy; Comparator sortingComparator = new WaypointComparator(this.sortingStrategy); this.fringe = new TreeSet(sortingComparator); }

// isEmpty -- Return true if and only if there are currently no nodes in // the frontier. public boolean isEmpty() { return (fringe.isEmpty()); }

// removeTop -- Return the Waypoint object at the top of the frontier // list. Also, remove this node from the frontier. Return null if the // frontier is empty. public Waypoint removeTop() { if (fringe.isEmpty()) { return (null); } else { Waypoint top = fringe.first(); fringe.remove(top); return (top); } }

// addSorted -- Add the given Waypoint object to the frontier in the // appropriate position, given its sorting statistics. public void addSorted(Waypoint wp) { fringe.add(wp); } // addSorted -- Add the given list of Waypoint objects to the frontier // in the appropriate positions, given their sorting statistics. public void addSorted(List points) { for (Waypoint wp : points) { addSorted(wp); } }

// remove -- Remove a specified Waypoint object from the frontier. public void remove(Waypoint wp) { fringe.remove(wp); }

// remove -- Remove all of the Waypoint objects in the given list from // the frontier. public void remove(List points) { for (Waypoint wp : points) { remove(wp); } }

// contains -- Return true if and only if the frontier contains a // Waypoint with the given Location name. public boolean contains(String name) { // This linear search is very inefficient, but it cannot be avoided // without maintaining a parallel data structure containing the // fringe members (e.g., a HashSet) indexed by location name. for (Waypoint element : fringe) if (name.equals(element.loc.name)) return (true); // The location was not found in the fringe ... return (false); }

// contains -- Return true if and only if the frontier contains a // Waypoint with the given Location object as its state. public boolean contains(Location loc) { return (contains(loc.name)); }

// contains -- Return true if and only if the frontier contains an // equivalent Waypoint (with regard to the Location) to the one provided // as an argument. public boolean contains(Waypoint wp) { return (contains(wp.loc)); }

// find -- Return a Waypoint in the frontier with the given location // name, or null if there is no such Waypoint. public Waypoint find(String name) { // This linear search is very inefficient, but it cannot be avoided // without maintaining a parallel data structure containing the // fringe members (e.g., a HashSet) indexed by location name. for (Waypoint element : fringe) if (name.equals(element.loc.name)) return (element); // The location was not found in the fringe ... return (null); }

// find -- Return a Waypoint in the frontier with the given location // name, or null if there is no such Waypoint. public Waypoint find(Location loc) { return (find(loc.name)); }

// find -- Return a Waypoint in the frontier with the same location // name as the provided Waypoint, or null if there is no such Waypoint. public Waypoint find(Waypoint wp) { return (find(wp.loc)); }

}

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

// // GoodHeuristic // // This class extends the Heuristic class, providing a reasonable // implementation of the heuristic function method. The provided "good" // heuristic function is admissible. // // YOUR NAME -- TODAY'S DATE //

public class GoodHeuristic extends Heuristic {

// YOU CAN ADD ANYTHING YOU LIKE TO THIS CLASS ... WHATEVER WOULD // ASSIST IN THE CALCULATION OF YOUR GOOD HEURISTIC VALUE.

// heuristicFunction -- Return the appropriate heuristic values for the // given search tree node. Note that the given Waypoint should not be // modified within the body of this function. public double heuristicFunction(Waypoint wp) { double hVal = 0.0; // COMPUTE A REASONABLE HEURISTIC VALUE HERE

return (hVal); }

}

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

/ // Heuristic // // This class implements a heuristic function for use when performing a map // search for a shortest path from one location to another. The heuristic // function object records the destination location for use when calculating // the heuristic value of a given search tree node (i.e., Waypoint). This // basic heuristic function assigns a value of zero to all nodes, but classes // that inherit from this one can override this behavior to do something // more reasonable. // // David Noelle -- Wed Feb 21 14:55:23 PST 2007 //

public class Heuristic { Location destination;

// Default constructor ... public Heuristic() { this.destination = null; } // Constructor with desination Location object specified ... public Heuristic(Location destination) { this.destination = destination; }

// getDestination -- Return the destination being used by this heuristic // function. public Location getDestination() { return (destination); }

// setDestination -- Set the destination location to be used by this // heuristic function to the given location. public void setDestination(Location destination) { this.destination = destination; }

// heuristicFunction -- Return the appropriate heuristic values for the // given search tree node. Note that the given Waypoint should not be // modified within the body of this function. For this skeletal class, // a value of zero is returned for every node. Classes that inherit // from this one should override this method to do something more // reasonable. public double heuristicFunction(Waypoint wp) { return (0.0); }

}

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

// // Location // // This class implements a place on a map. It is a single "state" in the // "state space" to be searched for a short route from one location to // another. Each location includes a textual name, a pair of Cartesian // coordinates, and a collection of Road objects which encode the immediate // routes leading away from this location. Note that textual names are // assumed to be unique; two locations are considered the same if they have // the same name. // // David Noelle -- Sun Feb 11 17:37:21 PST 2007 //

import java.io.*; import java.util.*;

public class Location { public String name = ""; public double longitude = 0.0; public double latitude = 0.0; public List roads;

// Default constructor ... public Location() { this.roads = new ArrayList(); }

// Constructor with location name specified ... public Location(String name) { this(); this.name = name; }

// Constructor with location name and coordinates specified ... public Location(String name, double longitude, double latitude) { this(name); this.longitude = longitude; this.latitude = latitude; }

// equals -- Return true if and only if this location has the same name // as the argument location. public boolean equals(Location loc) { return (loc.name.equals(this.name)); }

// read -- Read a location description from the given stream into this // object. At minimum, a name must be read from the stream. Optionally, // coordinates may also be specified as a pair of double precision // floating point numbers. Return true if at least a name was read and // false otherwise. public boolean read(BufferedReader str) { try { String thisLine = str.readLine(); if (thisLine == null) // No more input, at all ... return (false); Scanner inScanner = new Scanner(thisLine).useDelimiter("\\s+"); if (inScanner.hasNext()) { // There is something to read ... name = inScanner.next(); if (inScanner.hasNextDouble()) { // There is a longitude to read ... longitude = inScanner.nextDouble(); if (inScanner.hasNextDouble()) { // There is a latitude to read ... latitude = inScanner.nextDouble(); } } // At least a name was successfully read ... return (true); } else { // Did not even read a name ... return (false); } } catch (IOException e) { // Something went wrong ... return (false); } }

// write -- Write the name of this location to the given stream. If the // "showCoords" argument is true, then also output the Cartesian // coordinates of this location, separated by blanks, on the same line. public void write(OutputStream str, boolean showCoords) { PrintWriter out = new PrintWriter(str, true); out.printf("%s", name); if (showCoords) { out.printf(" %f %f", longitude, latitude); } }

// findRoad -- Search the collection of roads leading out of this // location for one that leads directly to the argument destination // location. Return this Road object if it is found, or null if no // matching road is found. public Road findRoad(Location destination) { for (Road r : roads) { if (r.toLocation.equals(destination)) return (r); } return (null); }

// recordRoad -- Add the given Road object to the collection of roads // leading out of this location. public void recordRoad(Road r) { roads.add(r); }

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

// // Map // // This class implements a simple street map for the purposes of shortest-path // search. It makes use of Location objects to encode specific locations on // the map and Road objects to encode direct connections between locations. // These maps are designed to be read from simple text files. In particular, // two files are needed to specify a map: a location file and a road file. // The location file contains a list of all locations on the map, with one // location per line. The road file contains a list of all road segments on // the map, with one road segment per line. The pathnames of these two files // are stored in the Map object, so the files can be specified in advance of // their being read and parsed. The map is stored as a collection of // Location objects, with each Location being given the responsibility of // maintaining all of the Road objects corresponding to road segments leading // out of it. // // David Noelle -- Sun Feb 11 18:05:18 PST 2007 //

import java.io.*; import java.util.*;

public class Map { String locationFilename = "locations.dat"; String roadFilename = "roads.dat"; List locations;

// Default constructor ... public Map() { this.locations = new ArrayList(); }

// Constructor with filenames specified ... public Map(String locationFilename, String roadFilename) { this(); this.locationFilename = locationFilename; this.roadFilename = roadFilename; }

// setLocationFilename -- Record the given pathname of a location file for // later use during map reading. public void setLocationFilename(String filename) { locationFilename = filename; }

// setRoadFilename -- Record the given pathname of a road file for later // use during map reading. public void setRoadFilename(String filename) { roadFilename = filename; }

// promptForFilenames -- Using the standard output stream and the standard // input stream, prompt the user to input the pathnames for a location // file and for a road file. Record the input pathnames in this Map object // for later use during map reading. Return false on error. public boolean promptForFilenames() { try { InputStreamReader converter = new InputStreamReader(System.in); BufferedReader in = new BufferedReader(converter); String buffer; System.out.println("Enter the name of the location file:"); buffer = in.readLine(); setLocationFilename(buffer); System.out.println("Enter the name of the road file:"); buffer = in.readLine(); setRoadFilename(buffer); } catch (IOException e) { // Something went wrong ... return (false); } return (true); }

// findLocation -- Search through the collection of locations on this map // for one with the given textual name. Return a reference to the // corresponding Location object, or null if no such location is found. public Location findLocation(String name) { for (Location loc : locations) { if (loc.name.equals(name)) return (loc); } return (null); }

// recordLocation -- Add the given Location object to the collection of // locations for this map. public void recordLocation(Location loc) { locations.add(loc); }

// readLocations -- Attempt to open the location file specified by the // appropriate pathname stored in this Map object. If this file can // be opened for reading, read a collection of locations from this file // into the Map object's collection of Location objects. Return false // on error. public boolean readLocations() { try { File locFile = new File(locationFilename); if (locFile.exists() && locFile.canRead()) { FileInputStream locFileIn = new FileInputStream(locFile); InputStreamReader locISReader = new InputStreamReader(locFileIn); BufferedReader locBufferedReader = new BufferedReader(locISReader); // Allocate storage for the first location to be read ... Location loc = new Location(); while (loc.read(locBufferedReader)) { // Record location in the map ... recordLocation(loc); // Allocate storage for the next location ... loc = new Location(); } return (true); } else { // The file cannot be read ... return (false); } } catch (IOException e) { // Something went wrong ... return (false); } }

// readRoads -- Attempt to open the road file specified by the appropriate // pathname stored in this Map object. If this file can be opened for // reading, read a collection of roads from this file. Generate // corresponding Road objects and store those objects in the appropriate // Location objects in this Map object's collection of locations. Note // that this means that the map must know about all locations on the map // before a road file is read. This can be done by calling the // "readLocations" method before calling this method. Return false on // error. public boolean readRoads() { try { File roadFile = new File(roadFilename); if (roadFile.exists() && roadFile.canRead()) { FileInputStream roadFileIn = new FileInputStream(roadFile); InputStreamReader roadISReader = new InputStreamReader(roadFileIn); BufferedReader roadBufferedReader = new BufferedReader(roadISReader); // Allocate storage for the first road segment ot be read ... Road r = new Road(); while (r.read(roadBufferedReader)) { // Fill in connections to location objects ... r.fromLocation = findLocation(r.fromLocationName); if (r.fromLocation == null) { System.err.printf("The location, %s, is not known. ", r.fromLocationName); return (false); } r.toLocation = findLocation(r.toLocationName); if (r.toLocation == null) { System.err.printf("The location, %s, is not known. ", r.toLocationName); return (false); } // Record the road in the appropriate location ... r.fromLocation.recordRoad(r); // Allocate storage for the next road segment ... r = new Road(); } return (true); } else { // The specified road file could not be read ... return (false); } } catch (IOException e) { // Something went wrong ... return (false); } }

// readMap -- Prompt the user for the pathnames of a location file and // a road file, and then read those files into this Map object. Return // false on error. public boolean readMap() { return (promptForFilenames() && readLocations() && readRoads()); }

}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

// // Pone // // This class provides a "main" method that acts as a driver program for // evaluating a variety of heuristic search algorithms, as applied to // shortest-path searches on a map. A Map object is used to read in and // record a map from two files: one containing a list of locations and the // other containing a list of road segments. The user is then prompted for // a starting location on this map and a destination location. Three search // algorithms are then tested on this specified search problem: uniform-cost // search, greedy search, and A* search. Also, the effect of repeated state // checking is examined. A depth limit is provided to the search algorithms, // and the algorithms are expected to terminate and report failure if that // depth limit is ever reached during search. Summary results are sent to the // standard output stream. // // David Noelle -- Wed Feb 21 17:17:38 PST 2007 //

import java.io.*;

public class Pone {

public static void main(String[] args) { try { Map graph = new Map(); InputStreamReader converter = new InputStreamReader(System.in); BufferedReader in = new BufferedReader(converter); String initialLoc; String destinationLoc; Waypoint solution; int limit = 1000; // depth limit, to avoid infinite loops

System.out.println("HEURISTIC SEARCH ALGORITHM COMPARISON"); // Read map ... if (!(graph.readMap())) { System.err.println("Error: Unable to read map."); return; } // Get initial and final locations ... System.out.println("Enter the name of the initial location:"); initialLoc = in.readLine(); System.out.println("Enter the name of the destination location:"); destinationLoc = in.readLine(); // Testing uniform-cost search without repeated state checking ... System.out.println("TESTING UNIFORM-COST SEARCH WITHOUT REPEATED STATE CHECKING"); UniformCostSearch ucs = new UniformCostSearch(graph, initialLoc, destinationLoc, limit); solution = ucs.search(false); System.out.println("Solution:"); if (solution == null) { System.out.println("None found."); } else { solution.reportSolution(System.out); System.out.printf("Path Cost = %f. ", solution.partialPathCost); } System.out.printf("Number of Node Expansions = %d. ", ucs.expansionCount); // Testing uniform-cost search with repeated state checking ... System.out.println("TESTING UNIFORM-COST SEARCH WITH REPEATED STATE CHECKING"); solution = ucs.search(true); System.out.println("Solution:"); if (solution == null) { System.out.println("None found."); } else { solution.reportSolution(System.out); System.out.printf("Path Cost = %f. ", solution.partialPathCost); } System.out.printf("Number of Node Expansions = %d. ", ucs.expansionCount);

// Testing greedy search without repeated state checking ... System.out.println("TESTING GREEDY SEARCH WITHOUT REPEATED STATE CHECKING"); GreedySearch gs = new GreedySearch(graph, initialLoc, destinationLoc, limit); solution = gs.search(false); System.out.println("Solution:"); if (solution == null) { System.out.println("None found."); } else { solution.reportSolution(System.out); System.out.printf("Path Cost = %f. ", solution.partialPathCost); } System.out.printf("Number of Node Expansions = %d. ", gs.expansionCount); // Testing greedy search with repeated state checking ... System.out.println("TESTING GREEDY SEARCH WITH REPEATED STATE CHECKING"); solution = gs.search(true); System.out.println("Solution:"); if (solution == null) { System.out.println("None found."); } else { solution.reportSolution(System.out); System.out.printf("Path Cost = %f. ", solution.partialPathCost); } System.out.printf("Number of Node Expansions = %d. ", gs.expansionCount);

// Testing A* search without repeated state checking ... System.out.println("TESTING A* SEARCH WITHOUT REPEATED STATE CHECKING"); AStarSearch as = new AStarSearch(graph, initialLoc, destinationLoc, limit); solution = as.search(false); System.out.println("Solution:"); if (solution == null) { System.out.println("None found."); } else { solution.reportSolution(System.out); System.out.printf("Path Cost = %f. ", solution.partialPathCost); } System.out.printf("Number of Node Expansions = %d. ", as.expansionCount); // Testing A* search with repeated state checking ... System.out.println("TESTING A* SEARCH WITH REPEATED STATE CHECKING"); solution = as.search(true); System.out.println("Solution:"); if (solution == null) { System.out.println("None found."); } else { solution.reportSolution(System.out); System.out.printf("Path Cost = %f. ", solution.partialPathCost); } System.out.printf("Number of Node Expansions = %d. ", as.expansionCount);

// Done ... System.out.println("ALGORITHM COMPARISON COMPLETE"); } catch (IOException e) { // Something went wrong ... } } }

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

// // Road // // This class implements a segment of road directly connecting two nearby // locations on a map. Thus, Road objects form the "links" between location // "states", and the collection of all Road objects leading out of a given // location provides the result of the "successor function" for that "state". // Each road segment has a name. While it would be nice if these road names // were unique, there is nothing in this or related classes that depends on // road names being unique identifiers. (This is unlike Location names, which // must be unique.) Each Road also maintains the names of "from" and "to" // locations, as well as references to the actual Location objects // corresponding to those locations. (Note that this is slightly redundant, // as the Location objects know their own names, but this redundancy makes // the reading of maps from files a little easier.) Lastly, each Road object // has an incremental path cost: the cost, in either time or distance, of // traversing this road segment. // // David Noelle -- Sun Feb 11 17:53:48 PST 2007 //

import java.io.*; import java.util.*;

public class Road { public String name; public String fromLocationName; public String toLocationName; public Location fromLocation; public Location toLocation; public double cost = 0.0;

// read -- Read a road segment description from the given stream into this // object. Every road segment description must include the following // fields, separated by whitespace: a textual name, a textual "from" // location name, a textual "to" location name, and a double precision // floating point incremental path cost. Return true if and only if all // fields are successfully read. public boolean read(BufferedReader str) { try { String thisLine = str.readLine(); if (thisLine == null) // No more input, at all ... return (false); Scanner inScanner = new Scanner(thisLine).useDelimiter("\\s+"); if (!inScanner.hasNext()) return (false); name = inScanner.next(); if (!inScanner.hasNext()) return (false); fromLocationName = inScanner.next(); fromLocation = null; if (!inScanner.hasNext()) return (false); toLocationName = inScanner.next(); toLocation = null; if (!inScanner.hasNextDouble()) return (false); cost = inScanner.nextDouble(); return (true); } catch (IOException e) { // Something went wrong ... return (false); } }

// write -- Write a description of this Road object to the given stream. // If "showLocs" is false, then only write the name of the road segment. // If "showLocs" is true, then generate a more verbose description of // the road segment that includes the names of the "from" and "to" // locations. public void write(OutputStream str, boolean showLocs) { PrintWriter out = new PrintWriter(str, true); if (showLocs) { out.printf("%s FROM %s TO %s", name, fromLocationName, toLocationName); } else { out.printf("%s", name); } }

}

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

// // Waypoint // // This class implements a "node" in a search tree being constructed to find // a shortest path from one location to another on a map. Each node includes // a reference to the corresponding location "state", a reference to its parent // in the search tree (i.e., the "previous" node), and a collection of children // nodes (i.e., the "options" for the next step) which remains empty until the // node is expanded. Each Waypoint node also records the depth of the node in // the search tree, the partial path cost from the initial node in the search // tree to this one, and a heuristic evaluation value for this node. This // class provides two noteworthy methods. First, the "expand" method fills // in the "options" list of children of this node, using information embedded // in this node's Location object. Second, the "reportSolution" recursive // method uses the "previous" references of nodes in the search tree in order // to output the path from the initial node of the search tree to this node. // // David Noelle -- Sun Feb 11 18:26:42 PST 2007 //

import java.io.*; import java.util.*;

public class Waypoint { public Location loc; public Waypoint previous; public List options; public int depth = 0; public double partialPathCost = 0.0; public double heuristicValue = 0.0;

// Default constructor ... public Waypoint() { this.options = new ArrayList(); }

// Constructor with Location object specified ... public Waypoint(Location loc) { this(); this.loc = loc; }

// Constructor with Location object and parent node specified ... public Waypoint(Location loc, Waypoint previous) { this(loc); this.previous = previous; }

// expand -- Fill in the collection of children of this node, stored in // it's "options" variable. Make sure that each child is appropriately // linked into the search tree, and make sure that it's partial path cost // is correctly calculated. This version of this method, which takes no // arguments, always sets the heuristic values of nodes to zero. public void expand() { options.removeAll(options); for (Road r : loc.roads) { Waypoint option = new Waypoint(r.toLocation, this); option.depth = this.depth + 1; option.partialPathCost = this.partialPathCost + r.cost; option.heuristicValue = 0.0; options.add(option); } }

// expand -- Fill in the collection of children of this node, stored in // it's "options" variable. Make sure that each child is appropriately // linked into the search tree, and make sure that it's partial path cost // is correctly calculated. This version of this method, which takes a // heuristic function object as an argument, uses the given heuristic // function to fill in the heuristic values of the children nodes. public void expand(Heuristic h) { options.removeAll(options); for (Road r : loc.roads) { Waypoint option = new Waypoint(r.toLocation, this); option.depth = this.depth + 1; option.partialPathCost = this.partialPathCost + r.cost; option.heuristicValue = h.heuristicFunction(option); options.add(option); } }

// isFinalDestination -- Return true if and only if the name of the // location corresponding to this node matches the provided argument. public boolean isFinalDestination(String destinationName) { return (loc.name.equals(destinationName)); }

// reportSolution -- Output a textual description of the path from the // root of the search tree (i.e., the initial node) to this node, sending // the description to the given stream. Note that this method is // recursive; a recursive call outputs the path up to the parent of this // node before the final road segment in the path is described. public void reportSolution(OutputStream str) { PrintWriter out = new PrintWriter(str, true); if (previous == null) { // This is the starting point ... out.printf("START AT "); loc.write(str, false); out.printf(". "); } else { // First provide the solution up until this point ... previous.reportSolution(str); // Now report the road segment to this point ... out.printf("TAKE "); (previous.loc.findRoad(loc)).write(str, true); out.printf(". "); } }

}

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SAMPLE: car-dealer-to-bus-station-log

---------------------------------------------------------------------------------------

HEURISTIC SEARCH ALGORITHM COMPARISON Enter the name of the location file: small-locations.dat Enter the name of the road file: small-roads.dat Enter the name of the initial location: car-dealer Enter the name of the destination location: bus-station TESTING UNIFORM-COST SEARCH WITHOUT REPEATED STATE CHECKING Solution: START AT car-dealer. TAKE back-road FROM car-dealer TO truck-stop. TAKE highway-south FROM truck-stop TO bookstore. TAKE highway-east FROM bookstore TO fast-food. TAKE highway-north FROM fast-food TO bus-station. Path Cost = 25.100000. Number of Node Expansions = 22. TESTING UNIFORM-COST SEARCH WITH REPEATED STATE CHECKING Solution: START AT car-dealer. TAKE back-road FROM car-dealer TO truck-stop. TAKE highway-south FROM truck-stop TO bookstore. TAKE highway-east FROM bookstore TO fast-food. TAKE highway-north FROM fast-food TO bus-station. Path Cost = 25.100000. Number of Node Expansions = 9. TESTING GREEDY SEARCH WITHOUT REPEATED STATE CHECKING Solution: START AT car-dealer. TAKE overgrown-path FROM car-dealer TO fast-food. TAKE highway-north FROM fast-food TO bus-station. Path Cost = 32.100000. Number of Node Expansions = 2. TESTING GREEDY SEARCH WITH REPEATED STATE CHECKING Solution: START AT car-dealer. TAKE overgrown-path FROM car-dealer TO fast-food. TAKE highway-north FROM fast-food TO bus-station. Path Cost = 32.100000. Number of Node Expansions = 2. TESTING A* SEARCH WITHOUT REPEATED STATE CHECKING Solution: START AT car-dealer. TAKE back-road FROM car-dealer TO truck-stop. TAKE highway-south FROM truck-stop TO bookstore. TAKE highway-east FROM bookstore TO fast-food. TAKE highway-north FROM fast-food TO bus-station. Path Cost = 25.100000. Number of Node Expansions = 8. TESTING A* SEARCH WITH REPEATED STATE CHECKING Solution: START AT car-dealer. TAKE back-road FROM car-dealer TO truck-stop. TAKE highway-south FROM truck-stop TO bookstore. TAKE highway-east FROM bookstore TO fast-food. TAKE highway-north FROM fast-food TO bus-station. Path Cost = 25.100000. Number of Node Expansions = 8. ALGORITHM COMPARISON COMPLETE ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

small-locations.dat

---------------------------------------------

home 32.1 54.4

corner-store 37.9 58.2

school 42.0 55.5

fire-station 28.1 50.3

coffee-shop 36.6 49.8

bus-station 42.0 50.0

stadium 59.9 49.1

ranch 67.7 44.0

park 86.0 42.0

donut-shop 37.6 41.9

police-station 27.7 36.5

grocery-store 34.1 39.9

fast-food 48.0 36.4

gym 35.3 32.3

diner 69.0 32.0

car-dealer 47.7 22.2

bookstore 64.0 24.2

truck-stop 66.6 18.1

factory 31.9 28.2

---------------------------------------------------------------------------------

small-roads.dat

---------------------------------------

path home corner-store 3.1

path corner-store home 3.1

sidewalk home fire-station 3.3

sidewalk fire-station home 3.3

north-street corner-store school 4.2

north-street school corner-store 4.2

hill-street home coffee-shop 3.6

hill-street coffee-shop home 3.6

narrows fire-station coffee-shop 5.1

narrows coffee-shop fire-station 5.1

central home bus-station 6.9

central bus-station home 6.9

elm-street school bus-station 5.8

elm-street bus-station school 5.8

the-avenue coffee-shop bus-station 4.9

the-avenue bus-station coffee-shop 4.9

back-street fire-station police-station 9.9

back-street police-station fire-station 9.9

side-street coffee-shop donut-shop 6.6

side-street donut-shop coffee-shop 6.6

lower-main police-station grocery-store 3.9

lower-main grocery-store police-station 3.9

upper-main grocery-store donut-shop 3.7

upper-main donut-shop grocery-store 3.7

alley grocery-store gym 4.2

alley gym grocery-store 4.2

grimey-place police-station factory 6.3

grimey-place factory police-station 6.3

damp-drive factory gym 4.9

damp-drive gym factory 4.9

long-drive gym car-dealer 13.0

long-drive car-dealer gym 13.0

back-road car-dealer truck-stop 15.3

back-road truck-stop car-dealer 15.3

highway-north bus-station fast-food 4.2

highway-north fast-food bus-station 4.2

highway-east fast-food bookstore 4.2

highway-east bookstore fast-food 4.2

highway-south bookstore truck-stop 1.4

highway-south truck-stop bookstore 1.4

overgrown-path fast-food car-dealer 27.9

overgrown-path car-dealer fast-food 27.9

hill-pass school stadium 18.1

hill-pass stadium school 18.1

stadium-street bus-station stadium 16.0

stadium-street stadium bus-station 16.0

gravel-road stadium ranch 15.4

gravel-road ranch stadium 15.4

old-highway ranch diner 19.1

old-highway diner ranch 19.1

dirt-road ranch park 35.5

dirt-road park ranch 35.5

access-road diner bookstore 14.4

access-road bookstore diner 14.4