August 2008

- 再帰による幅優先探索

Actionscriptで、迷路の最短距離の解が必要になり、

幅優先探索アルゴリズムを使用してみることに。

幅優先探索

下記の仕様で迷路配列を定義する。

// 0 : 道ID
// 1 : 壁ID

private const maze_ary:Array=[
[1,0,1,1,1,1,1,1],
[1,0,0,0,0,0,0,1],
[1,1,1,0,1,1,0,1],
[1,1,1,1,1,1,0,1]
]

// 5 : 探索済みID
private static const PASSED_ID:uint=5;

1. 探索を開始する。

まず空のキュー配列を作成し、

探索を開始する最初のマスのMassインスタンスを追加する。

※すべてのMassインスタンスは、
観測者、リレー走者みたいなものと、考えるとわかりやすい。
最初のMassインスタンスは、スタート走者とイメージできる。

迷路探索と最適解

※すべてのMassインスタンスは、
自分のマス情報であるrow , colプロパティと、
探索開始から、自分のマスにたどり着いたまでの
経路massList_aryを保持している。
つまり最初のMassインスタンス（スタート走者）に渡すmassList_aryは、空である。

※Massインスタンスは、コンストラクタで、
与えられたmassList_aryをコピーし、自分のMass情報
{row : row , col : col}を、コピーしたmassList_aryに追加する。

2.再帰処理を行う。

キュー配列からqueue_ary[0]のMassインスタンスを取り出す。

このインスタンスをcurrentMassと呼ぶとする。

currentMassのrow,colを調べ、左右上下で
キュー配列に追加すべき、移動可能なマスを探す。

ここでもし、移動可能なマスが、

すでに経由済みのマスであれば追加しない。

上記2つの条件を満たす場合、その移動可能なマスのMassインスタンスを作成し、
キュー配列に追加する。
この時、作成されるnextMassインスタンスのコンストラクタで、
currentMassインスタンスが保持している経由配列massList_aryを渡す。
これでnextMassインスタンスは、今までの経路を知っている。

（次の走者にバトンを渡す。バトンを渡す際は必ず、
自分に辿りつくまでに経由した各走者の位置配列を渡すことで、
現在の走者はどの経路を通ってバトンが渡ってきたか
を常に知っていることになる。）

左右上下調べ、キュー配列に、有効なMassインスタンスをすべて追加後、
maze_ary[currentMass.col-1][currentMass.row-1]=PASSED_ID
とし、すでに経由済みMassであることを記憶する。

不要になったcurrentMassインスタンスをキュー配列から削除し、
キュー配列に追加されているnextMassインスタンスに、委ねる。

ここでキュー配列を調べ、空でなければ 2. を繰り返す。

最初にゴールを見つけたMassインスタンスが、
最短経路massList_aryを保持していることになる。

ゴールが見つかった時点で、再帰処理をストップする。

※ここで重要なことは、
左右上下調べ、queue_aryに追加後
再帰処理を行うことだ。

でなければ、迷路に広いスペースがあった場合、
必ずしも最短距離を導き出してくれるとは限らない。

以上を、Actionscriptでプログラミングする。

----------------------------------------------------------------

MazeConfigクラスは、迷路の定数などを保持する。
MazeDataクラスは、迷路状況(どのマスに今いるかなど)
とMazeConfigクラスの一部のデータを保持する。
Massクラスは、MazeUtilsの内部クラス。

package utils
{

    import data.MazeConfig;
    import data.MazeData;

    public class MazeUtils
    {

        public static var queue_ary:Array;

        public static var maze_ary:Array;

        public static var COL:uint=MazeData.COL;

        public static var ROW:uint=MazeData.ROW;

        public static var goalRow:uint=MazeData.goalRow;

        public static var goalCol:uint=MazeData.goalCol;

        public static var startRow:uint=MazeData.startRow;

        public static var startCol:uint=MazeData.startCol;

        private static var goalInfo:Array;

        public static var PASSED_ID:uint=5;

        /**
         * 現在の位置からゴールまでの最短距離の配列を返却します。
         *
         * @return
         *
         */
        public static function get goalList():Array{
            goalInfo=null;

            startRow=MazeData.currentRow;
            startCol=MazeData.currentCol;

            maze_ary=MazeData.copyInfo;

            queue_ary=[];
            queue_ary[0]=new Mass(startRow , startCol , []);

            check();

            return goalInfo;
        }

        private static function check():void{
            var currentMass:Mass=queue_ary[0];
            queue_ary.shift();
　　　　　　　　　　
           if(maze_ary[currentMass.col-1][currentMass.row-1]==PASSED_ID){
           return;
           }

            maze_ary[currentMass.col-1][currentMass.row-1]=PASSED_ID;
           if(goalInfo!=null){
                   //最短距離が見つかっているので、残りのmassでは、何もしない。
            }else if(currentMass.isGoal){
                   //ゴールの最短距離を見つけた。
                goalInfo=currentMass.massList;
            }else{
                var nextMass:Mass;

                //前方
                if(needCheck(currentMass.row , currentMass.col+1)){
                    nextMass=new Mass(currentMass.row , currentMass.col+1 , currentMass.massList);
                    queue_ary.push(nextMass);
                  //ここで、check関数を実行してしまうと最短距離でなくなる可能性がある。
                }

                //後方
                if(needCheck(currentMass.row , currentMass.col-1)){
                    nextMass=new Mass(currentMass.row , currentMass.col-1 , currentMass.massList);
                    queue_ary.push(nextMass);
                }

                //左方
                if(needCheck(currentMass.row-1 , currentMass.col)){
                    nextMass=new Mass(currentMass.row-1 , currentMass.col , currentMass.massList);
                    queue_ary.push(nextMass);
                }

                //右方
                if(needCheck(currentMass.row+1 , currentMass.col)){
                    nextMass=new Mass(currentMass.row+1 , currentMass.col , currentMass.massList);
                    queue_ary.push(nextMass);
                }

                currentMass=null;

                if(queue_ary.length==0){
                    trace("not founded");
                }else{
                    check(queue_ary);
                }
            }


        }

        /**
         * 一度も通っていない場合　&&
         * マスが存在する　&&
         * 道である場合、trueを返却します。
         *
         * @param row
         * @param col
         * @return
         *
         */
        private static function needCheck(row , col):Boolean{
            if(row>1&&row<=ROW&&col>1&&col<=COL){
                return maze_ary[col-1][row-1]==MazeConfig.ROAD_ID;
            }
            return false;
        }
    }
}

/**
* マス情報と経由配列を保持する内部クラス(観測者)
*
* @author
*
*/
import utils.MazeUtils;

class Mass{
    private var mass_ary:Array;
    private var maze_ary:Array;

    private var _row,_col:uint;

    public function Mass(row:uint,col:uint,list:Array ){
        this.mass_ary=[];

        this._row=row;
        this._col=col;

        var len=list.length;
        for(var i=0;i<len;i++){
            mass_ary.push(list[i]);
        }

        this.mass_ary.push({row:_row , col:_col});

    }

    public function get massList():Array{
        return mass_ary;
    }

    public function get isGoal():Boolean{
        return row==MazeUtils.goalRow&&col==MazeUtils.goalCol;
    }

    public function get row():uint{
        return _row;
    }

    public function get col():uint{
        return _col;
    }
}

高速化など考えると、多々改善の余地はありし。
知らんけど。

再帰による幅優先探索 > ... more

« June 2008 | Main | Archive | October 2008 »

August 2008

- 再帰による幅優先探索

- Recent Entry

- Category