元気にやっていますか?
私は相変わらず、曖昧な空白とともにふらふらする毎日です。
健体壮美なあなたのことだから大丈夫だとは思いますが、
くれぐれもお体にはお気をつけください。

2010/04/10

[Java] 迷路の最短経路出力プログラム

氏曰く、
最低でも3時間以内にこのプログラムを完成させることができないようでは、"ほぼ確実に"優秀ではない。
最低でも。
問題を読んだ。3時間でできる気が全くしない。
「袋小路にはまったら戻らなきゃダメだし・・・」
「ゴールから遠ざかる移動(回り道)が必要な場合は・・・」
こんな言葉が頭の中をグルグルと回るばかり。
僕はたぶん優秀ではないのだ・・・と、会ったこともない人間の評価を鵜呑みにして軽く落ち込みながら、 コメントやトラックバックの完成させた人たちのプログラムをいくつか読んだ。それでもわからない。というかC言語の複雑なアルゴリズムを読み解こうという気が起きない。文法は単純なものがばかりだが、何せアルゴリズムが複雑(に見える)。
この時点でわかったこと。
解法がわかっている人は、プログラムを作ることができる。
しかし、解法がわからない人は、正解プログラムを読んでも理解できない。(できなくはないが、めんどくさい。)

コメントやトラックバックからするとダイクストラ法とかA*(エースター)というアルゴリズムを使えばできるとのこと。
全くできないのは癪なので、そのアルゴリズムの理解から始めた。
取り組み始めて5時間、なんとか完成させることができた。
import java.io.*;
import java.util.*;

public class Maze {
    String MAZE_FILE = "C:/Temp/Maze.txt";
    //迷路のサイズ
    int width = 0;
    int length = 0;
    //スタート地点・ゴール地点
    int start_x = 0;
    int start_y = 0;
    int goal_x = 0;
    int goal_y = 0;
    //オープンしている(=到達可能性のある)ブロックのリスト
    List openList = new ArrayList();
    
    public static void main(String[] args) throws Exception {
        new Maze().search();
    }

    /**
     * 探索実行
     */
    private void search() throws Exception {
        //迷路テキスト読み込み
        BufferedReader reader = 
                new BufferedReader(
                    new FileReader(new File(MAZE_FILE)));
        List lineList = new ArrayList();
        String line = null;
        while ((line = reader.readLine()) != null) {
            lineList.add(line);
        }
        width = lineList.get(0).length();
        length = lineList.size();

        //迷路を2重配列に格納
        Block[][] mazeBlocks = new Block[width][length];
        for (int y = 0; y < lineList.size(); y++) {
            for(int x = 0; x < lineList.get(y).length(); x++) {
                mazeBlocks[x][y] = new Block();
                String block = lineList.get(y).substring(x, x + 1);
                if (" ".equals(block)) {
                    
                } else if ("*".equals(block)) {
                    mazeBlocks[x][y].wall = true;
                } else if ("S".equals(block)) {
                    mazeBlocks[x][y].start = true;
                    start_x = x;
                    start_y = y;
                } else if ("G".equals(block)) {
                    mazeBlocks[x][y].goal = true;
                    goal_x = x;
                    goal_y = y;
                }
                mazeBlocks[x][y].x = x;
                mazeBlocks[x][y].y = y;
            }
        }

        //各ブロックのゴールまでの最短移動距離を算出・格納
        for (int y = 0; y < length; y++) {
            for (int x = 0; x < width; x++) {
                mazeBlocks[x][y].expected = Math.abs(goal_x - x) + Math.abs(goal_y - y);
            }
        }
        
        //スタート地点をオープン
        mazeBlocks[start_x][start_y].cost = 0;
        openList.add(mazeBlocks[start_x][start_y]);
        
        //探索開始
        while (true) {
            //スタートからゴールまでの期待値が最小のものから順次探索する
            Block now = getShortestOpenBlock();
            now.stamped = true;

            //現在地点がゴールに隣接していたら探索終了
            if (now.x + 1 == goal_x &&
                    now.y == goal_y) {
                mazeBlocks[goal_x][goal_y].parent = now;
                break;
            } else if (now.x == goal_x &&
                    now.y + 1 == goal_y) {
                mazeBlocks[goal_x][goal_y].parent = now;
                break;
            } else if (now.x - 1 == goal_x &&
                    now.y == goal_y) {
                mazeBlocks[goal_x][goal_y].parent = now;
                break;
            } else if (now.x == goal_x &&
                    now.y - 1 == goal_y) {
                mazeBlocks[goal_x][goal_y].parent = now;
                break;
            }
            
            //現在地点の四方のうち、進めるブロックをオープンリストに追加
            if (now.x + 1 <= width &&
                    !mazeBlocks[now.x + 1][now.y].wall &&
                    !mazeBlocks[now.x + 1][now.y].stamped) {
                mazeBlocks[now.x + 1][now.y].parent = now;
                openList.add(mazeBlocks[now.x + 1][now.y]);
            }
            if (now.x - 1 >= 0 &&
                    !mazeBlocks[now.x - 1][now.y].wall &&
                    !mazeBlocks[now.x - 1][now.y].stamped) {
                mazeBlocks[now.x - 1][now.y].parent = now;
                mazeBlocks[now.x - 1][now.y].cost = now.cost + 1;
                openList.add(mazeBlocks[now.x - 1][now.y]);
            }
            if (now.y + 1 <= length &&
                    !mazeBlocks[now.x][now.y + 1].wall &&
                    !mazeBlocks[now.x][now.y + 1].stamped) {
                mazeBlocks[now.x][now.y + 1].parent = now;
                mazeBlocks[now.x][now.y + 1].cost = now.cost + 1;
                openList.add(mazeBlocks[now.x][now.y + 1]);
            }
            if (now.y - 1 >= 0 &&
                    !mazeBlocks[now.x][now.y - 1].wall &&
                    !mazeBlocks[now.x][now.y - 1].stamped) {
                mazeBlocks[now.x][now.y - 1].parent = now;
                mazeBlocks[now.x][now.y - 1].cost = now.cost + 1;
                openList.add(mazeBlocks[now.x][now.y - 1]);
            }
        }
        
        //ゴールからスタートまでの道のりをマーキング
        Block parent =mazeBlocks[goal_x][goal_y].parent;
        while (true) {
            if (parent.start == false) {
                parent.correct = true;
                parent = parent.parent;
            } else {
                break;
            }
        }
        
        //正解を出力
        for (int y = 0; y < length; y++) {
            for (int x = 0; x < width; x++) {
                Block block = mazeBlocks[x][y];
                if (block.wall) {
                    System.out.print("*");
                } else if (block.start) {
                    System.out.print("S");
                } else if (block.goal) {
                    System.out.print("G");
                } else if (block.correct) {
                    System.out.print("$");
                } else {
                    System.out.print(" ");
                }
            }
            System.out.println();
        }
    }

    /**
     * オープンされているブロックのうち、最小コストのブロックを返却する
     * @return 最小コストのブロック
     */
    private Block getShortestOpenBlock() throws Exception {
        if (openList.size() == 0) {
            throw new Exception("ゴールへ辿り着く道はありません。");
        }
        Block shortest = null;
        int index = 0;
        for (int i = 0; i < openList.size(); i++) {
            if (shortest == null || 
                    shortest.getPoint() >= openList.get(i).getPoint()) {
                shortest = openList.get(i);
                index = i;
            }
        }
        return openList.remove(index);
    }

    /**
     * 迷路の1コマを表すインナークラス
     */
    private class Block {
        //座標
        int x;
        int y;
        //スタート地点か否か
        boolean start = false;
        //ゴール地点か否か
        boolean goal = false;
        //壁か否か
        boolean wall = false;
        //正解の軌道か否か
        boolean correct = false;
        //探索済みか否か
        boolean stamped = false;
        //スタート地点からの移動距離
        int cost;
        //ゴールまでの最短移動距離
        int expected;
        //スタートからゴールまでの最小期待値
        int getPoint() {
            return cost + expected;
        }
        //親ブロック
        Block parent = null;
    }
}
ふーむ、これを30分とか1時間で完成させる人がいるのか・・・。
まあ、そういう人は類似した問題を解いたことがあるのだろうが、それにしても速い。
たぶんそういう人が、↓こんな風に巨額を稼ぎ出すエンジニアになるんだろうな。
ITアントレプレナーになりたい若者のみなさんはプログラミングを習得しましょう - On Off and Beyond

0 件のコメント:

コメントを投稿