がりらぼ

WindowsRuntimeの応援ブログ

C#で横型探索

横型探索

前回、縦型探索を用いて迷路問題を解きました。

迷路問題を状態空間表現で表してみる - がりらぼ

C#で縦型探索 - がりらぼ

今回は同じ迷路問題を横型探索を用いて解きます。

横型探索とは、幅優先探索とも呼ばれ、ひたすら突き進んだ先にゴールがあるかもしれないと考えている縦型探索とは違い、めっちゃ分岐あるけどもしかしたら自分の近くにゴールがあるかもしれないという考えの元探索を行う方法です。(意味不 縦型探索と同じように網羅的探索法の一種です。

まずスタート地点は1から始まります。

f:id:garicchi:20140529060130p:plain

次に分岐点に来るので、すべての経路に進みます。

f:id:garicchi:20140529060201p:plain

さらに進みます。幅優先探索は分岐が起きるたびに探索範囲が増えます。 このとき、3に到達した探索は行き止まりなので3の経路に関してはこれ以上調べません。

f:id:garicchi:20140529060241p:plain

さらに分岐です。 分岐ですべての経路を探索するのでその中にゴール状態の7があるので探索終了です。

f:id:garicchi:20140529060356p:plain

幅優先探索は分岐点が起きるたびに探索範囲が指数的に増えていくので非常に多くのメモリ空間と処理時間を必要とします。 しかし、上図の5分岐点のように縦型探索ならば6に行ってバックトラック8にいってバックトラック、7にいって初めてゴール という手順を踏まなくても5分岐から1発でゴール状態をみつけられるので場合によっては探索が速いです。 さらに、縦型探索のようなバックトラック機構を作らなくても良いのでアルゴリズムとしては簡単です。

アルゴリズム

①現在の状態に適用可能なルールをすべて調べる

②適用可能なルールがなければ終了、適用可能なルールがあればすべてのルールを適用し新しい状態集合を取得

③新しい状態集合の中にゴール状態があれば終了、なければ新しい状態集合を現在の状態集合にして①に戻る。

プログラムは前々回作成したState.cs、Problem.cs、Rule.csが必要です。

BreadthFirstSearch.cs

メンバは迷路問題を表すProblemクラスのインスタンスと現在の状態集合を表すStateクラスのコレクションだけです。 Executeメソッドで探索実行します。 ISearchインターフェースを実装していますがExecuteメソッドがあるだけなのでいらないです。

//幅優先探索
public class BreadthFirstSearch:ISearch
{
    //現在考える問題
    Problem CurrentProblem { get; set; }
    //現在の状態集合
    IList<State> CurrentStateList { get; set; }

    public BreadthFirstSearch(Problem problem)
    {
        this.CurrentProblem = problem;
        CurrentStateList = new List<State>();
        //状態集合を初期状態にする
        CurrentStateList.Add(problem.BeginState);
    }



    public bool Execute()
    {
        Console.WriteLine(string.Join("-", CurrentStateList.Select(q=>q.ValueList["x"])));

        while (true)
        {
            IList<State> newStateList = new List<State>();
            //現在の状態集合各々に適用できるルールをすべて適用して新しい状態集合を作る
            foreach (State state in CurrentStateList)
            {
                //この状態に適用できるルールのリスト
                var canApplyRuleList = CurrentProblem.RuleList.Where(q => state.IsApplyRule(q)).ToList();
                
                foreach (Rule rule in canApplyRuleList)
                {
                    //ルールを適用して新しい状態集合に追加
                    State s = new State(state);
                    s.ApplyRule(rule);
                    newStateList.Add(s);
                }
            }
            //新しい状態集合が何もつくれなかったら終了
            if (newStateList.Count == 0)
            {
                return false;
            }
            //現在の状態集合を新しい状態集合でおきかえる
            CurrentStateList = newStateList;

            Console.WriteLine(string.Join("-", CurrentStateList.Select(q => q.ValueList["x"])));
            //ゴール状態とどれか一つでも一致したら
            if (CurrentStateList.Any(q => CurrentProblem.EndState.Compare(q)))
            {
                //現在の状態をゴール状態にして終了
                CurrentProblem.CurrentState = CurrentStateList.Single(q => CurrentProblem.EndState.Compare(q));
                return true;
            }
        }
        
    }
}

Program.cs

Main関数があるエントリポイントです。 前回と同じように迷路問題のルールを記述してBreadthFirstSearchのインスタンスを作成してExecuteメソッドを実行してるだけです。

class Program
{
    static void Main(string[] args)
    {
        //最初の状態
        State beginState = new State();
        beginState.ValueList.Add("x", "1");

        //ゴール状態
        State endState = new State();
        endState.ValueList.Add("x","8");

        //ルール

        Rule rule1 = new Rule("Rule1",(state) => state.ValueList["x"]=="1", (state) => state.ValueList["x"] = "2");

        Rule rule2 = new Rule("Rule2", (state) => state.ValueList["x"] == "2", (state) => state.ValueList["x"] = "3");

        Rule rule3 = new Rule("Rule3", (state) => state.ValueList["x"] == "1", (state) => state.ValueList["x"] = "4");

        Rule rule4 = new Rule("Rule4", (state) => state.ValueList["x"] == "4", (state) => state.ValueList["x"] = "5");

        Rule rule5 = new Rule("Rule5", (state) => state.ValueList["x"] == "5", (state) => state.ValueList["x"] = "6");

        Rule rule6 = new Rule("Rule6", (state) => state.ValueList["x"] == "5", (state) => state.ValueList["x"] = "7");

        Rule rule7 = new Rule("Rule7", (state) => state.ValueList["x"] == "5", (state) => state.ValueList["x"] = "8");
        
        //ルールのリスト
        var ruleList = new List<Rule>{
            rule1,rule2,rule3,rule4,rule5,rule6,rule7
        };

        //迷路問題をつくる
        Problem problem = new Problem(beginState, endState, ruleList);

        ISearch search = new DepthFirstSearch(problem);
        search.Execute();


        //出力
        Console.WriteLine("Current End State x={0}", problem.CurrentState.ValueList["x"]);
        Console.WriteLine("Begin State x={0}", beginState.ValueList["x"]);
        Console.WriteLine("Goal End State x={0}", endState.ValueList["x"]);
    }
}

実行結果

実行してみるとちゃんと上図のアルゴリズム通り探索していることがわかります。 縦型探索より計算量は少ないですが、メモリ内に所持しなければいけない状態が多いのでケースバイケースで使い分ける必要があります。

f:id:garicchi:20140529061623p:plain