[Java] LIFOで経路探索

#LIFOで経路探索
迷路をとくアルゴリズムはLIFOを使えばいけるそうな

#迷路
まずはこのような感じで迷路があったとして

等間隔に地点を設けます

しかしBCDやFなどはただの通路なので省いても問題ありません

ので削除してこう

このようなマップで探索をします

#LIFO
今回は深さ優先で探索します
つまり行き止まりまでとりあえず進む人間の進み方と同じです。
##①
スタート地点を1とした時に
地点1を追加

##②
一番上にある地点と繋がっている地点を追加
この場合7と2なので追加

これを行き止まりになるまで繰り返します
ので
2と繋がっている6を追加

##④
6は行き止まりでゴールでもないので削除

##⑤
2ももう行ける地点がないので削除

##⑥
7と繋がっている14と8を追加

##という流れです

#出来上がったものがこちらになります
##Main

DFS.java

import java.util.Scanner;
import java.util.Stack;
//https://qiita.com/drken/items/4a7869c5e304883f539b#3-%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2-dfs-%E3%81%A8%E5%B9%85%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2-bfs

public class LIFO {
    static class NodeM extends Node {
        int x, y;

        NodeM(String name, int x, int y) {
            super(name);
            this.x = x;
            this.y = y;
        }
    }

    static Scanner sc;
    static boolean debug = false;

    public static void main(String[] args) {
        sc = new Scanner(System.in);
        NodeM[] graph;
        graph = setData();
        printMap(graph, 5, 5);

        int start;//存在する名前を入力するまでずっと受付くん
        while((start = searchNode(graph,input("始点"))) == -1);
        int goal;
        while((goal = searchNode(graph,input("終点"))) == -1);
        debug = !input("過程の表示 0 or 1").equals("0");
        Stack<NodeM> dfs = DFS(graph, start, goal);
        if (dfs.size() != 0) {
            System.out.println("ゴールへの経路:" + dfs);
        } else {
            System.out.println("見つかりませんでした");
        }
        printMap(graph, 5, 5);
    }
    static int searchNode(Node[] graph,String name){
        for (int i = 0; i < graph.length; i++)
            if(graph[i].name.equals(name))return i;
        return -1;
    }
    //深さ優先探索
    static Stack<NodeM> DFS(NodeM[] graph, int start, int goal) {
        Stack<NodeM> dfs = new Stack<>();
        dfs.push(graph[start]);//初期位置をスタックに追加
        for (int i = 0; dfs.size() > 0 && i < 100; i++) {
            if (debug) System.out.println(dfs);
            NodeM currentNode = dfs.peek();
            currentNode.visit = Visit.探索中;
            for (Node toNode : currentNode.branch) {
                System.out.print(i + "\t:" + currentNode + "->" + toNode + " ");
                if (toNode.visit != Visit.未探索) {
                    System.out.println(toNode.visit);
                    continue;
                }
                System.out.println();
                toNode.from = currentNode;
                dfs.push((NodeM) toNode);

                if (toNode.name.equals(graph[goal].name)) {
                    int notSearch;
                    do {
                        notSearch = onlyVisited(dfs, graph[goal]);
                        if (notSearch == -1) break;
                        dfs.remove(notSearch);//ゴールへの経路じゃないものを削除
                    } while (true);
                    return dfs; //ゴールにたどり着いたら処理終了
                }
            }
            //本来の処理であればif()とdfs.pop()はいらない
            if (checkAllVisited(currentNode))
                dfs.pop();
        }
        return dfs;
    }

    static int onlyVisited(Stack<NodeM> dfs, NodeM goal) {
        for (int i = 0; i < dfs.size(); i++) {
            if (dfs.get(i).visit != Visit.探索中 && dfs.get(i) != goal) return i;
        }
        return -1;
    }

    static boolean checkAllVisited(Node node) {
        for (Node n : node.branch) {
            if (n == node.from) continue;
            if (n.visit != Visit.探索済)
                return false;
        }
        node.visit = Visit.探索済;
        if (debug) System.out.println(node.visit + ":" + node);
        return true;
    }

    static NodeM[] setData() {
        NodeM[] graph = new NodeM[17];
        graph[0] = new NodeM("01", 0, 0);
        graph[1] = new NodeM("02", 4, 0);
        graph[2] = new NodeM("03", 1, 1);
        graph[3] = new NodeM("04", 2, 1);
        graph[4] = new NodeM("05", 3, 1);
        graph[5] = new NodeM("06", 4, 1);
        graph[6] = new NodeM("07", 0, 2);
        graph[7] = new NodeM("08", 2, 2);
        graph[8] = new NodeM("09", 3, 2);
        graph[9] = new NodeM("10", 4, 2);
        graph[10] = new NodeM("11", 1, 3);
        graph[11] = new NodeM("12", 2, 3);
        graph[12] = new NodeM("13", 3, 3);
        graph[13] = new NodeM("14", 0, 4);
        graph[14] = new NodeM("15", 2, 4);
        graph[15] = new NodeM("16", 3, 4);
        graph[16] = new NodeM("17", 4, 4);
        setBranch(graph, 0, 1);
        setBranch(graph, 1, 5);
        setBranch(graph, 0, 6);
        setBranch(graph, 6, 7);
        setBranch(graph, 6, 13);
        setBranch(graph, 7, 3);
        setBranch(graph, 7, 11);
        setBranch(graph, 3, 2);
        setBranch(graph, 3, 4);
        setBranch(graph, 11, 10);
        setBranch(graph, 11, 12);
        setBranch(graph, 12, 8);
        setBranch(graph, 8, 9);
        setBranch(graph, 9, 16);
        setBranch(graph, 16, 15);
        setBranch(graph, 13, 14);
        return graph;
    }

    static void setBranch(NodeM[] graph, int n1, int n2) {
        graph[n1].branch.add(graph[n2]);
        graph[n2].branch.add(graph[n1]);
    }

    static void printMap(NodeM[] graph, int mapX, int mapY) {
        mapX = mapX * 2 - 1;
        mapY = mapY * 2 - 1;
        String[][] map = new String[mapX][mapY];
        for (NodeM node : graph) {
            map[node.x * 2][node.y * 2] = node.toString();
            for (Node branch : node.branch) {
                NodeM b = (NodeM) branch;
                int dist = b.x - node.x;
                if (dist > 0) {//接続関係でXの差が正の時だけ関係性を表示
                    for (int i = 0, offset = 1; i < dist; i++, offset += 2) {
                        map[node.x * 2 + offset][node.y * 2] = "==";
                    }
                } else if ((dist = b.y - node.y) > 0) {//接続関係でYの差が正の時だけ関係性を表示
                    for (int i = 0, offset = 1; i < dist; i++, offset += 2) {
                        map[node.x * 2][node.y * 2 + offset] = "||";
                    }
                }
            }
        }
        for (int j = 0; j < mapY; j++) {
            for (int i = 0; i < mapX; i++) {
                if (map[i][j] == null) System.out.print("  ");
                else System.out.print(map[i][j]);
            }
            System.out.println();
        }
    }

    static int input(String prompt) {
        System.out.print(prompt + "\t->");
        return sc.nextInt();
    }
}

##Node

Node.java

import java.util.ArrayList;

public class Node{
    String name;
    Node from;
    ArrayList<Node> branch;
    Visit visit;
    Node(String name){
        this.name = name;
        branch = new ArrayList<>();
        visit = Visit.未探索;
    }

    @Override
    public String toString() {
        return getColor() + name + "\u001b[00m";
    }
    String getColor(){
        StringBuilder str = new StringBuilder("\u001b[00;");
        switch (visit){
            case 未探索:str.append("32");break;
            case 探索中:str.append("33");break;
            case 探索済:str.append("31");break;
        }
        str.append("m");
        return str.toString();
    }
}

##Visit

Visit.java

public enum Visit{
    未探索, 探索中, 探索済
}

#実行結果
実行するとコンソールにマップが表示されます

始点の名前、終点の名前、途中経過を表示するか(0 or 1)を入力します

14と15は探索しに行って、行き止まりだったので探索済みである赤色に、
03や04らは探索する前にゴールが見つかったので、見探索の緑色に、
06や17らは探索途中なので、黄色になっています

#まとめ
今回は深さ優先探索のLIFO方式で行い、無事探索することができました
他にはFIFO方式で探索する方法もありますが、やってないので書きません
今回苦労した点は以下になります

• 文字の色付け
• マップの接続関係表示

探索アルゴリズムに全く関係ありません。本当にありがとうございました。

#次回作

[Processing]ダイクストラ法の探索を可視化