## June 7, 2016

### Problem Solving Methodology in Real World Situation

Filed under: 09. Projects & Proposals, NIL - All Posts — myreaders @ 9:23 am

Title :    Problem   Solving   Methodology    in    Real    World    Situation

Article   in   tutorial   form   for   students   working  on   ‘Real   World   Problem   Solving   Project’.

Your   problem   belongs   to   a   Real   World   Situation.

Start   with   a   few   things   you   may   or   may   not   know,   then   move    on  to  problem  solving    methodology.

1.   Problems  are  of   two   types

• Analytical  problems  like  ‘computation  of  the square’  can  be  solved  through  the use  of  deterministic  procedure  and  the   success  is  guaranteed.
• Real world problems do not offer straight forward  solutions. The most real world problems  can  be  solved  only  by  searching  for  a  solution.

Here  after   the  word   problem  addresses  only  real  world  problem.

2.   Defining  few  terms

• Problem  is  defined  by  its  elements   and  their  relations.
• State  is  a  representation  of  elements  at  a  given  instant.
•  Descriptors  tell  how  to  select  elements ?   At  each  instant  elements  have     specific  descriptors  and  relations.
• Initial  state    is     start point.
• Final  state      is     goal state.
• State  change  means  moving  one  state  to  another  state.
• Successor  function  is  a  description  of  possible  actions  for  state  change.
• Actions   are   a  set  of  operators.
• State  space  is  the set of all states reachable from the initial state that  forms a graph  (or map).
• Structures  of  State  space   are   graphs   and   trees.
• Graph  is  a  non-hierarchical  structure  has several paths  to  a  given node.   A graph  consists  of  a  set  of nodes  (vertices)  and  a  set  of edges (arcs).  The  nodes are  states  and  the edges  between  nodes  are  actions.  The edges establish  relations  (connections)  between  the   nodes.
• Tree  is a  hierarchical  structure  in  a  graphical  form.  A   tree  has  one  and  only one  path  from  any  point  to  any  other  point.
• Path  :  In  state  space,  a  path  is  a  sequence  of  states  connected  by  a  sequence  of   actions.

3.   Problem  solving  is  a  process  of  generating solutions  from  observed data.  The  data  consists  a  set  of  goals ,  a  set  of  objects ,   a  set  of  operators.  In  problem  solving it  is not  always  possible  to  go  directly  from  data  to  solution  called  direct methods. Instead,   problem   solving   often   need   to   use  indirect   or   model-based   methods.

4.   Problem  definition  :  A  problem  is  defined  precisely,  by  its elements  and  the relations  among  elements,  by  finding  the  input  and  the  final  situations  for  an acceptable  solution.  The  elements  and  relations  could  initially be  ill-defined  and evolve   better   during   problem   solving.

5.   Problem   space   is   an   abstract   space   called   state  space.

• Problem  space   encompasses   all   valid  states  generated  by  the  application  of operators   on   any   combination  of  objects.
• Problem  space   may   contain  one  or  more  solutions.
• Solutions  are   combination  of  operators  and  objects  that  achieve  the  goal.

6.   Search   refers   to   the  search   for  a  solution  in  a  problem  space.  The   search  proceeds   with   different   types   of   search   strategies.

7.   Building   system   to   solve   problem  :  you  need  to   do   the   following.

• Define   the   problem   precisely  (as  mentioned  above).
• Analyze   the  problem,  means  find  few  important  features  that  may  have  impact   on   possible   techniques   for   solving   the   problem.
• Isolate   and   represent   task   knowledge   necessary   to   solve   the   problem.
• Choose   best   problem   solving   technique(s)   and   apply   to   solve   the  problem.

8.   Formal   description   of   a   problem  :   you   need   to   do   following.

• Define  problem  space  called  state  space  that  contains  possible  configurations    of   the   relevant   objects.
• Specify  one   or   more  states  from  which  the  problem-solving  process  may start.   These   states   are    called   initial  states.
• Specify  one  or  more  states  that   would  be  acceptable  solution  to  the  problem.   These   states   are   called   goal   states.
• Specify  a  set   of   rules   that   describe   the   actions  (operators)   available.

9.   Problem  solving  model :  Most   if   not   all    real-world  problems   do   not  offer  any   direct   solution.   The   real-world   problems   are   solved   algorithmically.

• Algorithmic  solution  means  looking  for  a  finite set  of  unambiguous  instructions such  that  given  a  set   of  initial  conditions,  the  instructions  can  be  performed  in  a   prescribed  sequence  to  achieve  a  certain  recognizable  set  of end  conditions   called   goals   (solutions).
• Instruction  sets   comprise  rules   combined   with  a  strategy. The   instructions  sets  are  steps  that  pass  through  the  problem  space  until  a  path   from  an initial  state  to  a  goal  state  is  found.  This  methodology  is  known  as  search  process   and   the   algorithm   is   known   as   problem   solving   model.

10.  Summary   of   problem   description   &   solving

• Problem  consists  the  description  of current state  and  the actions  that  can  transform   one   state   into   another  state  to   reach   the  goal  state.
• State  space   describes   everything   that   is   needed  to  solve  a  problem.
• Operators  are  to  change  state,  do  actions  that  can  transform  one  state  into another. The  operators  include  the preconditions  and  the   instructions. The preconditions  provide  partial  description  of  the states  that  must  be  true  to perform   the   actions.  The  instructions   tell  on  how  to  create  next  state.
• Problem  solving   is   finding   an  ordered sequence  of  operators  that  transform  the  current  (start)  state   into   next   state   and   finally   goal   state.

11.  Mathematical   formulations

Follow  the  notations  and   the  representations  for  set,  relation,  function,  domain,  range,  restrictions,  mapping,   equation   and   many   more.

• Set  is  a  collection  of  distinct  things  or  items  or  objects,  or  numbers  etc,  that have  common  property  among  them.  Examples :   (a)   Collection  of  items you wear  like  :  shoes,  socks,  hat,  shirt;    (b)   Collection of  types  of  fingers  as  :  thumb,  index, middle,  ring,  pinky;   (c)   Collection of  odd  numbers  as  :  1 , 3 , 5 , 7 , 9 , 11 , 13 ;   The  individual  item  such  as  shoes,  socks,  middle,  ring,  3 ,  5 ,  11 are  called   element   or   member   of   the   respective   set   or   collection   or   group.
• Set  representation  is  a  list of  elements  separated  by  a comma,  and  then  put  the  whole  thing   within  curly  brackets   around.  Examples :  (a)  Set  of  items  you  wear  :  {shoes,  socks,  hat,  shirt}.  (b)  Set of fingers : {thumb,  index, middle,   ring,  pinky} .  (c)  Set  of  odd  numbers  :  {1,  3,  5,  7,  9,  11,  13} .
• Relation   is   a   set   of  ordered  pair  of  the  form  (x, y) .  Example :  A  set  { (1 , a),  (1 , b),   (2,b),   (3,c),   (3, a),   (4,a) }   is   a   relation.
• Function  relates   an  input  to  an  output. A  function  has  three  parts :  (a)  input,  (b) relation-ship,   (c)  output.  Example :  f(x)  =  x2   where  f  is name  of   the  function  used. The  input  is x  is  that  goes  into  the function  is  put  inside  parentheses () ;   The  relationship  is  what  function  does  to  the  input  is  ‘squaring’ ;   The   output  is  x2.  Example :  If  input  is  4  then  function  is  written  as  f(4)  =  16   which   means    is   some   way  related  to  16   which   is  expressed as   4 → 16   that   tells   4   is   mapped   into   16 .
• Function  is  a  relation (a  set  of  ordered  pairs)  usually  named  by  lower-case  letters   such  as  f ,  g ,  h.   Example :  f  =  { (-3 , 9) ,  (0 , 0) ,  (3 , 9) } ;    g  =  {(4 , -2),  (4 , 2) }
• Function   has   a   rule   in   which  no  two  ordered  pair  have  same  x-value  but  may  have  same  or  different  y-value.  In  the  above  example  f  is  a   function   but g  is  not  a   function.
• Domain,  Co-domain  &  Range  of  a  function  f =  {(X , Y)} . These  are  names  used  in  defining  function.   Definitions :   (a)  Domain  is  set  X  of  elements  that  can  go into  the  function;   (b)   Co-domain  is  set  of  elements  what may possibly  come  out of function.;   (c)  Range  is set  Y  of  elements that  actually comes  out  of  a function.  Example :  If  a  function  f  =  {(a , A), (b , B), (d , D)}   then   (a)  domain  of  the  function  is  {a , b , d }  ;    (b)   co-domain  of  the  function  is  {A , B , C ,  D ,  E } ;(c)  range  of  the  function  is  {A , B , D } .
• Function  and   mapping  :  A  function   may   be   viewed  as  a  mapping  or  a  pairing  of  elements   of   one  set  with  elements  of  second  set  such  that  each  element  of  the  first  set  (called  domain  is  paired  with  exactly  one  element  of  the  second   set  (called   co-domain).  Example  :  If  a  function f,  maps  set {a , b , d } into   set {A , B , C , D , E}   such   that   a → A   (read  ‘a  is  mapped  into  A‘) ,    b → B , d → D  then   the   domain   is  {a , b , d}   and   the   co-domain   is  {A , B , C , D}.  Note  that   (a)  the  element  of  the  co-domain  which  corresponds  to  an  element of  the  domain  is  called   the   image   of   that   element.  For  example,  element  a  of   domain   is   paired with   element    in   co-domain,  then  A  is  called  the  image   of  a ;   (b)  The  set   of   image   points {A , B , D}   is   called   the  range.  Thus,   range   is   a   subset   of   the   co-domain.
• Onto  mappings :   Set  A  is  mapped  onto  set  B   if  each  element  of  set B  is  image  of   an   element  of   a  set A.  Thus,   every  function  maps  its  domain  onto  its   range.
• Describing  function   by  an   equation : The  rule  by  which  each  x-value  gets  paired  with  the  corresponding  y-value  may  be  specified  by  an  equation. Example :   A   function   described  by   equation  y  =  x + 1   requires   that   for   any  choice   of  x  in  the  domain,   the   corresponding   range   value   is  x + 1.    Thus,   2 → 3 ,   3 → 4 ,    4 → 5   is   the   function   description

12.  Example  of   a  Real   World   Problem  :

A   game   of   8–Puzzle .    Solve   the   problem   algorithmically.

• State space    :    configuration  of  8 – tiles  on  the  board.
• Initial state    :    any configuration
• Goal state      :    tiles in a specific order
• Action            :    ‘blank moves’
• Condition      :    the  move  is  within  the  board
• Rule              :    blank  moves  Left,  Right,  Up,  Dn
• Solution        :    optimal sequence of operators

Conclusion  :

You   have   learned   a   methodology   to   solve    Real   World   Problems.   Apply   this methodology    and    solve    your   specific    ‘Real   world   problem’.

Tags :   Real World  Situation,  Problem definition,  Problem  solving,  Problem  space, Search,  Building system  to  solve  problem,  Formal  description  of  a  problem,  Problem solving  model,  Mathematical   formulations,  Example  of  real-world  problem.