Problem Solving through Searching PDF

Problem Solving through Searching 3/9/2024 34  Unit-2 Problem Solving Production Systems: Systems that generate (produce) rules (states) to reach a solution A production system comm...

Problem Solving through Searching 3/9/2024 34  Unit-2 Problem Solving Production Systems: Systems that generate (produce) rules (states) to reach a solution A production system commonly consists of following four basic components: 1. A set of rules of the form Ci Ai where Ci refers to starting state and Ai represents consequent state. Also Ci the condition part and Ai is the action part. 2. One or more knowledge databases that contain whatever information is relevant for the given problem. 3. A control strategy that ascertains the order in which the rules must be applied to the available database 4. A rule applier which is the computational system that implements the control strategy and applies the rules to reach to goal (if it is possible). 3/9/2024 35  State Space  State space search is a process used in which successive or states of an instance are considered, with the goal of finding a goal state with a desired property.  State space search often differs from traditional search (sequential, indexed sequential, binary search etc) methods because the state space is implicit: the typical state space graph is much too large to generate and store in memory. Instead, nodes are generated as they are explored, and typically discarded thereafter.  E.g. in a tic tack toe game, every move by a player forms a state space and the three similar (O or X) consecutive (row, column or diagonal) symbols forms goal state.  In a chess game also state space forms a set of moves by players.  We discuss water jug problem in the next section. 3/9/2024 36  State Space Search The water jug problem: You are given two jugs, a 4-litre one and a 3- litre one. Neither has any measuring markers on it. There is a pump that can be used to fill the jugs with water. How can you get exactly 2 litres of water into 4-litre jug. Let x and y be the amounts of water in 4-Lt and 3-Lt Jugs respectively Then (x,y) refers to water available at any time in 4-Lt and 3-Lt jugs. Also (x,y) (x-d,y+dd) means drop some unknown amount d of water from 4-Lt jug and add dd onto 3-Lt jug. All possible production rules can be written as follows 1. (x, y) (4, y) if x