Problem Solving
Problem Solving is a group of information that the agent will use to decide what to do. The basic components of a problem definition are the states and actions:
- The initial state that the agent knows itself to be in.
- The set of possible actions accessible to the agent. The term operator is used to indicate the explanation of an action in terms of which state will be reached by acting in a specific state. (An alternate formulation uses a successor function S.
- Given a particular state x, S(x) returns the set of states reachable from x by any single action.)
- Operator and Successor function define the state space of the problem, the set of all states nearby from the initial state by an order of actions.
- A route in the state space is simply an order of actions primary from one state to another. The goal test, which the agent can put on to a single state description to decide if it is a goal state.
- A route cost function is a function that assigns a cost to a route.
The initial state, operator set, goal test, and route cost function define a problem.
The performance measure of Problem solving
The efficiency of a search can be measured in at least three ways.
- First, does it has a solution at the end?
- Second, is its solution to maximize the performance (one with a low route cost)?
- Third, what is the search cost related to the time and memory required to find a solution?
The total cost of the search is the sum of the route cost and the search cost. a route with minimum cost will be followed.
General Search Algorithm
- function GENERAL-SEARCH(problem, strategy) returns a solution, or failure, initialize the search tree using the initial state of the problem.
- loop do
- if there are no candidates for expansion then return failure, choose a leaf node for expansion according to strategy
- if the node contains a goal state then return the corresponding solution
- else expand the node and add the resultant nodes to the search tree
- End
Some examples of problem-solving agents are vacuum cleaner, 8-Puzzle, robot navigation.
This article presents two uninformed search strategies that do not take into account the location of the goal. Spontaneously, these algorithms ignore where they are going until they find a goal and report success.
- Depth-first search
- Breadth-first search
Depth-First Search
The first strategy is a depth-first search. The depth-first search acts like a last-in-first-out stack.
The depth-first search every time expands one of the nodes at the deepest level of the tree. When the search hits a dead end (a non-goal node with no expansion) does the search go back and expand nodes at shallower levels.
The depth-first search has very modest memory requirements. it needs to store only a single route from the root to a leaf node, For a state space with branching factor b and maximum depth m, depth-first search requires storage of only bm nodes, whereas in Breadth-first it was bad.
- Algorithm outline:
- Always select from the OPEN the node with the greatest depth for expansion, and put all newly generated nodes into OPEN
- OPEN is organized as LIFO (last-in, first-out) list.
- Terminate if a node selected for expansion is a goal
The time complexity for depth-first search is O(bm).
return GENERAL-SEARCH(problem, ENQUEUE-AT-FRONT)
exp. node OPEN list
{ S }
S { A B C }
A { D E G B C}
D { E G B C }
E { G B C }
G { BC }
Solution route found is S A G <– this G has cost 10 Number of nodes expanded (including goal node) = 5
The drawback of a depth-first search is that it can get stuck going down the wrong route.
Breadth-first search
The next strategy is a breadth-first search. The root node is expanded first, then all the nodes created by the root node are expanded next, and then their beneficiaries, and so on.
Algorithm outline:
- Always select from the OPEN the node with the smallest depth for expansion, and put all newly generated nodes into OPEN
- OPEN is organized as FIFO (first-in, first-out) list, I.e., a queue.
- Terminate if a node selected for expansion is a goal
Properties:
- Complete
- Optimal (i.e., admissible) if all operators have the same cost. Else, not best but finds a solution with shortest path length (shallowest solution).
- Exponential time and space complexity, O(b^d) nodes will be generated, where d is the depth of the solution and b is the branching factor (i.e., number of children) at each node.
The memory requirements are a bigger issue for the breadth-first search than the execution time. BFS is suitable for problems with shallow solutions.
exp. node OPEN list
{ S }
S { A B C }
A { B C D E G }
B { C D E G G’ }
C { D E G G’ G” }
D { E G G’ G” }
E { G G’ G” }
G { G’ G” }
Solution path found is S A G <– this G also has cost 10 Number of nodes expanded (including goal node) = 7