木構造+Stack=深さ優先探索, 木構造+Queue=幅優先探索

概要

経路探索問題などは再帰的に解くことが多いかもしれませんが、ここでは木構造で経路を保存しておくことで、ループにより解けることを確認します。
また、探索対象の経路の管理をStack・Queueで行うことにより、深さ優先探索・幅優先探索が実現できることを確認します。

クラス図

• Node

• 木構造を構成するクラス。親Node→子Nodeの方向に探索が進むことになる。

• 親Nodeへの参照しか定義していないため、経路を取得するには末裔Nodeから親Nodeを辿る。

• 末裔Nodeへの参照はStackやQueueで保存しておく。

• Stack, Queue

• 末裔Nodeへの参照を保持し、次の探索対象の末裔Nodeを返却する。

• Stackの場合、新たな末裔Nodeを次の探索対象として返却する。

• Queueの場合、最古の末裔Nodeを次の探索対象として返却する。

• ISeeker

• 探索の初期値を定義する。

• 親Nodeから子Nodeの求め方を定義する。

• 探索の打ち切り判定を定義する。

• 末裔Nodeから経路の求め方を定義する。

オブジェクト図

(x,y)=(0,0)を出発して、x>0, y>0 方向を探索する様子を図にします。
上の図が深さ優先探索、下の図が幅優先探索になり、各図中の左から探索の試行回数=0, 1, 2, 3を表しています。
また、深さ優先探索では x の方向を優先的に探索しています。

実装

3x2のマス目の(0,0)から(2,1)を目指す経路を求めます。
実行結果は4通りとなり、深さ優先探索では最長の経路を最初に出力してしまうことがありますが、幅優先探索では最長の経路を最後に出力します。

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main (String[] args) throws java.lang.Exception {
        solve(DepthFirstSearcher.newSearcher(new PathSeeker()));
        solve(BreadthFirstSearcher.newSearcher(new PathSeeker()));
    }

    static void solve(AbstractSearcher<PathSeeker.Point[], PathSeeker.Point> searcher) {
        int count = 0;
        for (PathSeeker.Point[] result = searcher.next(); result != null; result = searcher.next()) {
            ++count;
            System.out.println(Arrays.toString(result));
        }
        System.out.println(count);
    }

    static class PathSeeker implements AbstractSearcher.ISeeker<PathSeeker.Point[], PathSeeker.Point> {
        final Point start = new Point(0, 0);
        final Point goal = new Point(2, 1);
        final Point[] moves = new Point[]{
            new Point(1, 0),
            new Point(-1, 0),
            new Point(0, 1),
            new Point(0, -1),
        };
        @Override
        public Point entrance() {
            return start;
        }
        @Override
        public boolean isGoal(Node<Point> leading) {
            return leading.value().equals(goal);
        }
        @Override
        public Collection<Node<Point>> advance(Node<Point> leading) {
            ArrayList<Node<Point>> result = new ArrayList<>();
            for (Point move : moves) {
                Point nextPoint = new Point(leading.value().x + move.x, leading.value().y + move.y);
                if (isValid(nextPoint, leading))
                    result.add(leading.newLeaf(nextPoint));
            }

            return result;
        }
        boolean isValid(Point nextPoint, Node<Point> leading) {
            if (nextPoint.x < start.x || nextPoint.x > goal.x) return false;
            if (nextPoint.y < start.y || nextPoint.y > goal.y) return false;
            for (Node<Point> n = leading.parent(); n != null; n = n.parent())
                if (nextPoint.equals(n.value()))
                    return false;
            return true;
        }
        @Override
        public Point[] footprint(Node<Point> leading) {
            ArrayList<Point> result = new ArrayList<>();
            for (Node<Point> n = leading; n != null; n = n.parent())
                result.add(n.value());
            Collections.reverse(result);
            return result.toArray(new Point[0]);
        }

        class Point {
            int x;
            int y;
            Point(int x, int y) {
                this.x = x;
                this.y = y;
            }
            @Override
            public String toString() {
                return String.format("P{%d,%d}", x, y);
            }
            @Override
            public boolean equals(Object o) {
                return (o instanceof Point)
                    && x == ((Point)o).x
                    && y == ((Point)o).y;
            }
        }
    }
}

class Node<E> {
    private Node<E> parent;
    private E value;
    private Node(Node<E> parent, E value) {
        this.parent = parent;
        this.value = value;
    }

    public static <E> Node<E> newRoot(E value) {
        return new Node<E>(null, value);
    }

    public Node<E> newLeaf(E value) {
        return new Node<E>(this, value);
    }

    public Node<E> parent() {
        return parent;
    }

    public E value() {
        return value;
    }

    @Override
    public String toString() {
        return String.format("Node(%s)->%s", value, parent);
    }
}

abstract class AbstractSearcher<R, E> {
    interface ISeeker<R, E> {
        E entrance();
        boolean isGoal(Node<E> leading);
        Collection<Node<E>> advance(Node<E> leading);
        R footprint(Node<E> leading);
    }

    private ISeeker<R, E> seeker;

    protected AbstractSearcher(ISeeker<R, E> seeker) {
        this.seeker = seeker;
    }

    abstract protected void add(Node<E> node);
    abstract protected Node<E> pick();
    abstract protected boolean empty();

    public R next() {
        while (!empty()) {
            Node<E> leading = pick();
            if (seeker.isGoal(leading))
                return seeker.footprint(leading);

            for (Node<E> newLeading : seeker.advance(leading))
                add(newLeading);
        }
        return null;
    }
}
class BreadthFirstSearcher<R, E> extends AbstractSearcher<R, E> {
    private Queue<Node<E>> leadingNodes;

    public static <R, E> BreadthFirstSearcher<R, E> newSearcher(ISeeker<R, E> seeker) {
        return new BreadthFirstSearcher<R, E>(seeker);
    }

    private BreadthFirstSearcher(ISeeker<R, E> seeker) {
        super(seeker);
        this.leadingNodes = new ArrayDeque<>();
        this.leadingNodes.add(Node.newRoot(seeker.entrance()));
    }

    @Override
    protected void add(Node<E> node) {
        leadingNodes.add(node);
    }

    @Override
    protected Node<E> pick() {
        return leadingNodes.poll();
    }

    @Override
    protected boolean empty() {
        return leadingNodes.isEmpty();
    }
}
class DepthFirstSearcher<R, E> extends AbstractSearcher<R, E> {
    private Stack<Node<E>> leadingNodes;

    public static <R, E> DepthFirstSearcher<R, E> newSearcher(ISeeker<R, E> seeker) {
        return new DepthFirstSearcher<R, E>(seeker);
    }

    private DepthFirstSearcher(ISeeker<R, E> seeker) {
        super(seeker);
        this.leadingNodes = new Stack<>();
        this.leadingNodes.push(Node.newRoot(seeker.entrance()));
    }

    @Override
    protected void add(Node<E> node) {
        leadingNodes.push(node);
    }

    @Override
    protected Node<E> pick() {
        return leadingNodes.pop();
    }

    @Override
    protected boolean empty() {
        return leadingNodes.empty();
    }
}

実行結果

深さ優先探索

[P{0,0}, P{0,1}, P{1,1}, P{1,0}, P{2,0}, P{2,1}]
[P{0,0}, P{0,1}, P{1,1}, P{2,1}]
[P{0,0}, P{1,0}, P{1,1}, P{2,1}]
[P{0,0}, P{1,0}, P{2,0}, P{2,1}]
4

幅優先探索

[P{0,0}, P{1,0}, P{2,0}, P{2,1}]
[P{0,0}, P{1,0}, P{1,1}, P{2,1}]
[P{0,0}, P{0,1}, P{1,1}, P{2,1}]
[P{0,0}, P{0,1}, P{1,1}, P{1,0}, P{2,0}, P{2,1}]
4