Introduction to Artificial Intelligence - Old Questions
3. What is state space representation of problem? Represent the root finding problem having four cities in to state representation (you can choose any ordering of cities and links) and devise the complete problem formulation.
Answer
AI is thinking...
The state space is commonly defined as a directed graph in which each node is a state and each arc represents the application of an operator transforming a state to a successor state. A solution is a path from the initial state to a goal state.
State Space representation of Vacuum World Problem:
States: two locations with or without dirt: = 8 states.
Initial state: Any state can be initial
Actions: {Left, Right, Suck}
Goal test: Check whether squares are clean.
Path cost: Number of actions to reach goal.
Representing the root finding problem having four cities in to state representation:
The above problem can be formulate as:
States: All four cities. {Oradea, Zerind, Sibiu, Arad}
Initial State: Current city where we are. For e.g. Oradea
Actions: Drive between cities or choose next city.
Goal test: Check whether the agent is in Arad and 4 cities have been visited.
Path Cost: Sum of distances.
A solution is a sequence of actions leading from the initial state to a goal state