がりらぼ

WindowsRuntimeの応援ブログ

迷路問題を状態空間表現で表してみる

前回水差し問題を状態空間表現で表してみました。 状態空間表現については前回の記事を参考にしてください。

今回は、このような迷路問題を状態空間表現であらわしてみます。

f:id:garicchi:20140527075859p:plain

※大まかなクラスは前回と同じですがところどころメソッドを変更しています。

Program.cs

Main関数です。

初期状態は1から始まり、ゴール状態の8で終わります。 その間の状態の変数としてxを使用します。

ルールは7個あり、迷路の各移動ルールに準じています。 1にいるときは2と4に移動でき、2にいるときは3にしか移動できない。 4にいるときは5に移動することができ、5にいるときは6、7、8に移動できます。 3と6と7と8は行き止まりです。

今回はある状態からスタート地点に戻るような操作は考えません。

さらに、ルールの適用順は考えず、テキトーにすべてのルールを適用してみます。

//最初の状態
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);

//テキトーにルールを適用してみる
foreach (var rule in problem.RuleList)
{
    problem.CurrentState.ApplyRule(rule);
    Console.WriteLine("Apply Rule {0}",rule.Name);
}


//出力
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"]);

State.cs

問題のある状態を表します。 前回の記事より比較メソッドやルールを適用するメソッドが増えています。 Stateはコピーコンストラクタをもちます。これは、State状態は今後問題を解くにあたって、複数のインスタンスを定義する必要があり、オブジェクトの実体をコピーできるようにするためです。

//状態
public class State
{
    //状態を表現する値のリスト
    public IDictionary<string,string> ValueList { get; set; }

    public State()
    {
        ValueList = new Dictionary<string,string>();
        
    }

    //コピーコンストラクタ
    public State(State state)
    {
        ValueList = new Dictionary<string, string>(state.ValueList);        
    }

    //状態を比較
    public bool Compare(State state)
    {
        bool result = true;
        for(int i=0;i<state.ValueList.Values.Count;i++)
        {
            if (state.ValueList.Values.ElementAt(i) != ValueList.Values.ElementAt(i))
            {
                return false;
            }
        }
        return true;

    }

    //ルールを適用する
    public void ApplyRule(Rule rule)
    {
        if (rule.CurrentCondition(this))
        {
            rule.NewAction(this);
        }
    }
    //ルールが適用できるか調べる
    public bool IsApplyRule(Rule rule)
    {
        return rule.CurrentCondition(this);
    }

    
}

Rule.cs

問題に適用するルールです。 前回の記事ではルールにApplyメソッドがあってStateに適用させていましたが廃止しました。 ルールを1意に特定するstring型の名前を持ちます。

//状態を変えるルール
public class Rule
{
    public string Name { get; set; }
    //現在の状態に適用される条件
    public Func<State, bool> CurrentCondition { get; set; }
    //条件に一致したときに実行されるアクション
    public Action<State> NewAction { get; set; }
    public Rule(string name,Func<State, bool> currentCondition, Action<State> newAction)
    {
        this.Name = name;
        this.CurrentCondition = currentCondition;
        this.NewAction = newAction;
    }

    
}

Problem.cs

問題をあらわすメソッドです。 問題は初期状態と終了状態をもち、ルールのリストも持ちます。 IsEndメソッドは現在の状態が終了状態と等しいなら終了状態であると判断します。

public class Problem
{
    //初期状態
    public State BeginState { get; set; }

    //現在の状態
    public State CurrentState { get; set; }
    //終了状態
    public State EndState { get; set; }
    //ルールのリスト
    public IList<Rule> RuleList { get; set; }

    public Problem(State beginState,State endState,IList<Rule> ruleList)
    {
        this.BeginState = beginState;
        this.EndState = endState;
        this.RuleList = ruleList;
        //初期状態をディープコピー
        this.CurrentState = new State(beginState);
    }


    public bool IsEnd()
    {
        return CurrentState.Compare(EndState);
    }
}

今回はテキトーにルールを適用したので状態が3で終了しています。 これでは迷路が解けていません。 次回以降で迷路を解かせるようなルールの適用順を導き出すプログラムを作っていきます。

f:id:garicchi:20140527082311p:plain