dimanche 17 avril 2016

Any way to avoid Object/casts in the child classes here?

Following the book "Artificial Intelligence - A Modern Approach" I am trying to make search algorithm implementations (DFS, A*, etc.) that can work with different problems (path from A to B, sliding-block puzzle, etc.) instead of just the one specific problem.

public abstract class Problem
{
    protected Problem(object initialState)
    {
        InitialState = initialState;
    }

    public object InitialState { get; }

    /// <summary>
    /// Checks if the state is the goal state
    /// </summary>
    public abstract bool IsGoalState(object state);

    /// <summary>
    /// Returns the actions available from the state
    /// </summary>
    public abstract ISet<Action> Actions(object state);

    /// <summary>
    /// Returns the state that results after performing the action on the state
    /// </summary>
    public abstract object ResultState(object state, Action action);

    /// <summary>
    ///  Returns the cost of action to reach from state to reachedState
    /// </summary>
    /// <param name="state">The state from which the action will be performed</param>
    /// <param name="action">One of the actions available in the state</param>
    /// <param name="reachedState">The state that results after performing the action</param>
    public virtual int StepCost(object state, Action action, object reachedState)
    {
        return 1;
    }
}

_

public class Node
{
    public Node(object state)
    {
        State = state;
        PathCost = 0;
    }

    /// <summary>
    /// </summary>
    /// <param name="action">The action that was applied to the parent to generate the node</param>
    /// <param name="stepCost">The cost from the parent node to this node</param>
    public Node(object state, Node parent, Action action, int stepCost)
        : this(state)
    {
        Parent = parent;
        Action = action;
        if (Parent != null)
            PathCost = Parent.PathCost + stepCost;
    }

    public object State { get; }

    public Node Parent { get; }

    /// <summary>
    /// The action that was applied to the parent to generate the node
    /// </summary>
    public Action Action { get; }

    /// <summary>
    /// The cost of the path from the initial statee to the node
    /// </summary>
    public int PathCost { get; }

    public bool IsRootNode => Parent == null;

    public IEnumerable<Node> PathFromRoot()
    {
        var path = new Stack<Node>();

        var node = this;
        while (!node.IsRootNode)
        {
            path.Push(node);
            node = node.Parent;
        }
        path.Push(node); // root

        return path;
    }
}

_

public abstract class Action
{
    /// <summary>
    /// true if it is a "No Operation" action
    /// </summary>
    public virtual bool IsNoOp()
    {
        return false;
    }

    public string Name => GetType().Name;

    public override string ToString()
    {
        return Name;
    }
}

public class NoOp : Action
{
    public override bool IsNoOp()
    {
        return true;
    }
}

public abstract class EightPuzzleAction : Action
{
}

/// <summary>
/// Move the blank tile to the left
/// </summary>
public class MoveLeft : EightPuzzleAction
{
}
// the same MoveRight, MoveTop, MoveBottom

In order to do that I can implement methods from this base Problem class and pass that concrete instance to a search algorithm (that accepts Problem).

class EightPuzzleProblem : Problem
{
    private readonly int[,] _goalState =
    {
        {0, 1, 2},
        {3, 4, 5},
        {6, 7, 8},
    };

    public EightPuzzleProblem(int[,] initialState) : base(initialState)
    { }

    public override bool IsGoalState(object state)
    {
        var puzzleState = (int[,]) state;

        ......... <check if puzzleState is the same as _goalState>
    }
    ............
}

class DepthFirstSearch
{
    public IEnumerable<Action> Search(Problem p)
    {
        return DfsRecursive(p, new Node(p.InitialState));
    }

    public IEnumerable<Action> DfsRecursive(Problem p, Node node)
    {
        if (p.IsGoalState(node.State))
            return node.PathFromRoot();

        .......<simple DFS implementation>
    }
}

// usage example

var dfs = new DepthFirstSearch();
var result = dfs.Search(new EightPuzzleProblem(initialState));

if (!result.Any)
   // fail
if (result.Count == 1 && result[0].IsNoOp)
   // already at goal


foreach (var act in result)
{
    if (act is MoveLeft) .....
}

But I see one inconvenience with my class design: in the concrete class implementation code I need to have a lot of casts from object. Is there any way to avoid that? If I make the Problem class generic and inherit ConcreteProblem from Problem<Something> then I will not be able to use it via Problem...

Aucun commentaire:

Enregistrer un commentaire