1

I have spent entire weekend playing around with this. I am trying to store the nodes in PriorityQueue data structure. My astar function doesnt seem to be doing what it should. Anyone mind having a look?

public void aStar(Node from, Node to) {

    PriorityQueue<Node> exploreList = new PriorityQueue<Node>();
    ArrayList<Node> visited = new ArrayList<Node>();
    ArrayList<Node> successors = new ArrayList<Node>();

    Node current = from;
    System.out.println(current.getName());
    while (current != to) {
            successors = current.getConnected();
            Collections.sort(successors);
            for (Node n : successors) {
                    if (!visited.contains(n)) {
                            exploreList.add(n);
                    }
                    for (Node n1 : successors) {
                            if (n.fSum() > n1.fSum()) {
                            exploreList.remove(n);
                            exploreList.add(n1);
                            }      
                    }
            }
            visited.add(current);
            current = exploreList.remove();
            System.out.println(current.getName());
    }

Node Class here

   public class Node implements Comparable {
   private String name;
   private int travDist;
   private int straightDist;
   private ArrayList<Arc> arcs;

/**
 * Constructor for a new node
 * 
 * @param n
 */
   public Node(String n, int aTravDist, int aStraightDist) {
       name = n;
       travDist = aTravDist;
       straightDist = aStraightDist;

       arcs = new ArrayList<Arc>();
  }

/**
 * Adds a new arc
 * 
 * @param to
 * @param c
 */
public void addArc(Node to, int c) {
    arcs.add(new Arc(to, c));
}

/**
 * Gets the list of connected nodes to this node
 * 
 * @return
 */
public ArrayList<Node> getConnected() {
    ArrayList<Node> returnData = new ArrayList<Node>();
    for (Arc a : arcs) {
        returnData.add(a.getNode());
    }
    return returnData;
}

@Override
public int compareTo(Object o) {
    //return name.compareTo(((Node) o).getName());
    Integer sum = ((Node)o).fSum();
    return sum.compareTo(fSum());
}

public int fSum () {

    return travDist + straightDist;
}

/**
 * Gets the name of the Node
 * 
 * @return
 */
public String getName() {
    return name;
}


}
2
  • What is your heuristic function? is it n.fSum()? Commented May 6, 2013 at 8:58
  • public int fSum () { return travDist + straightDist; } Commented May 6, 2013 at 9:04

1 Answer 1

6

What you are doing is not a proper A star algorithm.

Collections.sort(successors);

You shouldn't do that. In A star you always consider all the successors. You needn't worry about the order- the priority queue will take care of that. However, adding this line increases the complexity of the algorithm.

for (Node n1 : successors) {
  if (n.fSum() > n1.fSum()) {
    exploreList.remove(n);
    exploreList.add(n1);
  }      
}

This is entirely wrong. What you are doing here is: you only add the closest of all the successors. This will be a beam search with a beam of size 1, not A star - just keep them all in.

Sign up to request clarification or add additional context in comments.

9 Comments

@SohaibMushtaq : don't forget to upvote /accept if I helped you solve your issue.
Yeah dude i am trying but its telling me i need 15 reputation points.
@SohaibMushtaq Hah that's fine you will get it in some time. You can still accept the answer though - clicking the check. Accpets guide other users to what really solved the problem for you.
Actually i check again and it didnt work. (i was calling another search function forgot to change). I commented out the lines Collections.sort(successors); and exploreList.remove(n); thats what i was meant to do correct?
@SohaibMushtaq remove the whole for cycle I have cited. What do you actually store in a Node? I actually don't see you to ever calculate the augmented paths... Can you include the definition of the class in the question?
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.