| Author |
Breadth first search
|
David Spencer
Greenhorn
Joined: May 04, 2006
Posts: 1
|
|
Hi, im new to the ranch and i know this is a big question for a first time!But here goes Ive got the code given below which can only bee changed ion the main method. It does a Breadth first search between two islands. Now i have made classes that represtent the islands and there ok, but the method requires a journey class and i have no idea what it needs to do as im having difficulty trying to work out what the method uses from it. In the main method i will creat teh variables that the method needs, but im stuck on journey class and the mothods they contain. (journey(), getLastIsland() add()inRoute() ANy helpo much appreciated public class Search { /** * Carries out a breadth first search between two islands. Method * is provided with start and end islands, a list of islands to * search through and the maximum distance that can be travelled * between islands in a single step. * * @param start Island at start of journey * @param end Island at end of journey * @param islands list of Island objects to be searched * @param max_jump maximum distance which can be travelled between islands * in any step * */ public Journey BreadthFirstSearch(Island start, Island end, ArrayList islands, int max_jump) { // routes contains a list of possible routes through the islands // of a particular length as they are being generated ArrayList routes = new ArrayList(); // List of complete possible routes between the two islands ArrayList completeRoutes = new ArrayList(); // Create the first route which just consists of the start island // add add it to routes Journey journey = new Journey(); journey.add(start); routes.add(journey); while(true) { // List of routes that are found this iteration ArrayList updated_routes = new ArrayList(); // Extend each journey by trying to add each island to it. // Don't add an island if (1) it is already in the journey // or (2) the distance between the last island in the route and // the one being added is too far for(int i = 0; i < routes.size(); i++) { Journey jor = (Journey)routes.get(i); for(int j = 0; j < islands.size(); j++) { // Check that this island isn't already in the route if(jor.inRoute((Island)islands.get(j))) { continue; } //if // Check that the distance from this island to the last one // isn't too long Island isl = jor.getLastIsland(); if(isl.getDistance((Island)islands.get(j)) > max_jump) { continue; } //if // Create a new journey by adding this island to a copy // of the curent one Journey new_journey = ((Journey)routes.get(i)).copy(); new_journey.add(islands.get(j)); // If this journey is a complete route between the start // and end islands then store it as a possibleRoute. // Otherwise it is a partial route so store it to be // extended at the next iteration if(((Island)islands.get(j)).equals(end)) { completeRoutes.add(new_journey); } else { updated_routes.add(new_journey); } //if/else } //for // Replace routes with updated routes routes = updated_routes; } //for // Don't try to extend the routes if none were genereted // this time if(updated_routes.size() == 0) { break; } //if } //while // Check to see whether any possible routes were generated // If there were none then create a route with no islands and // return that if(completeRoutes.size() == 0) { // Return an empty journey Journey empty = new Journey(); return empty; } else { // If some routes were created then go through them and // find the shortest one Journey shortest_route = (Journey)completeRoutes.get(0); for(int i = 0; i < completeRoutes.size(); i++) { if(((Journey)completeRoutes.get(i)).length() < shortest_route.length()) { shortest_route = (Journey)completeRoutes.get(i); } //if } //for return shortest_route; } //if/else } // public BreadthFirstSearch public static void main(String[] args) {
|
 |
 |
I agree. Here's the link: jrebel
|
|
subject: Breadth first search
|
|
|