ヽ｜∵｜ゝ(Fantom) の 開発blog？

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.HashSet;

public class FifteenPuzzleAstar {

    public static void main(String[] args) throws Exception {
        new FifteenPuzzleAstar();
    }

    //４方向探索用
    static final int[] dx = { 0, 1, 0, -1};
    static final int[] dy = {-1, 0, 1,  0};
    static final char[] dir = {'u', 'r', 'd', 'l'};

    static final int N = 4;          //盤サイズ
    static final int NN = N * N;     //パネル総数

    //各パネルのマンハッタン距離のテーブル
    static final int[][] MDTable = new int[NN][NN];
    static {
        for (int i = 0; i < NN; i++) {
            for (int j = 0; j < NN; j++) {
                MDTable[i][j] = getManhattanDistance(i % N, i / N, j % N, j / N);
            }
        }
    }

    //マンハッタン距離を求める
    static int getManhattanDistance(int x1, int y1, int x2, int y2) {
        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
    }

    public FifteenPuzzleAstar() {

        int[][] board = new int[][]{    //初期の盤の状態
            { 1, 7, 2, 4},
            { 6, 0,14, 3},
            {13,10,11, 8},
            { 5, 9,15,12},
        };  //rrdllldruuurdllddrurrd 22(手)

        String ans = astar(board);
        System.out.println(ans);
        System.out.println(ans.length());
    }

    //A*(A-star)で15パズルを解く
    String astar(int[][] board) {
        Set<String> done = new HashSet<String>();    //既出パターンチェック用
        Queue<Puzzle> q = new PriorityQueue<Puzzle>();

        Puzzle p = new Puzzle();
        p.setBoard(board);        //初期の盤の状態をセットする
        p.estimate = p.md;        //推定値
        q.add(p);
        done.add(p.toString());

        while (!q.isEmpty()) {
            p = q.poll();
            if (p.md == 0) {      //全てのパネルが揃ったら０
                return p.path;    //空白の移動経路
            }

            done.add(p.toString());
            int sx = p.space % N;    //空白の位置
            int sy = p.space / N;

            for (int i = 0; i < dx.length; i++) {
                int nx = sx + dx[i];    //空白の移動位置
                int ny = sy + dy[i];
                if (nx < 0 || N <= nx || ny < 0 || N <= ny) {    //範囲外
                    continue;
                }

                Puzzle p2 = p.clone();
                p2.changeSpace(nx, ny);   //空白と数字パネルを入れ替える（スライドする）
                if (!done.contains(p2.toString())) {    //既出パターンチェック
                    p2.cost++;            //手数
                    p2.estimate = p2.md + p2.cost;    //推定値
                    //p2.estimate = p2.md;    //推定値（実行速度を優先したいときはこっちにする）
                    p2.path += dir[i];    //空白の移動経路(移動方向の記録)
                    q.add(p2);
                }
            }
        }

        return "unsolvable";    //完成できなかったとき
    }

    //パズルの状態を保存する構造体（クラス）
    class Puzzle implements Cloneable, Comparable<Puzzle> {
        int[] panel = new int[NN];    //各位置にあるパネル番号(番号は１ベース)
        int space;                    //空白のインデクス
        int md;                       //全パネルのマンハッタン距離の合計
        int cost;                     //手数
        int estimate;                 //推定値
        String path = "";             //空白の移動経路(移動方向の記録)

        //盤の並びをセットする
        void setBoard(int[][] board) {
            int p = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (board[i][j] == 0) {   //空白
                        panel[p] = NN;        //空白は最大値にする
                        space = p;            //空白のインデクス
                    } else {
                        panel[p] = board[i][j];
                    }
                    p++;
                }
            }

            calcMD();    //全パネルのマンハッタン距離の合計を求める
        }

        //全パネルのマンハッタン距離の合計を求める
        void calcMD() {
            md = 0;
            for (int i = 0; i < NN; i++) {
                if (panel[i] != NN) {        //空白は除外する
                    md += MDTable[i][panel[i] - 1];    //番号は１ベース
                }
            }
        }

        //空白と数字パネルを入れ替える（スライドする）
        void changeSpace(int x, int y) {
            int index = x + y * N;           //インデクスに変換
            md += MDTable[space][panel[index] - 1];    //全パネル距離合計から移動後の数字パネル距離を足す(差分計算)
            md -= MDTable[index][panel[index] - 1];    //全パネル距離合計から現在の数字パネル距離を引く
            panel[space] = panel[index];    //数字パネルを交換(スライド)
            panel[index] = NN;              //空白を交換
            space = index;                  //空白のインデクス更新
        }

        //比較関数
        @Override
        public int compareTo(Puzzle o) {
            return this.estimate - o.estimate;    //推定値で小さい順
        }

        //盤の状態を文字列にする（既出パターンのキーとしても利用）
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder(NN * 3);
            for (int i = 0; i < NN; i++) {
                if (i > 0) {
                    if (i % N == 0) {
                        sb.append("\n");
                    } else {
                        sb.append(" ");
                    }
                }
                sb.append(panel[i]);
            }
            return sb.toString();
        }

        //盤の状態を複製する
        @Override
        public Puzzle clone() {
            try {
                Puzzle obj = (Puzzle)super.clone();
                obj.panel = this.panel.clone();
                return obj;
            } catch (CloneNotSupportedException e) {
                throw new RuntimeException();
            }
        }
    }
}

import java.util.PriorityQueue;
import java.util.Queue;

public class MazeShortestAstar {

    public static void main(String[] args) throws Exception {
        new MazeShortestAstar();
    }

    static final int INF = Integer.MAX_VALUE;    //INF値

    //４方向探索用
    static final int[] dx = { 0, 1, 0, -1};
    static final int[] dy = {-1, 0, 1,  0};
    static final char[] dir = {'u', 'r', 'd', 'l'};

    String path = "";    //移動経路(戻値用)

    //マンハッタン距離を求める
    static int getManhattanDistance(int x1, int y1, int x2, int y2) {
        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
    }
    //チェビシェフ距離を求める
    static int getChevyshevDistance(int x1, int y1, int x2, int y2) {
        return Math.max(Math.abs(x1 - x2), Math.abs(y1 - y2));
    }

    public MazeShortestAstar() {

        int n = 10;    //↓方向
        int m = 10;    //→方向
        String[] maze = new String[]{
            "S..#...#..",
            ".#.#.#.#.#",
            "...#.#....",
            "##...#.##.",
            ".....#.#..",
            ".#####.#.#",
            ".......#..",
            "##.######.",
            "...#...#..",
            ".#...#...G",
        };

        int ans = astar(n, m, maze);
        System.out.println(ans);
        System.out.println(path);
    }

    //A*(A-star)探索アルゴリズム
    int astar(int n, int m, String[] maze) {
        int[][] grid = new int[n][m];    //移動コスト(距離)の記録
        int sx, sy, gx, gy;              //スタートとゴール位置
        sx = sy = gx = gy = 0;

        //迷路データのパース
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (maze[i].charAt(j) == '#') {
                    grid[i][j] = -1;       //壁
                } else if (maze[i].charAt(j) == 'S') {
                    grid[i][j] = 0;        //スタートは距離０
                    sy = i;
                    sx = j;
                } else if (maze[i].charAt(j) == 'G') {
                    grid[i][j] = INF;
                    gy = i;
                    gx = j;
                } else {
                    grid[i][j] = INF;
                }
            }
        }

        //A*(A-star) 探索
        Queue<Position> q = new PriorityQueue<Position>();

        Position p = new Position(sx, sy);
        p.estimate = getManhattanDistance(sx, sy, gx, gy);    //推定値
        q.add(p);

        while (!q.isEmpty()) {
            p = q.poll();
            if (p.cost > grid[p.y][p.x]) {
                continue;
            }
            if (p.y == gy && p.x == gx) {    //ゴールに到達
                path = p.path;        //移動経路(戻値用)
                break;
            }

            for (int i = 0; i < dx.length; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if (nx < 0 || m <= nx || ny < 0 || n <= ny) {    //範囲外
                    continue;
                }
                if (grid[ny][nx] > grid[p.y][p.x] + 1) {
                    grid[ny][nx] = grid[p.y][p.x] + 1;
                    
                    Position p2 = new Position(nx, ny);
                    p2.cost = grid[ny][nx];        //移動コスト(スタートからの移動量)
                    p2.estimate = getManhattanDistance(nx, ny, gx, gy) + p2.cost;    //推定値
                    p2.path = p.path + dir[i];     //移動経路(移動方向の記録)
                    q.add(p2);
                }
            }
        }

        return grid[gy][gx];    //見つからないときは INF 値になる
    }

    //位置情報の構造体
    class Position implements Comparable<Position>{
        int x;               //座標
        int y;
        int cost;            //移動コスト(スタートからの移動量)
        int estimate;        //推定値(ゴールまでのマンハッタン距離＋移動コスト)
        String path = "";    //移動経路(移動方向の記録)

        //コンストラクタ
        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }

        //比較関数
        @Override
        public int compareTo(Position o) {
            return this.estimate - o.estimate;    //推定値で小さい順
        }
    }
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class Dijkstra {

    public static void main(String[] args) throws Exception {
        new Dijkstra();
    }

    public Dijkstra() {
        //Wikipedia の例(図)をデータにしたもの
        int n = 6;    //頂点数
        int s = 0;    //スタート頂点(頂点番号は -1 されている[元は 1])
        int g = 4;    //ゴール頂点(頂点番号は -1 されている[元は 5])
        int[][] adj = new int[][]{
            //接続元ノード, 接続先ノード, 重み
            {0, 1, 7},
            {0, 2, 9},
            {0, 5, 14},
            {1, 2, 10},
            {1, 3, 15},
            {2, 3, 11},
            {2, 5, 2},
            {3, 4, 6},
            {4, 5, 9}
        };    //s:0 → g:4 のとき、答えは 20

        //隣接リスト
        @SuppressWarnings("unchecked")
        List<Edge>[] edges = new List[n];
        for (int i = 0; i < n; i++) {
            edges[i] = new ArrayList<Edge>();
        }

        for (int i = 0; i < adj.length; i++) {
            edges[adj[i][0]].add(new Edge(adj[i][0], adj[i][1], adj[i][2]));
            edges[adj[i][1]].add(new Edge(adj[i][1], adj[i][0], adj[i][2])); //無向グラフなので、逆方向も接続する
        }

        int ans = dijkstra(n, edges, s, g);
        System.out.println(ans);    //s → g の最短距離
    }

    static final int INF = 100100100;    //INF 値(十分に大きな値)

    //ダイクストラ法[単一始点最短経路(Single Source Shortest Path)]
    int dijkstra(int n, List<Edge>[] edges, int s, int g) {
        int[] distance = new int[n];        //始点からの最短距離

        Arrays.fill(distance, INF);    //各頂点までの距離を初期化(INF 値)
        distance[s] = 0;    //始点の距離は０

        Queue<Edge> q = new PriorityQueue<Edge>();
        q.add(new Edge(s, s, 0));     //始点を入れる

        while (!q.isEmpty()) {
            Edge e = q.poll();        //最小距離(cost)の頂点を取り出す
            if (distance[e.target] < e.cost) {
                continue;
            }

            //隣接している頂点の最短距離を更新する
            for (Edge v : edges[e.target]) {
                if (distance[v.target] > distance[e.target] + v.cost) {  //(始点～)接続元＋接続先までの距離    
                    distance[v.target] = distance[e.target] + v.cost;    //現在記録されている距離より小さければ更新
                    q.add(new Edge(e.target, v.target, distance[v.target]));  //始点～接続先までの距離    
                }
            }
        }

        return distance[g];    //到達できなかったときは、INF となる
    }

    //辺情報の構造体
    class Edge implements Comparable<Edge> {
        public int source = 0;    //接続元ノード
        public int target = 0;    //接続先ノード
        public int cost = 0;      //重み

        public Edge(int source, int target, int cost) {
            this.source = source;
            this.target = target;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return this.cost - o.cost;    //重みの小さい順
        }

        @Override
        public String toString() {    //デバッグ用
            return "source = " + source + ", target = " + target + ", cost = " + cost;
        }
    }
}

・・・（略）・・・
import java.util.Collections;

public class Dijkstra {
    ・・・（略）・・・
    public Dijkstra() {
        ・・・（略）・・・
        List<Edge> paths = new ArrayList<Edge>();    //選択した辺(戻値用)

        int ans = dijkstra(n, edges, s, g, paths);
        System.out.println(ans);    //s → g の最短距離

        //選択した辺(確認)
        int len = paths.size();
        for (int i = 1; i < len; i++) {    //一番最初[0]は始点のためスキップ
            System.out.println(paths.get(i));
        }
    }

    static final int INF = 100100100;    //INF 値(十分に大きな値)

    //ダイクストラ法[単一始点最短経路(Single Source Shortest Path)]
    //選択した辺を返す
    int dijkstra(int n, List<Edge>[] edges, int s, int g, List<Edge> paths) {
        int[] distance = new int[n];        //始点からの最短距離
        int[] parent = new int[n];          //接続元ノード

        Arrays.fill(distance, INF);    //各頂点までの距離を初期化(INF 値)
        distance[s] = 0;    //始点の距離は０
        Arrays.fill(parent, -1);    //-1 は始点または未到達

        Queue<Edge> q = new PriorityQueue<Edge>();
        q.add(new Edge(s, s, 0));     //始点を入れる

        while (!q.isEmpty()) {
            Edge e = q.poll();        //最小距離(cost)の頂点を取り出す
            if (distance[e.target] < e.cost) {
                continue;
            }

            //隣接している頂点の最短距離を更新する
            for (Edge v : edges[e.target]) {
                if (distance[v.target] > distance[e.target] + v.cost) {  //(始点～)接続元＋接続先までの距離
                    distance[v.target] = distance[e.target] + v.cost;    //現在記録されている距離より小さければ更新
                    q.add(new Edge(e.target, v.target, distance[v.target]));  //始点～接続先までの距離
                    parent[v.target] = e.target;	//接続元を記録
                }
            }
        }

        //選択した辺(逆から辿る[到達点→始点])
        paths.clear();
        if (parent[g] > -1) {
            int p = g;
            while (p > -1) {
                paths.add(new Edge(parent[p], p, distance[p]));
                p = parent[p];
            }
            Collections.reverse(paths);    //反転する(始点→到達点)
        }

        return distance[g];    //到達できなかったときは、INF となる
    }
    ・・・（略）・・・
}

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class Prim {

    public static void main(String[] args) throws Exception {
        new Prim();
    }

    public Prim() {
        //Wikipedia の例(図)をデータにしたもの
        int n = 7;    //頂点数
        int[][] adj = new int[][]{
            //接続元ノード, 接続先ノード, 重み
            {0, 1, 7},
            {0, 3, 5},
            {1, 2, 8},
            {1, 3, 9},
            {1, 4, 7},
            {2, 4, 5},
            {3, 4, 15},
            {3, 5, 6},
            {4, 5, 8},
            {4, 6, 9},
            {5, 6, 11}
        };    //答えは 39

        //隣接リスト
        @SuppressWarnings("unchecked")
        List<Edge>[] edges = new List[n];
        for (int i = 0; i < n; i++) {
            edges[i] = new ArrayList<Edge>();
        }

        for (int i = 0; i < adj.length; i++) {
            edges[adj[i][0]].add(new Edge(adj[i][0], adj[i][1], adj[i][2]));
            edges[adj[i][1]].add(new Edge(adj[i][1], adj[i][0], adj[i][2])); //無向グラフなので、逆方向も接続する
        }

        int ans = prim(n, edges);
        System.out.println(ans);    //最小全域木の重み
    }

    //プリム法[最小全域木(Minimum Spannig Tree)]
    int prim(int n, List<Edge>[] edges) {
        boolean[] done = new boolean[n];    //訪問フラグ

        Queue<Edge> q = new PriorityQueue<Edge>();
        q.add(new Edge(0, 0, 0));     //０から(ダミー)

        int totalCost = 0;            //最小全域木の重み
        while (!q.isEmpty()) {
            Edge e = q.poll();        //最小コストの辺を取り出す
            if (done[e.target]) {
                continue;
            }

            done[e.target] = true;        //訪問済にする
            totalCost += e.cost;
            q.addAll(edges[e.target]);    //隣接しているすべての辺を追加
        }

        return totalCost;
    }

    //辺情報の構造体
    class Edge implements Comparable<Edge> {
        public int source = 0;    //接続元ノード
        public int target = 0;    //接続先ノード
        public int cost = 0;      //重み

        public Edge(int source, int target, int cost) {
            this.source = source;
            this.target = target;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return this.cost - o.cost;
        }

        @Override
        public String toString() {    //デバッグ用
            return "source = " + source + ", target = " + target + ", cost = " + cost;
        }
    }
}

・・・（略）・・・
import java.util.LinkedList;

public class Prim {
    ・・・（略）・・・
    public Prim() {
        ・・・（略）・・・
        List<Edge> paths = new LinkedList<Edge>();    //選択した辺(戻値用)

        int ans = prim(n, edges, paths);
        System.out.println(ans);    //最小全域木の重み

        //選択した辺(確認)
        int len = paths.size();
        for (int i = 1; i < len; i++) {    //一番最初[0]はダミーのためスキップ
            System.out.println(paths.get(i));
        }
    }

    //プリム法[最小全域木(Minimum Spannig Tree)]
    //選択した辺を返す
    int prim(int n, List<Edge>[] edges, List<Edge> paths) {
        boolean[] done = new boolean[n];    //訪問フラグ

        Queue q = new PriorityQueue();
        q.add(new Edge(0, 0, 0));     //０から(ダミー)

        paths.clear();
        int totalCost = 0;            //最小全域木の重み
        while (!q.isEmpty()) {
            Edge e = q.poll();        //最小コストの辺を取り出す
            if (done[e.target]) {
                continue;
            }

            done[e.target] = true;        //訪問済にする
            totalCost += e.cost;
            paths.add(e);                 //選択した辺を記録(一番最初はダミー)
            q.addAll(edges[e.target]);    //隣接しているすべての辺を追加
        }

        return totalCost;
    }
    ・・・（略）・・・
}