読者です 読者をやめる 読者になる 読者になる

がりらぼ

WindowsRuntimeの応援ブログ

C#で縦型探索

C# 人工知能

縦型探索

前回迷路問題を状態空間表現しました。

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

これでコンピュータに迷路問題を認識させることができたのでゴールまで迷路を解かせてみましょう。 問題をコンピュータに解かせるには「探索」をつかいます。 つまりゴールまでの道のりを計算によって探させます。

今回は探索の中でも縦型探索で解いてみます。

縦型探索とは、深さ優先探索とも呼ばれ、とりあえず分岐点を直進し、行き止まりになったら前回の分岐点まで戻って別の経路を進むという方法です。

図示するとこんな感じ

とりあえず行き止まりまでいって、

f:id:garicchi:20140528104833p:plain

直前の分岐までかえる。その後次の経路を進む。

f:id:garicchi:20140528104954p:plain

また行き止まりなので分岐までかえって次の経路へ

f:id:garicchi:20140528105021p:plain

さらに行き止まりなので分岐までかえって次の経路へ。これでゴールです。

f:id:garicchi:20140528105038p:plain

このような何も考えずに総当たりで探索する方法は網羅的探索法と呼ばれ、確実に最適解にたどり着きますがそれまでの時間とメモリの消費が圧倒的に大きいです。

縦型探索は行き止まりになったときに前回の分岐点まで戻るので、分岐点情報をスタックに積んでおく必要があります。このような分岐点まで戻ることをバックトラックといいます。

アルゴリズム

縦型探索は以下のようなアルゴリズムになります。


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

②適用可能なルールがあるなら⑤へ

③適用可能なルールがないなら分岐情報スタックを見てスタックに何も分岐情報がなければ探索失敗

④スタックに分岐情報があれば現在の状態とどのルールを適用したのかを新しくスタックにpush BacktrackフラグをOnにする

⑤適用可能なルールが1つなら一本道なので最初のルールを選択する(というより1つしかルールがない)、そして⑦へ

⑥適用可能なルールが複数個なら分岐なので現在の分岐情報からまだ適用していないルールを選択

⑦BackTrackフラグがONなら現在の分岐情報に現在選択したルールをいれ、スタックにpush。 BackTrackフラグがOffなら新しい分岐情報に選択したルールをいれ、スタックにpush。

⑧選択したルールを適用して現在の状態を新しい状態にする。

⑨新しい状態がゴール状態なら終了。そうでなければ①へ


という感じだと思います。 本とかにはもっと簡単に書いてありますがこれが一番簡単に実装できたのでこんな感じにしました。

今回のプログラムは前回のProblem.cs、Rule.cs、State.csを使います。

BranchState.cs

スタックに積まれる分岐情報です。 分岐情報は初めて分岐するたびに別のインスタンスが新しく作られるコピーコンストラクタを用意しています。

メンバとしては分岐情報既に適用したことのあるルールのコレクションが入っています。

//分岐情報
public class BranchState
{
    //分岐時の状態
    public State CurrentState { get; set; }
    //この分岐で適用したルールのリスト
    public IList<Rule> AppliedRuleList { get; set; }

    public BranchState(State state)
    {
        this.CurrentState = state;
        AppliedRuleList = new List<Rule>();
    }

    //コピーコンストラクタ
    public BranchState(BranchState state)
    {
        this.CurrentState = new State(state.CurrentState);
        AppliedRuleList = new List<Rule>(state.AppliedRuleList);

    }
}

DepthFirstSearch.cs

深さ優先探索を実装するクラスです。 ISearchインターフェースとかいうのを実装していますが単純にExecuteメソッドがあるだけの単純んものです。

メンバとしては現在考えているの問題と、現在の分岐情報BranchStateのスタックがあります。 Branchのスタックは、分岐情報が入るスタックです。

Executeメソッドで探索実行します。 上記のアルゴリズム通りに実装しています。LINQめっちゃ使ってますが。

public class DepthFirstSearch:ISearch
{
    //現在考える問題
    Problem CurrentProblem{ get; set; }
    //現在の分岐情報
    BranchState CurrentBranch { get; set; }
    //分岐情報のスタック
    Stack<BranchState> BranchStack { get; set; }


    public DepthFirstSearch(Problem problem)
    {
        this.CurrentProblem = problem;
        this.CurrentBranch = null;
        this.BranchStack = new Stack<BranchState>();
    }

    public bool Execute()
    {
        Console.WriteLine("Start State x={0}", CurrentProblem.CurrentState.ValueList["x"]);

        while (true)
        {
            //適用できるルール一覧を取得する
            var applyList = CurrentProblem.RuleList.Where(q => CurrentProblem.CurrentState.IsApplyRule(q)).ToList();
            //バックトラックフラグ
            bool isBackTrack = false;
            Rule currentRule = null;

            //行き止まり
            if (applyList.Count == 0)
            {
                if (BranchStack.Count == 0)
                {
                    //行き止まりかつスタックになにも積まれてなければ終了
                    return false;
                }
                else
                {
                    //行き止まりでスタックに前回の分岐が入っているならバックトラックを開始する
                    //スタックから直前の分岐情報取得
                    CurrentBranch = new BranchState(BranchStack.Pop());
                    //現在の状態を分岐時の状態に戻す
                    CurrentProblem.CurrentState = CurrentBranch.CurrentState;
                    //適用可能ルールリストを更新する
                    applyList = CurrentProblem.RuleList.Where(q => CurrentProblem.CurrentState.IsApplyRule(q)).ToLis
                    //バックトラックフラグをいれる
                    isBackTrack = true;
                    Console.WriteLine("BackTrack");
                }
            }

            //一本道
            if (applyList.Count == 1)
            {
                //一本道はルールが一つしかない
                currentRule = applyList.First();
            }
            //分岐
            else
            {
                if (CurrentBranch == null)
                {
                    //最初の分岐用
                    currentRule = applyList.First();
                }
                else
                {
                    //現在の分岐情報からまだ適用したことがないルールを取得する
                    Rule applyRule = null;
                    foreach (var rule in applyList)
                    {
                        if (CurrentBranch.AppliedRuleList.All(q => q.Name != rule.Name))
                        {
                            applyRule = rule;
                            break;

                        }
                    }
                    currentRule = applyRule;

                }

                if (isBackTrack)
                {
                    //バックトラックからの分岐なら
                    //現在の分岐情報をスタックに入れる
                    CurrentBranch.AppliedRuleList.Add(currentRule);
                    BranchStack.Push(new BranchState(CurrentBranch));
                }
                else
                {
                    //バックトラックではない分岐なら
                    //新しく分岐情報を作成してスタックに入れる
                    CurrentBranch = new BranchState(new State(CurrentProblem.CurrentState));
                    CurrentBranch.AppliedRuleList.Add(currentRule);
                    BranchStack.Push(new BranchState(CurrentBranch));
                }
            }
            
            //ルール適用
            CurrentProblem.CurrentState.ApplyRule(currentRule);

            //出力
            Console.WriteLine("State x={0}", CurrentProblem.CurrentState.ValueList["x"]);

            //終了判定
            if (CurrentProblem.IsEnd())
            {
                return true;
            }



        }
        
    }

}

Program.cs

Main関数があるクラスです。 迷路問題の定義とDepthFirstSearchを実行します。 前回同様、初期状態は(1)ゴール状態は(8)ルールは7個あります。

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:20140528112814p:plain

この縦型探索プログラムには問題点があり、 1の状態から2に状態遷移してさらに1に状態遷移をすると無限ループに陥ってしまうことです。

この迷路問題は数字が大きいほうにしか行けないようなルールを設定しているので(バックトラック以外は)1から2にいってさらに1に行くことはありません。

しかし2から1に行くようなルールを追加したら、たぶん無限ループにはいります。 これの対処方法としては、以前行ったことのある状態には遷移しないという解決方法があります。 なのですでに遷移したことのある状態を記憶しておく必要があるんですね。

今回は実装していませんが...