1
\$\begingroup\$

Introduction

I have this iterative deepening search algorithm. The main "research" attempt was to find out a bidirectional version of that search, and it turned out to be superior compared to two other ID algorithms. The code I would like to get reviewed is as follows:

package net.coderodde.libid.support;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import net.coderodde.libid.NodeExpander;

public final class BidirectionalIterativeDeepeningDepthFirstSearch<N> {

    private final N source;
    private final Deque<N> backwardSearchStack;
    private final Set<N> frontier;
    private final NodeExpander<N> forwardExpander;
    private final NodeExpander<N> backwardExpander;

    public BidirectionalIterativeDeepeningDepthFirstSearch() {
        this.source              = null;
        this.backwardSearchStack = null;
        this.frontier            = null;
        this.forwardExpander     = null;
        this.backwardExpander    = null;
    }

    private BidirectionalIterativeDeepeningDepthFirstSearch(
        N source,
        NodeExpander<N> forwardExpander,
        NodeExpander<N> backwardExpander) {
        this.source              = source;
        this.backwardSearchStack = new ArrayDeque<>();
        this.frontier            = new HashSet<>();
        this.forwardExpander     = forwardExpander;
        this.backwardExpander    = backwardExpander;
    }

    public List<N> search(N source, 
                          N target, 
                          NodeExpander<N> forwardExpander,
                          NodeExpander<N> backwardExpander) {
        // Handle the easy case. We need this in order to terminate the 
        // recursion in buildPath.
        if (source.equals(target)) {
            return new ArrayList<>(Arrays.asList(source));
        }

        BidirectionalIterativeDeepeningDepthFirstSearch<N> state = 
                new BidirectionalIterativeDeepeningDepthFirstSearch<>(
                        source,
                        forwardExpander,
                        backwardExpander);

        for (int depth = 0;; ++depth) {
            // Do a depth limited search in forward direction. Put all nodes at 
            // depth == 0 to the frontier.
            state.depthLimitedSearchForward(source, depth);

            // Perform a reversed search starting from the target node and 
            // recurring to the depth 'depth'.
            N meetingNode = state.depthLimitedSearchBackward(target, depth);

            if (meetingNode != null) {
                return state.buildPath(meetingNode);
            }

            state.backwardSearchStack.clear();

            // Perform a reversed search once again with depth = 'depth + 1'.
            // We need this in case the shortest path has odd number of arcs.
            meetingNode = state.depthLimitedSearchBackward(target, depth + 1);

            if (meetingNode != null) {
                return state.buildPath(meetingNode);
            }

            state.backwardSearchStack.clear();
            // Wipe out the frontier.
            state.frontier.clear();
        }
    }

    private void depthLimitedSearchForward(N node, int depth) {
        if (depth == 0) {
            frontier.add(node);
            return;
        }

        for (N child : forwardExpander.expand(node)) {
            depthLimitedSearchForward(child, depth - 1);
        }
    }

    private N depthLimitedSearchBackward(N node, int depth) {
        backwardSearchStack.addFirst(node);

        if (depth == 0) {
            if (frontier.contains(node)) {
                return node;
            }

            backwardSearchStack.removeFirst();
            return null;
        }

        for (N parent : backwardExpander.expand(node)) {
            N meetingNode = depthLimitedSearchBackward(parent, depth - 1);

            if (meetingNode != null) {
                return meetingNode;
            } 
        }

        backwardSearchStack.removeFirst();
        return null;
    }

    private List<N> buildPath(N meetingNode) {
        List<N> path = new ArrayList<>();
        List<N> prefixPath = 
                new BidirectionalIterativeDeepeningDepthFirstSearch<N>()
                        .search(source, 
                                meetingNode, 
                                forwardExpander, 
                                backwardExpander);
        path.addAll(prefixPath);
        path.remove(path.size() - 1);
        path.addAll(backwardSearchStack);
        return path;
    }
}

Performance figures You can see something like this:


*** 8-puzzle graph benchmark ***
Seed = 1542379748450
BreadthFirstSearch in 7 milliseconds. Path length: 14
IterativeDeepeningDepthFirstSearch in 162 milliseconds. Path length: 14
BidirectionalIterativeDeepeningDepthFirstSearch in 1 milliseconds. Path length: 14
IterativeDeepeningAStar in 1 milliseconds. Path length: 14
Algorithms agree: true

*** General graph benchmark ***
Seed = 1542379748655
Warming up...
Warming up done!
BidirectionalIterativeDeepeningDepthFirstSearch in 0 milliseconds. Path length: 4
IterativeDeepeningDepthFirstSearch in 26 milliseconds. Path length: 4
BreadthFirstSearch in 4484 milliseconds. Path length: 4

The entire project lives here.

\$\endgroup\$
  • 1
    \$\begingroup\$ "These Three". You only posted BidirectionalIterativeDeepeningDepthFirstSearch. Is that intentional? \$\endgroup\$ – Vogel612 Nov 16 '18 at 15:14
  • \$\begingroup\$ @Vogel612 My bad. Will fix soon. \$\endgroup\$ – coderodde Nov 16 '18 at 15:18
  • \$\begingroup\$ @Vogel612 But there are 3 ID search algos in a GitHub repository. \$\endgroup\$ – coderodde Nov 16 '18 at 15:20
  • 1
    \$\begingroup\$ I haven't checked, but that's not really relevant anyways. Only the code posted to Code Review is really up for review. Everything else is just context \$\endgroup\$ – Vogel612 Nov 16 '18 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.