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