Question

My path-finding method is given two objects containing an id, name, x/y coordinates, and path stored in an Array List. The path data is the id of each object that it can directly connect to. The objective is to call my method recursively until it finds its goal using the shortest distance, and when it reaches the end it returns true.

The problem: If the distance to the node that you came from is shorter than the other nodes in the current nodes path, then it will cause an infinite loop bouncing back and forth between the two nodes. I have struggled with this problem for several hours and could be over thinking it. Any advice or suggestions will be greatly appreciated!

The Algorithm:

while (!pathfound) {
    current = findPath(current, end);
}

public static Place findPath(Place curPlace, Place endPlace) {
    ArrayList<Integer> path = curPlace.path;
    int id;
    double lastdist = 999;
    double distance;
    Place bestPlace = null;

    for (int i = 0; i < path.size(); i++) {
        id = curPlace.path.get(i);
        distance = distance(getPlace(id), curPlace)
                + distance(getPlace(id), endPlace);
        if (distance < lastdist) {
            bestPlace = getPlace(id);
        } 

        lastdist = distance;
    }

    if (result.length() == 0) {
        result += bestPlace.name;
    } else {
        result += ", " + bestPlace.name;
    }

    System.out.println("CURCITY: " + bestPlace.id);
    System.out.println(result);
    System.out.println(lastdist);

    if (bestPlace == endPlace) {
        pathfound = true;
    }

    return bestPlace;
}

You can ignore result, it is for keeping up with the nodes that are passed through. If there are any other details you would like to know, please ask.

Was it helpful?

Solution

If it is acceptable to modify Place you can add a boolean "visited" flag. Reset them all to false prior to running the algorithm; set to true when you visit and false when you leave (don't forget to unset them on the way out of the recursion - if you do this properly you can even avoid having to explicitly reset the flags before starting). Skip nodes where the flag is true.

A more short-sighted option is to pass the last visited Place as a parameter to the function, and skip that one. This will not prevent larger loops but may be entirely appropriate for your situation and is the simplest to implement.

Both of the above are O(1) with minimal overhead. If you cannot modify Place you could store a Set of visited places (remove them from the set on the way out of recursion), and skip places that are already in that set. Depending on your performance requirements, if you use a HashSet you will want to come up with an appropriate hashing function.

Along those lines, at the expense of more memory, if your ID numbers are unique and cover a reasonably sized finite range, a boolean[] indexed by ID number is a constant time alternative to a set here (it is essentially the "visited" flag option with the flags stored externally).

OTHER TIPS

Using a recursive approach to path finding algorithm can be quite tricky, as you always need some kind of global information to evaluate, which one of two paths is more suitable. While following a single path, you can never be sure, if it is the right one. Even if you always follow the nearest node, it doesn't have to be the right path. This is called best-first search strategy and although it is not the best, it can be made to work, but you have to make sure to try other paths as well, because you can't pull it off by simply always sticking to the closest node.

If you want to do a path finding algorithm, you will need to keep track of all the nodes, that you have already explored exhaustively and therefore will never need to visit again. This can be done either explicitly, by storing the list of visited nodes in a structure of some kind, or you can be smarter about it and enforce this by good design of policy for selecting a new node to be visited.

In other words, if you keep track of the nodes to be visited along with the distances to each node (priority queue) and you always make sure to visit the nearest not-yet-visited node, you will never revisit the same nodes again, without having to explicitly enforce it, such as in A* algorithm, or Dijkstra.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top