Problem Solving

  • Post author:
Download PDF
Advertisement

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.

Advertisement

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 }

problem solving

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.

problem solving

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

 

Tugging Test

Advertisement

This Post Has 3 Comments

  1. minecraft

    Just want to say your article is as surprising. The clarity
    in your publish is simply spectacular and that i could assume you
    are knowledgeable in this subject. Well along with your permission allow me to snatch your feed to
    stay up to date with drawing close post. Thank you a million and please carry on the enjoyable work.

  2. minecraft

    Very good article. I certainly appreciate this
    website. Keep writing!

  3. zvodret iluret

    I have learn some excellent stuff here. Certainly worth bookmarking for revisiting. I wonder how a lot attempt you set to make this kind of wonderful informative web site.

Comments are closed.