Various Problem Solving Approaches

Various Problem Solving
Approaches
Problem solving by analogy
Very often problems can be solved by looking at
similar problems. For example, consider the
problem of adding two 1x3 matrices A and B. The
matrices are made up of 1 row and 3 columns.
Let A = [ a11 a12 a13] B =[ b11 b12 b13].
Then A + B is
A + B = [a11+b11 a12+b12 a13+b13]

Problem solving by analogy
Suppose we have developed a program for
adding the two matrices A and B. Then the
program can be easily modified for matrix
subtraction. All we need to do is to replace the +
sign by the sign.
A-B = [a11-b11 a12-b12 a13-b13]
In problem solving by analogy, we use a solution
that solves an analogous problem.
Problem solving by brainstorming
Consider a scenario in a company, when it has got
an additional project
To manage the extra work, a discussion is made
between 3 employees of the company and they
give different suggestions.
First participant suggests outsourcing the work
Second participant suggests to hire a new
employee.
Third one suggest to share extra workload among
employees
Weight age for each idea is given on the basis of
cost, feasibility and ease of implementation, and
how it will help other processes.
Generated Low cost Easy to Will help Total
idea implement other
and is processes
feasible
Outsource 20 20 20 60
to a vendor
Hire a new 30 10 10 50
employee
Share the 10 30 30 70
extra
workload
We see that hiring a new employee is the best
solution since it has the lowest total score.
Brainstorming works by focusing on a

problem, and then deliberately coming up
with as many solutions as possible and by
pushing the ideas as far as possible.
Problem solving by abstraction
Suppose we have a quadratic equation a*x^2
+ b*x + c = 0.
Then a well-known result says that the roots

of that quadratic equation are
X1 = ( -b + squareroot(b^2 -4*a*c) ) / (2*a)
X2 = ( -b - squareroot(b^2 -4*a*c) ) / (2*a)

Suppose we have been asked to solve the
equation a*y^4 + b*y^2 + c =0. Then
substituting y^2 by x we get the quadratic
equation a*x^2 + b*x + c = 0. We know how to
solve this quadratic equation so we can also
solve the equation
a*y^4 + b*y^2 + c =0.

A computer program for the quadratic
equation helps to easily obtain a computer
program for a quartic equation.
Abstraction helps to simplify the original

problem into problems which are simpler and
for which we know the solution.
Problem solving by divide and
conquer
Suppose we have the sorted array
1 4 6 7 12 13 15 18 19 20 22 24. Suppose we
want to search for 20. We compare 20 with 13
which is in the middle of the sorted array and find
20 > 13.
Next we search for 20 in 15 18 19 20 22 24. We
find 19 is the middle element of that list. Then we
search for 20 in 20 22 24. We find 20 is the first
element in 20 22.
conquer
The technique we just described is called as
binary search. Every iteration in binary search
eliminates half of the remaining possibilities.
This makes binary searches very efficient -
even for large collections. Binary search is an
example of divide and conquer.
conquer
The Euclidean algorithm of finding the gcd of
two integers is another example of the divide
and conquer strategy.A divide and conquer
problem solving strategy works by recursively
breaking down a problem into two or more
sub-problems of the same (or related) type,
until these become simple enough to be
solved directly. The solutions to the sub-
problems are then combined to give a solution
to the original problem.
Problem solving by exhaustive search
Suppose we have a Boolean expression
F(a, b, c) = ab`c` + abc` + ac`
One way of finding all the tuples (a, b, c) that

yield true is to try out all the possibilities for
the Boolean variables a, b, c.
This gives 2^3 possibilities.

Problem solving by exhaustive search
Suppose we have n variables then we get 2^n
possibilities.
This is an example of exhaustive search.
Here the number of searches grows
exponentially with n.
Exhaustive search is also known as brute-force
search.
Problem solving by trial and error
Suppose we have to factor the polynomial x^2
+ 4x + 3.
The original binomials must have looked like
this:
(x + m)(x + n),
where m and n are integers.We need to figure
out the values of m and n. The constant term
of the original polynomial is 3, so we need
m*n = 3.
What integers multiply together to give 3? The
only choices are 1 and 3, or perhaps -1 and -3.
The coefficient of the x term in the original
polynomial is 4, so we also need
m + n = 4.
Since 1 and 3 multiply to give 3 and add
together to give 4, we have m = 1 and n = 3.
Therefore, we can factor our original
polynomial as
(x + 1)(x + 3)
If we let m = 3 and n = 1 we'll have the same
factorization, except with the factors written in
a different order. Either way is correct,
The problem was solved by the problem solving
strategy of trial and error. Trial and error can be
used for solving puzzles such as Sudoku.
Problem solving by backtracking
Suppose we have to arrange 8 queens in a chess
board such that no two queens attack each
other.
This puzzle is called the 8 queens puzzle.
We can solve this puzzle by considering partial
candidates.
The partial candidates are arrangements of k
queens in the first k rows of the board, all in
different rows and columns.
Any partial solution that contains two mutually
attacking queens can be abandoned, since it
cannot possibly be completed to a valid
solution.
Backtracking is a problem solving strategy that
can be applied only for problems which admit
the concept of a "partial candidate solution"
and a relatively quick test of whether it can
possibly be completed to a valid solution.
Thus the 8 queens puzzle can be solved by
backtracking. Backtracking is often faster than a
brute force strategy.
Any partial solution that contains two mutually
attacking queens can be abandoned, since it
cannot possibly be completed to a valid solution.
Backtracking is a problem solving strategy that can
be applied only for problems which admit the
concept of a "partial candidate solution" and a
relatively quick test of whether it can possibly be
completed to a valid solution.
Thus the 8 queens puzzle can be solved by
backtracking.
Backtracking is often faster than a brute force
strategy.
Eight queens problem
Algorithm:
Start with one queen at the first column first
row
Continue with second queen from the second
column first row
Go up until find a permissible situation
Continue with next queen
Red cells show ruled out cells
Placing First Queen Options for Second Queen
So the next queen Q2 has to options: B3 or B4

Choose B3
Placed two Queens Options for third Queen
No option for placing third queen

Back track and choose B4 for second queen
Change two Queens Options for third Queen
Third queen can be placed in C2

But Fourth queen cannot be placed else where
Backtrack and change position of first queen to A2

Various Problem Solving Approaches

Uploaded by

Copyright:

Available Formats

Various Problem Solving Approaches

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Various Problem Solving Approaches

Uploaded by

Copyright:

Available Formats

Various Problem Solving

Let A = [ a11 a12 a13] B =[ b11 b12 b13].

A + B = [a11+b11 a12+b12 a13+b13]

Brainstorming works by focusing on a

Then a well-known result says that the roots

X1 = ( -b + squareroot(b^2 -4ac) ) / (2*a)

X2 = ( -b - squareroot(b^2 -4ac) ) / (2*a)

ay^4 + by^2 + c =0.

Abstraction helps to simplify the original

Suppose we have a Boolean expression

F(a, b, c) = ab`c` + abc` + ac`

One way of finding all the tuples (a, b, c) that

This gives 2^3 possibilities.

So the next queen Q2 has to options: B3 or B4

No option for placing third queen

Third queen can be placed in C2

You might also like