AI_codes

ai_codes.java

// Main.java

public class Main {

    public static void main(String[] args) {
        System.out.println("----- BFS -----");
        BFS bfs = new BFS();
        bfs.search();
        Graph.printCourse(bfs.getCourse());
        System.out.println("----- DFS -----");
        DFS dfs = new DFS();
        dfs.search();
        Graph.printCourse(dfs.getCourse());
        System.out.println("----- IDDFS -----");
        IDDFS iddfs = new IDDFS();
        iddfs.search();
        Graph.printCourse(iddfs.getCourse());
    }
}

// Graph.java

public class Graph {
    public static final int[][] STATE_SPACE = {
            {0,1,1,0,0,0,0,0,0,0},
            {0,0,1,0,0,0,1,0,0,0},
            {0,0,0,1,0,0,1,1,0,0},
            {0,0,0,0,1,0,0,1,1,0},
            {0,0,0,0,0,0,0,0,1,0},
            {0,1,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,1,0,1,0,0},
            {0,0,0,0,0,0,0,0,1,1},
            {0,0,0,0,0,0,0,0,0,1},
            {0,0,0,0,0,0,0,0,0,0}
    };

    public static final String[] STATE_NAME = {
            "S", "A", "B", "C", "D", "E", "F", "H", "I", "G"
    };

    public static final int GOAL = 9;

    public static void printOpen(ArrayDeque open) {
        System.out.print("OPEN:[");
        for(Object o : open) {
            System.out.print(Graph.STATE_NAME[(int) o] + ", ");
        }
        System.out.println("]");
    }

    public static void printClosed(List<Integer> closed) {
        System.out.print("CLOSED:[");
        for(int i : closed) {
            System.out.print(Graph.STATE_NAME[i] + ", ");
        }
        System.out.println("]");
    }

    public static void printCourse(List<Integer> course) {
        System.out.print("COURSE:[");
        for(int i = course.size()-1; i>0; i--) {
            int node = course.get(i);
            System.out.print(Graph.STATE_NAME[node] + ", ");
        }
        System.out.println("]");
    }
}

// BFS.java

public class BFS {

    private ArrayDeque mOpen = new ArrayDeque();
    private List<Integer> mClosed = new ArrayList<>();
    private int[] mParents = new int[10];
    private List<Integer> mCourse = new ArrayList<>();

    public BFS() {
        mOpen.offer(0);
    }

    public List<Integer> getCourse() {
        return mCourse;
    }

    /**
     * 幅優先探索を実行する．成功でtrue，失敗でfalse
     * @return
     */
    public boolean search() {
        while(!mOpen.isEmpty()) {
            Graph.printOpen(mOpen);
            Graph.printClosed(mClosed);
            int current = (int)mOpen.poll();
            if(current == Graph.GOAL) {
                mCourse.add(9);
                mCourse.add(current);
                int parent = mParents[current];
                while(parent != 0) {
                    mCourse.add(parent);
                    parent = mParents[parent];
                }
                mCourse.add(0);
                return true;
            }
            mClosed.add(current);
            int[] neighbors = Graph.STATE_SPACE[current];
            for(int i = 0; i < neighbors.length; i++) {
                int connect = neighbors[i];
                if(connect == 1) {
                    if(!mOpen.contains(i) && !mClosed.contains(i)) {
                        mParents[i] = current;
                        if (i == Graph.GOAL) {
                            mOpen.addFirst(i);
                        } else {
                            mOpen.offer(i);
                        }

                    }
                }
            }
        }
        return false;
    }


}

// DFS.java

public class DFS {

    private ArrayDeque mOpen = new ArrayDeque();
    private List<Integer> mClosed = new ArrayList<>();
    private int[] mParents = new int[10];
    private List<Integer> mCourse = new ArrayList<>();

    public DFS() {
        mOpen.push(0);
    }

    public List<Integer> getCourse() {
        return mCourse;
    }

    /**
     * 深さ優先探索を実行する．成功でtrue，失敗でfalse
     * @return
     */
    public boolean search() {
        while(!mOpen.isEmpty()) {
            Graph.printOpen(mOpen);
            Graph.printClosed(mClosed);
            int current = (int)mOpen.pop();
            if(current == Graph.GOAL) {
                mCourse.add(9);
                mCourse.add(current);
                int parent = mParents[current];
                while(parent != 0) {
                    mCourse.add(parent);
                    parent = mParents[parent];
                }
                mCourse.add(0);
                return true;
            }
            mClosed.add(current);
            int[] neighbors = Graph.STATE_SPACE[current];
            for(int i = 0; i < neighbors.length; i++) {
                int connect = neighbors[i];
                if(connect == 1) {
                    if(!mOpen.contains(i) && !mClosed.contains(i)) {
                        mParents[i] = current;
                        if (i == Graph.GOAL) {
                            mOpen.addFirst(i);
                        } else {
                            mOpen.push(i);
                        }
                    }
                }
            }
        }
        return false;
    }
}

// IDDFS.java

public class IDDFS {

    private ArrayDeque mOpen = new ArrayDeque();
    private List<Integer> mClosed = new ArrayList<>();
    private int[] mDepths = {0,0,0,0,0,0,0,0,0,0};
    private int[] mParents = new int[10];
    private List<Integer> mCourse = new ArrayList<>();

    public IDDFS() {
        mOpen.push(0);
    }

    public List<Integer> getCourse() {
        return mCourse;
    }


    /**
     * 反復深化探索を実行する．成功でtrue，失敗でfalse
     * @return
     */
    public boolean search() {
        int cutoff = 1;
        while(cutoff < 100) {
            System.out.println("----- cutoff=" + String.valueOf(cutoff) + " -----");
            while(!mOpen.isEmpty()) {
                Graph.printOpen(mOpen);
                Graph.printClosed(mClosed);
                int current = (int)mOpen.pop();
                if(current == Graph.GOAL) {
                    mCourse.add(9);
                    mCourse.add(current);
                    int parent = mParents[current];
                    while(parent != 0) {
                        mCourse.add(parent);
                        parent = mParents[parent];
                    }
                    mCourse.add(0);
                    return true;
                }
                mClosed.add(current);
                int[] neighbors = Graph.STATE_SPACE[current];
                for(int i = 0; i < neighbors.length; i++) {
                    int connect = neighbors[i];
                    if(connect == 1) {
                        if(!mOpen.contains(i) && !mClosed.contains(i)) {
                            mParents[i] = current;
                            mDepths[i] = mDepths[current] + 1;
                            if (mDepths[i] <= cutoff) {
                                if (i == Graph.GOAL) {
                                    mOpen.addFirst(i);
                                } else {
                                    mOpen.push(i);
                                }
                            }
                        }
                    }
                }
            }
            cutoff++;
            reset();
        }
        return false;
    }

    private void reset() {
        mOpen = new ArrayDeque();
        mClosed = new ArrayList<>();
        mOpen.push(0);
    }
}