がりらぼ

WindowsRuntimeの応援ブログ

C#で最良優先探索

最良優先探索法

前に迷路問題の状態空間表現を作成し、2回にわたって縦型探索と横型探索を適用してきました。

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

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

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

しかし、これらは網羅的探索法と呼ばれ、ゴールがどちらにありそうかとかは関係なくただ単に総当たりでゴールを探す方法です。

今回は、「ゴールがどっちにありそうか」、という情報を与えて、それに従ってゴールがありそうな方向に探索を進めるようにしましょう。

このようなゴールがありそうな方向に探索を進める方法を発見的探索法とよばれます。 また、ある状態でどれくらいゴールが近いかという情報は「評価値」と呼ばれ、評価値を取得する関数を発見的関数といいます。

今回は発見的探索法の中でも戻ってもいいから評価値が高い方向に進むという風に探索を行う最良優先探索法を実装します。

例えば前の迷路問題を最良優先探索法で解くとすると、 最初の状態「1」から適用可能なルールをすべて求め、 今回は「2」と「4」に遷移できそうなので「2」と「4」の評価値を計算します。 この迷路は状態の数字が大きければ大きいほどゴールに近そうなので状態の数字をそのまま評価値とします。 すると、「2」と「4」では「4」のほうが評価値が高いので「4」に進みます。

f:id:garicchi:20140531112911p:plain

「5」に移動したとき、現在の状態リストは「4」と「2」と「5」です。 このなかで一番評価値が大きいのは「5」なので「5」に進みます。

f:id:garicchi:20140531113458p:plain

「5」に移動したとき、現在の状態リストは「2」「4」「5」「6」「7」「8」です。このなかにゴール状態である「8」が入っているので探索終了です。

f:id:garicchi:20140531113604p:plain

今回は、評価値の計算方法として発見的関数を状態のラベル値の大きい順ということにしました。 つまり状態のラベル値が小さい方より大きいほうがゴールに近いとかんがえているのです。 なので発見的関数を状態のラベル値が小さければ小さいほど大きい評価値を返すような関数にすれば、ゴール状態からスタート地点まで行くことが可能です。

アルゴリズム

①未探索状態の集合の中で一番評価値が大きいものを選択

②選択した状態に適用可能なルールをすべて求める。

③ルールが1つもなかったら探索失敗

④適用可能なルールをすべて適用して新しい状態集合を得る。

⑤新しい状態集合の中にゴール状態があれば探索成功

⑥現在の未探索状態の集合に新しい状態集合を追加し、①にもどる

今回も、迷路問題の状態空間表現のState.csとProblem.csとRule.csを使います。

BestFirstSearch.cs

基本的にアルゴリズム通りです。 メンバーは現在の未探索状態集合と、現在考えている問題です。 GetHuristicValueが発見的関数です。状態のラベル値をそのままint型で返します。 ISearchインターフェースを実装していますがただのExecuteメソッドしかないインターフェースです。

//最良優先探索法
public class BestFirstSearch:ISearch
{
    //現在の未探索状態
    public IList<State> CurrentStateList { get; set; }
    //現在の問題
    public Problem CurrentProblem { get; set; }
    
    public BestFirstSearch(Problem problem)
    {
        CurrentProblem = problem;
        CurrentStateList = new List<State>()
        {
            new State(problem.BeginState)
        };
        
        
    }

    public bool Execute()
    {
        while (true)
        {
            //現在の未探索リストから一番評価値(発見的関数の値)が大きい状態を一つ選択
            var state = CurrentStateList.OrderByDescending(q => GetHuristicValue(q)).First();
            //その状態に適用できるすべてのルールを取得
            var ruleList = CurrentProblem.RuleList.Where(q => state.IsApplyRule(q)).ToList();
            //ルールが一つもなかったら探索失敗
            if (ruleList.Count == 0)
            {
                return false;
            }

            //ルールをすべて適用して新しい状態集合を取得
            var newList = new List<State>();
            foreach (var rule in ruleList)
            {
                var s = new State(state);
                s.ApplyRule(rule);
                newList.Add(s);
                //新しい状態集合にゴール状態があれば探索成功
                if (s.Compare(CurrentProblem.EndState))
                {
                    CurrentProblem.CurrentState = s;
                    return true;
                }
            }
            //新しい状態集合を現在の状態集合に追加
            CurrentStateList=CurrentStateList.Concat(newList).ToList();
            //出力
            Console.WriteLine("Current Search State "+string.Join(",",CurrentStateList.Select(q=>q.ValueList.Values.First())));
        }
        
    }

    //発見的関数
    //状態の評価値を計算する
    //今回は状態のラベル値を評価値とする。
    private int GetHuristicValue(State state)
    {
        return int.Parse(state.ValueList["x"]);
    }
}

Probram.cs

Main関数があるエントリポイントです。 前と同じように迷路問題の状態空間表現をし、BestFirstSearchを実行します。

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 BestFirstSearch(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"]);

    }
}

実行結果

実行結果です。 現在の未探索状態がちゃんと上図のとおりになっていますね。「1」がありますが

f:id:garicchi:20140531114442p:plain

前にやっていた縦型探索や横型探索よりも早く、かつメモリが少なく探索成功することができました。 これだけ小さな迷路ではわかりにくいですが、もっと大きな迷路問題になると、探索スピードが大きく変わってきます。 大きな問題に網羅的探索法をすると組み合わせ爆発を起こし、いつまでたっても処理がおわらないという状態に至ってしまいます。 そういう時に、コンピュータにより良い方向に探索をさせて最小限のリソースでゴール状態までたどり着かせると比較的早く探索成功させることができます。

しかし最良優先探索法の場合、前にも戻る必要があるので未探索状態集合が探索するたびに増大していくので注意が必要です。 あと、評価値を計算できないような問題には適用できません。