Breadth-first search strategy for searching in map taking too long

Question

I have a problem with my program using BFS search. I am giving this method Node n and it should give me back true if it found the way to the target n using method n.expand. There are some other classes that implement Nodes and methods for expand and isTarget. When it's a short distance, it works, but when it is a longer distance between these nodes, it takes about 15 minutes or more. Can anyone help me with this problem?

public boolean prog(Node n)
{
    Queue<Node> FIFO = new LinkedList<Node>();
    List<Node> close = new LinkedList<Node>();

    FIFO.add(n);
    while (true) {
        n = FIFO.poll();

        if (close.contains(n)) {
        } else {
            close.add(n);
        }
        close.add(n);
        for (int i = 0; i < n.expand().size(); i++) {
            if (!close.contains(n.expand().get(i))) {
                FIFO.add(n.expand().get(i));
            } else {
            }

            if (n.expand().get(i).isTarget()) {
                return true;
            }else{
            }
        }
    }
}

score 1 · Answer 1 · edited May 23 '17 at 11:50

close.contains is a really expensive check considering that close is a LinkedList - it needs to, at worst, go through the entire list looking for the element, so my guess is that there's a lot of running time going into that.

I suggest you try a HashSet or TreeSet instead.

If you're familiar with big-O notation (if not, I suggest you read this post), LinkedList.contains is O(n), HashSet.contains is expected O(1) and TreeSet.contains is O(log n).

I'd also suggest that you move the n.expand() calls out of the for loop, instead storing it in a temporary variable which you use instead. Every call to n.expand() is (presumably) going to result in having to set up the collection of neighbouring nodes again.

The A* search algorithm might also be a consideration as an alternative to BFS. This involves coming up with an estimated cost to the destination (called a 'heuristic'), allowing us to focus on nodes which we think are close to the destination.

score 0 · Answer 2 · answered Apr 11 '14 at 08:52

0

You can think of Bi-directional BFS.

Consider source and destination both as source and check if they meet in some intermediate node. That should save a lot of time.

answered Apr 11 '14 at 08:52

Obaida.Opu

444
1
4
18

Ralor · Accepted Answer · 2014-04-11T10:45:01.130

Your code looks strange, I fixed it a bit.

public boolean prog(Node n)
{
    Queue<Node> FIFO = new LinkedList<Node>();
    List<Node> close = new LinkedList<Node>();

    FIFO.add(n);
    while (!FIFO.empty()) {
        n = FIFO.poll();
        if( n.isTarget() )
            return true;         
        for (int i = 0; i < n.expand().size(); i++) {
            Node nxt = n.expand().get(i); // Note dukeling suggestion here, I don't know what's behind expand()
            if (!close.contains(nxt)) {
                FIFO.add(nxt); close.add(nxt);
            }
        }
    }
    return false;
}

It also have very bad complexity (O(NM) instead of O(N+M) where N - Node count, M - edge count) because of using close.contains().

You should add internal bool flag "used" to Node (then get(i) will provide required information about that).

If it's impossible, you should add identificator (int) to every node, so you can mark it visited in local bool array (used[id]). But if Nodes count is too big for local array (up to 10^6) you souldn't use bfs at all I think.

UPD HashSet mentioned by Dukeling may provide O(N+M) in middle case and O(NM) in worst. TreeSet can provide stable O(MlogN).

it's always bad when you see while( true ) without if( ) break; or recursion without if( ) return; — Ralor, Apr 11 '14 at 12:50

Breadth-first search strategy for searching in map taking too long

3 Answers3